为什么Haskell的Data.Set不支持无限集？

Question

在以下代码段中:

import qualified Data.Set as Set

data Nat = Zero | Succ Nat deriving (Eq, Show, Ord)

instance Enum Nat where
  pred (Succ x)     = x
  succ x            = Succ x
  toEnum 0          = Zero
  toEnum x          = Succ (toEnum (x-1))
  fromEnum Zero     = 0
  fromEnum (Succ x) = 1 + (fromEnum x)

nats :: [Nat]
nats = [Zero ..]

natSet :: Set.Set Nat
natSet = Set.fromList nats

为什么:

• elem (toEnum 100) nats == True

但

• Set.member (toEnum 100) natSet 永远不会结束？

Answer 1

现有的答案已经足够,但我想对Sets 的行为进行一点阐述.

看起来你希望有一套懒惰Nat的东西; 你获取所有Nats 的无限列表并使用Set.toList它.那样就好了; 数学家经常谈论"所有自然数的集合".问题是实施Set不像列表那样适应懒惰.

Set的实现基于大小平衡的二叉树(或有界平衡树)

Data.Set的文档

假设您希望从列表中懒惰地构造二叉树.当需要对树进行更深的遍历时,列表中的元素将仅插入到树中.那么你问一下100是否在树上.它会在树上添加1-99号,一次一个.然后它最终将100添加到树中,并发现100确实是树中的元素.但请注意我们做了什么.我们刚刚执行了懒惰列表的有序遍历!所以第一次,我们的虚构LazyTree.contains将具有大致相同的复杂度List.find(假设一个转换的O(1)插入,这对于简单的二叉树来说是一个坏假设,它具有O(log n)复杂度).如果没有平衡,我们的树就会非常不平衡(我们按顺序添加数字1到100,所以它只是每个分支的正确子项下的一个大链表).但是在遍历期间通过树平衡,很难知道再次开始遍历的位置; 至少它肯定不会立即直观.

tl;博士:没人(afaik)已经做了一个很好的懒人套装.因此,无限集合现在更容易表示为无限列表.

Answer 2

Set.fromList不是懒惰,所以如果你把它传递给无限列表它就不会结束.但是natSet在需要之前不会构建,因此当你Set.member在它上面运行时你只会注意到它.

例如,即使Set.null $ Set.fromList [0..]不终止.