Dlaczego ocena kluczy do WHNF jest wystarczająca do skonstruowania Zestawy w Haskell?

Question

Haskell's Data.Set page mówi:

Główne argumenty są oceniane na WHNF

w sekcji "Właściwości surowości".

Zastanawiam się jednak, dlaczego WHNF wystarcza do stworzenia zestawów. Na przykład, aby skonstruować instancję Set [Int], musimy dokładnie ocenić jej elementy List Ints, aby je porównać.

Answer 1

Aby rozwinąć komentarz @ chi: Oznacza to tylko, że klucze są co najmniej oceniane na WHNF. Często można je oceniać zawsze, gdy są porównywane, ale nie zawsze. Załóżmy wywołać ghc-heap-view i spojrzeć na kilka przykładów:

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 nie w pełni ocenić jego argumentu (the _bco jest 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 

Nawet wkładając kolejny element nie oceni w pełni pozostałych elementów na liście, ponieważ można je już rozróżnić, patrząc na pierwszy element:

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 

Ale wstawienie t2 znowu będzie teraz zmusić drugi element tej listy:

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 

Więc nie można polegać na Data.Set ocenić klawiszy w pełni, jak je przechowywać. Jeśli chcesz, musisz użyć na przykład (singleton $!! t1) i (insert $!! t2).

(Jeśli ktoś chce zamienić dane wyjściowe ghc-heap-view w tej odpowiedzi na wykresy ghc-vis, możesz to zrobić :-)).

Answer 2

Mogą istnieć typy danych, które można wykorzystać jako klucze, które nie muszą oceniać wszystkiego, co zawierają, w celu ustalenia równości lub kolejności. Listy oczywiście nie są tego typu.

Jednakże, mimo że listy muszą być w pełni ocenione, aby znaleźć równość, nie muszą być konieczne, aby znaleźć nierówność. Oznacza to, że nie spodziewamy się, że obliczymy na zawsze. Podobnie z

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

Tutaj wystarczy uzyskać WHNF z drugiej listy, aby znaleźć, że nie jest równa pierwszej. Nie musimy zawracać sobie głowy obliczaniem 40+2, a tym bardziej elementów następnych.