c# - 为什么 F#'s default set collection is sorted while 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树不同，树的遍历是基于哈希的，所以不需要比较约束。

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