Why F#'s default set collection is sorted while C#'s isn't?

Question

When migrating from a C# world to an F# (the most idiomatic possible) mindset, I've found this interesting difference.

In C#'s OOP&mutable world, the default set collection seems to be HashSet, which seems to be not sorted by default (because the comparer that it accepts is just for equality); while if you wanted a sorted one you would have to use SortedSet.

However in F#'s world, the basic set is already sorted because it requires the element type used to implement equality and comparison. Any specific reason for this? Why not having an unordered set in the main collections for this language?

As a side-note, I'm wondering if it'd be possible to have a set collection that didn't allow duplicates, but that had a preference over certain elements when discarding some elements as duplicates. Example: a record { Name: string; Flag: Option<unit> } so that when inserting { Name = "foo"; Flag = None } and later { Name = "foo"; Flag = Some() } it ended up containing only the latter element (because Flag is present).

Answer 1

F# Set happens to be sorted, but it's more of an implementation detail resulting from the choice of the underlying data structure and should not generally be relied upon.

F# sets and maps are based on a variant of AVL tree and that structure happens to maintain the invariant that elements stored in the tree are sorted. The reason why it requires comparison constraint is because lookup in this tree structure depends on direct comparisons between elements to select the subtree that gets traversed.

The selling point of these structures however is the fact that they can be used to implement reasonably efficient, immutable versions of maps and sets cheaply, and that's what F# needed at a time where the wider .NET platform didn't offer any alternatives.

Note that this is not the only viable choice in this context and JVM functional languages like Clojure or Scala opted for a different data structure as the base for their maps - hash array mapped trie - which is also immutable and persistent, arguably more complex to implement, arguably more efficient for larger collection sizes, but happens to store elements unordered. Unlike AVL trees, the traversal of the tree is based on hashes, so comparison constraint is not required.

So if you already know that your priority is immutability, a sorted set is actually easier to implement than an unsorted set.