为什么F#的默认set集合排序而C#的默认集合没有排序? [英] Why F#'s default set collection is sorted while C#'s isn't?

问题描述

从C#世界迁移到F#(最常见的)心态时，我发现了这种有趣的区别.

When migrating from a C# world to an F# (the most idiomatic possible) mindset, I've found this interesting difference.

在C#的OOP& mutable世界中，默认的集合集合似乎是

In C#'s OOP&mutable world, the default set collection seems to be HashSet, which seems to be not sorted by default (because the comparer that it accepts is just for equality); while if you wanted a sorted one you would have to use SortedSet.

但是，在F#的世界中，基本的set已被排序，因为它需要用于实现等式和比较的元素类型.有什么具体原因吗?为什么在该语言的主要集合中不设置无序集合?

However in F#'s world, the basic set is already sorted because it requires the element type used to implement equality and comparison. Any specific reason for this? Why not having an unordered set in the main collections for this language?

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

As a side-note, I'm wondering if it'd be possible to have a set collection that didn't allow duplicates, but that had a preference over certain elements when discarding some elements as duplicates. Example: a record { Name: string; Flag: Option<unit> } so that when inserting { Name = "foo"; Flag = None } and later { Name = "foo"; Flag = Some() } it ended up containing only the latter element (because Flag is present).

推荐答案

F#Set恰好是排序的，但是更多的是实现细节，它是由基础数据结构的选择而产生的，通常不应该被依赖.

F# Set happens to be sorted, but it's more of an implementation detail resulting from the choice of the underlying data structure and should not generally be relied upon.

F#集和映射基于AVL树的变体，并且该结构恰好保持了对存储在树中的元素进行排序的不变性.之所以需要比较约束，是因为在此树结构中的查找取决于元素之间的直接比较，以选择要遍历的子树.

F# sets and maps are based on a variant of AVL tree and that structure happens to maintain the invariant that elements stored in the tree are sorted. The reason why it requires comparison constraint is because lookup in this tree structure depends on direct comparisons between elements to select the subtree that gets traversed.

但是，这些结构的卖点在于，它们可以用于廉价地实现合理高效，不变的地图和集合版本，而这正是在更广泛的.NET平台不提供任何功能的情况下F#所需要的替代品.

The selling point of these structures however is the fact that they can be used to implement reasonably efficient, immutable versions of maps and sets cheaply, and that's what F# needed at a time where the wider .NET platform didn't offer any alternatives.

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

Note that this is not the only viable choice in this context and JVM functional languages like Clojure or Scala opted for a different data structure as the base for their maps - hash array mapped trie - which is also immutable and persistent, arguably more complex to implement, arguably more efficient for larger collection sizes, but happens to store elements unordered. Unlike AVL trees, the traversal of the tree is based on hashes, so comparison constraint is not required.

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

So if you already know that your priority is immutability, a sorted set is actually easier to implement than an unsorted set.

这篇关于为什么F#的默认set集合排序而C#的默认集合没有排序?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！