为什么F＃的默认set集合排序而C＃的默认集合没有排序？

Question

从C＃世界迁移到F＃（最惯用的）思维方式时，我发现了这种有趣的区别。

在C＃的OOP＆mutable世界中，默认的set集合似乎是HashSet，它似乎不是默认排序的（因为它接受的比较器只是为了相等）。而如果要排序的话，则必须使用SortedSet。

但是，在F＃的世界中，基本set已经被排序，因为它需要用于实现相等和比较的元素类型。有什么具体原因吗？为什么在该语言的主要集合中没有无序集合？

作为附带说明，我想知道是否有可能有一个不允许重复的set集合，但是当丢弃某些元素作为重复项时，它优先于某些元素。示例：一条记录​​，{ Name: string; Flag: Option<unit> }以便在插入时{ Name = "foo"; Flag = None }稍后{ Name = "foo"; Flag = Some() }它最终仅包含后一个元素（因为存在Flag）。

Answer 1

F#Set恰好是排序的，但它更多的是由底层数据结构的选择产生的实现细节，通常不应依赖。

F# 集和映射基于 AVL 树的变体，该结构恰好保持了存储在树中的元素已排序的不变性。之所以需要比较约束，是因为这种树结构中的查找依赖于元素之间的直接比较来选择遍历的子树。

然而，这些结构的卖点是，它们可以用来以低廉的成本实现相当高效、不可变的映射和集合版本，而这正是 F# 在更广泛的 .NET 平台不提供任何替代方案的情况下所需要的。

请注意，这并不是这种情况下唯一可行的选择，并且像 Clojure 或 Scala 这样的 JVM 函数式语言选择了不同的数据结构作为其映射的基础 - 哈希数组映射 trie - 这也是不可变和持久的，可以说实现起来更复杂，对于较大的集合大小来说可以说更有效，但碰巧存储无序的元素。与AVL树不同，树的遍历是基于哈希的，因此不需要比较约束。

因此，如果您已经知道您的优先级是不变性，那么排序集实际上比未排序集更容易实现。