Why is the F # Set needed iComparable?

Question

Therefore, I am trying to use F # Set as a hash table. But my element type does not implement the IComparable interface (although it implements IEquatable ). I received a message stating that the design is not allowed due to limitation of comparison. And after some further reading, I found that the F # Set is implemented using a binary tree, which makes O(log(n)) reason for the insertion. This looks strange to me, why is the Set structure designed this way?

Edit: So, I found out that Set in F # is actually a SortedSet . And I think the question arises, why is the Sorted Set somehow preferable to a common set of hashes as an immutable / functional data structure?

Answer 1

There are two important points that will help you understand how the F # functions (and in functional languages ​​in general) work and how they are used:

• Implementing immutable hash tables (e.g. .NET HashSet ) is complicated - when you delete or add items, you want to avoid copying everything in the data structure and (as far as I know) there is no common path (you end up copying too much, so this will be inefficient).

  For this reason, most functional sets are implemented as (some tree shapes). This requires a comparison to build a sorted tree. A good feature of balanced trees is that deleting and adding elements does not need to copy everything to the tree, so even the worst-case scenario is quite effective (although a mutable hash table is even faster).

• Now F # is functionally first, which means that immutable structures are preferable, but it is perfectly normal to use mutable data structures (especially if you restrict the use to a certain well-defined and limited area). For this reason, F # programmers often use Dictionary or HashSet , especially if it is only within the same function.