为什么Data.Set需要元素作为Ord的实例？

Question

这不起作用

data Cutlery = Knife | Fork deriving (Show,Eq)
let x = [Knife,Fork]
let set1 = Set.fromList x

在定义时

data Cutlery = Knife | Fork deriving (Show,Ord,Eq)

解决了这个问题,但没有意义.Data.Set是否与集合的数学定义不同？

Answer 1

A Data.Set捕获集合的数学抽象,但它不相同.主要区别在于a Data.Set要求对其元素进行排序,而数学集只要求其元素在相等性方面具有可比性.

要求的原因Ord是效率.通过定义构建集合抽象是完全可能的

data Set a = Set [a]

即在引擎盖下它只是一个列表,我们确保我们永远不会插入重复的元素.在elem和insert操作将是

elem a (Set as) = any (a ==) as

insert a (Set as) | a `elem` as = Set as
                  | otherwise   = Set (a:as)

然而,这意味着,elem和insert为O(ñ)操作.如果我们想要做得比这更好,标准方法是

1. 将元素存储在平衡的二叉树中(需要一个Ord实例)
2. 散列元素并将它们存储在一个数组中(需要一个Hashable实例).

TreeSet中

作者选择的实现Data.Set是使用二叉树,您可以通过转到源来查看.实施或多或少

data Set a = Bin a (Set a) (Set a)
           | Tip

现在您可以将elem函数编写为

elem :: Ord a => a -> Set a -> Bool
elem = go
  where
    go _  Tip = False
    go x (Bin y l r) = case compare x y of
      LT -> go x l
      GT -> go x r
      EQ -> True

这是一个O(log n)操作,而不是O(n).插入比较棘手(因为你需要保持树平衡)但类似.

HashSet的

在哈希集中,在插入和删除元素时不直接比较元素.相反,每个元素都被散列为整数,并存储在基于该整数的位置.

从理论上讲,这不需要Ord实例.在实践中,您需要一些方法来跟踪散列到相同值的多个元素,开发人员选择的方法Data.HashSet是将多个元素存储在常规中Data.Set,因此事实证明您确实需要Ord实例!

data HashSet a = HashSet (Data.IntMap.IntMap (Data.Set.Set a))

它原本可以写成

data HashSet a = HashSet (Data.IntMap.IntMap [a])

相反,Ord如果存在许多具有相同值的元素,则以某种低效率为代价来消除需求.

Answer 2

是Data.Set不是比一组的数学定义？

显然,数学集可以是无数的 - 你无法用计算机,甚至图灵机来表示这一点.

但您要寻找的答案是:Data.Set基于二叉树的数据类型,需要元素的总线性顺序,以了解是否放置并稍后在节点的左侧或右侧子树上找到某些内容.因此,虽然可以在没有Ord约束的情况下实现set数据类型,但这种特殊的,更有效的实现不会.