为什么评估 WHNF 的密钥足以在 Haskell 中构造集合？

Question

Key arguments are evaluated to WHNF

在其 "Strictness properties" 部分。

但是，我想知道为什么WHNF足以构造集合。例如，要构造 Set [Int] 的实例，我们必须深入评估其 Ints 列表的元素以比较它们。

Answer 1

扩展@chi 的评论：这只意味着密钥至少被评估为 WHNF。通常，一旦对它们进行比较，它们可能总是会被评估，但并非总是如此。让我们调用 ghc-heap-view 并看几个例子：

预赛：

~ $ ghci
GHCi, version 8.0.1: http://www.haskell.org/ghc/  :? for help
Prelude> :script /home/jojo/.cabal/share/x86_64-linux-ghc-8.0.1/ghc-heap-view-0.5.7/ghci
Prelude> import qualified Data.Set as S

singleton 没有完全评估它的论点（_bco 是一个 thunk）：

Prelude S> let t = [True, True && True] -- a thunk in a list
Prelude S> let s1 = S.singleton t
Prelude S> s1 `seq` ()
()
Prelude S> :printHeap s1
let x1 = True()
    x2 = Tip()
in Bin [x1,(_bco _fun)()] x2 x2 1

即使插入另一个元素也不会完全评估列表中的第二个元素，因为通过查看第一个元素已经可以区分它们:

Prelude S> let t2 = [False, False && False] -- a thunk in another  list
Prelude S> let s2 = S.insert t2 s1
Prelude S> s2 `seq` ()
()
Prelude S> :printHeap s2
let x1 = True()
    x2 = toArray (0 words) 
    f1 = _fun
    x3 = []
    x4 = False()
    x5 = Tip()
in Bin (x1 : (_bco f1)() : x3) (Bin (x4 : (_bco f1)() : x3) x5 x5 1) x5 2

但是再次插入 t2 现在将强制该列表的第二个元素：

Prelude S> let s3 = S.insert t2 s2
Prelude S> s3 `seq` ()
()
Prelude S> :printHeap s3
let x1 = True()
    x2 = []
    x3 = False()
    x4 = Tip()
in Bin (x1 : (_bco _fun)() : x2) (Bin (x3 : _bh x3 : x2) x4 x4 1) x4 2

因此您不能依赖 Data.Set 在存储密钥时对其进行全面评估。如果需要，您需要使用 (singleton $!! t1) 和 (insert $!! t2).

（如果有人想用 ghc-vis 图表替换此答案中的 ghc-heap-view 输出，请随意这样做:-)）。

Answer 2

可能有一些数据类型可用作不需要评估它们包含的所有内容来确定相等性或顺序的键。当然，列表不是这样的类型。

然而，虽然必须对列表进行全面评估才能找到相等性，但它们不一定需要为了找到 non-equality。也就是说，我们不希望

[1..] == [2..]

永远计算。同样

[] == [(40+2)..]

这里拿到第二个列表的WHNF就可以发现它不等于第一个了。我们不需要计算 40+2，更不用说后续元素了。

为什么评估 WHNF 的密钥足以在 Haskell 中构造集合？

Why is evaluating keys to WHNFs enough to construct Sets in Haskell?

haskell

lazy-evaluation

data-structures