Why it is possible to specify a value comparer for ImmutableDictionary<TKey, TValue>?

Question

What is the intended usage of the ImmutableDictionary<TKey,TValue>.ValueComparer property?

Why is it useful being able to compare dictionary values by using a specified equality semantic?

I totally understand the necessity of being able to compare dictionary keys by using a specified equality semantic, but I can't get the point for value comparison. Why the immutable dictionary creator should be able to specify the intended semantic for value comparison ? Can you please show me a use case where it is useful ?

Interestingly enough, by checking at the Microsoft documentation, it seems that the Dictionary<TKey, TValue> class does not have a similar property. The only available comparer on the Dictionary<TKey, TValue> class is the one meant to compare the keys.

I'm totally sure that the public API of the ImmutableDictionary<TKey,TValue> class has been carefully designed, so I would like to understand what I'm missing about the need for value comparison in a dictionary.

Answer 1

I think the question should not be why ImmutableDictionary<TKey,TValue> allows to specify a comparer for values - the question should be why Dictionary<TKey, TValue> does not.

Both classes are general purpose containers for key-value pairs, with methods ContainsKey and ContainsValue. Both containers allow to specify an individual comparer for keys which is used in ContainsKey. So it is quite natural to assume - at least for reasons of symmetry - that specifying such a comparer for values should be possible as well. For ImmutableDictionary<...>, the designers obviously decided to do so, for Dictionary<...>, the designers did not, which seems to be odd, at least.

I can only speculate why Dictionary<...> is designed in such an unsymmetric way. My best guess is at the time when Dictionary<...> was introduced (14 years ago, in 2006, .Net Fw 2.0) "time-to-market" was more important than making the API more elegant by keeping these details symmetric. Maybe the designers later on decided not to change the public interface of the Dictionary<...> class, for not risking to add any breaking changes afterwards. I can imagine the designers of ImmutableDictionary<...> learned from the unsymmetric design of Dictionary<...> and decided to fix it for this new class (which is AFAIK from this year, 2020).

For a canonical answer, you would have to ask the designers at Microsoft by themselves.

Answer 2

As always the source code can give you some insight.

As Doc Brown has already mentioned the primary goal of the ValueComparer is to be able to implement ContainsValue.

If we look at the .NET Core implementation of the ImmutableDictionary then you can see that the implementation has split into many files:

• ImmutableDictionary_2.Builder.cs
• ImmutableDictionary_2.Comparers.cs
• ImmutableDictionary_2.Enumerator.cs
• ImmutableDictionary_2.HashBucket.cs
• ImmutableDictionary_2.MutationInput.cs
• ImmutableDictionary_2.MutationResult.cs
• ImmutableDictionary_2.cs

From our perspective the last file is the interesting one because it contains the ContainsValue method:

public bool ContainsValue(TValue value)
{
    foreach (KeyValuePair<TKey, TValue> item in this)
    {
        if (this.ValueComparer.Equals(value, item.Value))
        {
            return true;
        }
    }
    return false;
}

But when you take a look at the mono implementation then you can see it uses the comprarer in a slightly different way:

public bool Contains(KeyValuePair<TKey, TValue> kv)
{
    var node = root.SearchNode(kv, CompareKV);
    return !node.IsEmpty && valueComparer.Equals(node.Value.Value, kv.Value);
}