HaskellでSetを構築するのに十分なWHNFキーを評価するのはなぜですか？

Question

Haskell's Data.Set page言う：

キーの引数は、その "正格のプロパティ" セクションでWHNF

に評価されます。

しかし、なぜWHNFがセットを構築するのに十分であるのだろうか。たとえば、Set [Int]のインスタンスを作成するには、Ints Listsの要素を深く評価して比較する必要があります。

Answer 1

@ chiのコメントで拡張する：これは、少なくともキーがWHNFに評価されていることを意味します。多くの場合、比較されると常に評価されることがありますが、必ずしもそうとは限りません。さんはghc-heap-viewを起動し、いくつかの例を見てみましょう：

Prelimaries：

~ $ 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がサンクである）その引数を評価しません：

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 

とにも別の要素を挿入します彼らは最初の要素を見て、すでに区別できるように完全に、リストの2番目の要素を評価しません。

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を挿入することは、今、そのリストの2番目の要素を強制します：あなたがそれらを保存するよう

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-heap-view出力をghc-visグラフで置き換えたい場合は、気軽に:-)）。

Answer 2

等価性や秩序を判定するために含まれているすべてを評価する必要のないキーとして使用できるデータ型があります。もちろん、リストはそのようなタイプではありません。

しかし、リストは完全性を見つけるために完全に評価されなければならないが、非等価性を見つけるためにリストを必要とするわけではない。つまり、我々はそれを期待しません。

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

永遠に計算します。同様に

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

ここで、第2のリストのWHNFを取得すれば、第1のリストと同じでないことが分かります。 40+2を計算するのは面倒でなくても、後続の要素ははるかに少なくなります。