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

Question

在从C#世界迁移到F#（最符合习惯的）思维方式时，我发现了这个有趣的差异。

在C#的OOP&可变世界中，默认的集合似乎是未排序的 HashSet，因为它接受的比较器仅用于相等性；而如果你想要一个排序的集合，则必须使用 SortedSet。

然而，在F#的世界中，基本的set已经排序，因为它需要用于实现相等性和比较的元素类型。有没有特定的原因？为什么不在该语言的主要集合中拥有无序集合？

作为旁注，我想知道是否可能有一个集合，它不允许重复项，但对于某些元素具有优先选择，当舍弃某些元素作为重复项时。例如：一个记录 { Name: string; Flag: Option<unit> }，当插入 { Name = "foo"; Flag = None } 后，再插入 { Name = "foo"; Flag = Some() } 时，它最终仅包含后一个元素（因为Flag存在）。

- knocte

---

C# 没有默认的集合设置。HashSet 更常见，因为不需要排序的情况更为普遍 - 查找、添加和集合操作。在这些情况下，HashSet 的性能为 O(1)，而 SortedSet 和 F# 的 set 则为 O(logN)。 - Panagiotis Kanavos

这里有两个需要阅读的链接：https://dev59.com/gGQo5IYBdhLWcg3wOtQC 和 https://dev59.com/FYfca4cB1Zd3GeqPmbWR。本质上，这里的区别在于可变性 - HashSet 设计为可变的，因此其实现优化了这种情况。而 F# 不是这样的。 - mjwills

@knocte Petricek 的第一个要点就是实际答案——HashSet 内部使用缓存，就像列表一样，因此只要不必重新分配缓存，添加或"删除"项就非常快——只需将某些内容写入到空闲的位置或"取消标记"即可。然而，生成一个新的(哈希)set 的集合操作可能比遍历两棵树更昂贵，就像 F#'s set 或 SortedSet 所做的那样。例如，可以查看 F#'s intersect 实现 [intersectAux] (https://github.com/fsharp/fsharp/blob/master/src/fsharp/FSharp.Core/set.fs#L317)。 基本上，它同时遍历两个树。 - Panagiotis Kanavos

可能是为什么 F# Set 需要 IComparable 接口？的重复问题。 - knocte

几乎是为什么F# Set需要IComparable？的副本，但在我看来并不是完全相同的。 - rmunn

Answer 1

F#中的Set是有序的，但这更多是由于底层数据结构的选择而导致的实现细节，并且通常不应过度依赖。

F#的集合和映射基于AVL树的变种，该结构恰好维护存储在树中的元素排序不变式。之所以需要比较约束是因为在此树结构中查找取决于元素之间的直接比较，以选择要遍历的子树。

这些结构的卖点是它们可以用来实现相对高效、廉价的不可变版本的地图和集合，这正是F#在.NET平台没有其他选择的情况下所需求的。

请注意，在此上下文中，这并不是唯一可行的选择，JVM功能性语言（如Clojure或Scala）选择了不同的数据结构作为其映射的基础 - 哈希数组映射Trie - 它也是不可变和持久的，对于更大的集合大小来说可能更复杂、更有效率，但恰好存储无序元素。与AVL树不同，树的遍历基于哈希值，因此不需要比较约束。

因此，如果您已经知道您的优先事项是不变性，则有序集比无序集更容易实现。

- scrwtp