I know this question is very similar to this one I asked some time ago: Why F#'s default set collection is sorted while C#'s isn't?
However, I'd like to confirm if the reason given there is the same for this case? And I wonder if there's an implementation of an immutable Map in F# out there, written by someone, which is less strict and doesn't require K to be comparable? I'd happily use it because I don't care so much about performance.
Why F#'s idiomatic dictionary collection
Map<K,V>needs the type K to implement comparable while C#'sDictionary<K,V>doesn't?
F# Map<Key, Value> requires keys to be comparable, because map is implemented as a tree structure (you have to decide which subtree to go depending on comparison result). C# Dictionary<Key, Value> is implemented as a bucket of linked lists. You get a bucket by hash code of key and then iterate list until you (not)find the equal key. In both data structures keys are compared. The only difference is that for dictionary equality comparison is enough.
So, the question is why F# Map has explicit comparison constraint, but C# Dictionary has implicit equality requirement?
Let's start with C#. What would be if the dictionary would have an IEquatable key constraint? Well, you would have to manually implement this interface for every custom data type used as dictionary key. But what if you want different implementations of equality? E.g. in some dictionaries you want your key string case insensitive. Of course, you can pass IEqualityComparer implementation to be used for keys comparison (not only to the dictionary, but anywhere when you need comparison). But why then enforce key to be comparable if external comparer will be used? Note that there is always a default comparer which is used if you don't pass anything to the dictionary. Default comparer checks if key implements IComparable and uses that implementation.
Why then F# has an explicit comparable constraint on key data type? Because this constraint will not enforce you to manually implement IComparable for every custom data type used as map key. One big difference between C# and F# type system is that F# types comparable and equatable by default. F# compiler generates IComparable, IComparable<T>, and IStructuralComparable implementations unless you explicitly mark type with NoComparison attribute. So this constraint doesn't enforce you to write any additional code when you use F# data types.
One more benefit of using comparison/equality constrains - F# has a number of predefined generic operations on types that implement comparison or equality (=,<,<=,>=,=,max,min). Which makes code with generic comparable/equatable types much more readable.