为什么 F# 的默认集合是排序的，而 C# 的不是？

Question

当从 C# 世界迁移到 F#（最惯用的可能）思维方式时，我发现了这个有趣的差异。

在 C# 的 OOP&mutable 世界中，默认的集合集合似乎是HashSet，默认情况下它似乎没有排序（因为它接受的比较器只是为了相等）；而如果你想要一个排序的，则必须使用SortedSet。

然而在 F# 的世界中，基本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树不同，树的遍历是基于哈希的，因此不需要比较约束。因此，如果您已经知道您的优先级是不变性，那么排序集实际上比未排序集更容易实现。