为什么F#Set需要IComparable? [英] Why does F# Set need IComparable?

问题描述

因此，我尝试将F#集用作哈希表.但是我的元素类型没有实现IComparable接口(尽管它实现了IEquatable).我收到一个错误消息，说由于比较约束，不允许进行构造.通过进一步阅读，我发现F#Set是使用二叉树实现的，这使得插入原因O(log(n)).这对我来说很奇怪，为什么Set结构是这样设计的?

So I am trying to use the F# Set as a hash table. But my element type doesn't implement the IComparable interface (although it implements IEquatable). I got an error saying the construction is not allowed because of comparison constraint. And through some further read, I discovered that F# Set is implemented using binary tree, which makes insertion causes O(log(n)). This looks weird to me, why is the Set structure designed this way?

因此，我了解到F#中的Set实际上是SortedSet.我猜想问题就变成了，为什么排序集在某种程度上比普通的哈希集更可取，因为它是不可变的/有功能的数据结构?

So I learned that Set in F# is actually a SortedSet. And I guess the question becomes, why is Sorted Set somehow more preferable than a general Hash Set as an immutable/functional data structure?

推荐答案

有两个重要的点可以帮助您了解F#(以及一般的功能语言)中的集合如何工作以及如何使用它们:

There are two important points that should help you understand how sets in F# (and in functional languages in general) work and how they are used:

• 实现不可变哈希表(例如.NET HashSet)非常困难-删除或添加元素时，您要避免复制数据结构中的所有内容，并且(据我所知)没有通用的方法这样做(您最终将复制过多，因此效率低下).

• Implementing immutable hashtables (like .NET HashSet) is hard - when you remove or add elements, you want to avoid copying everything in the data structure and (as far as I know) there is no general way of doing that (you would end up copying too much, so it would be inefficient).

由于这个原因，大多数功能集都被实现为(某种形式的树).那些需要比较以构建排序的树.平衡树的好特性是，删除和添加元素不必复制树中的所有内容，因此即使最坏的情况也相当有效(尽管可变哈希表仍然更快).

For this reason, most functional sets are implemented as (some form of trees). Those require comparison to build a sorted tree. The nice property of balanced trees is that removing and adding elements does not have to copy everything in the tree, so even the worst case scenario is reasonably efficient (though mutable hashtable is still faster).

现在，F#是功能优先的，这意味着不可变的结构是首选，但是使用可变数据结构是完全可以的(特别是如果您将用法限制在某些明确定义和限制的范围内).因此，F#程序员经常使用Dictionary或HashSet，尤其是当这仅在单个函数的范围之内时.

Now, F# is functional-first, which means that immutable structures are preferred, but it is perfectly fine to use mutable data structures (especially if you limit the usage to some well defined and restricted scope). For this reason, F# programmers often use Dictionary or HashSet, especially when this is only within the scope of a single function.

这篇关于为什么F#Set需要IComparable?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！