하스켈에서 Sets를 구성하기에 WHNF에 대한 키를 평가하는 이유는 무엇입니까?

Question

Haskell's Data.Set page는 말한다 :

키 인수가 WHNF

는 "엄격 성 속성"섹션에서

로 평가됩니다.

그러나 WHNF가 Sets를 만드는 데 충분한 이유가 궁금합니다. 예를 들어, Set [Int]의 인스턴스를 생성하려면 Ins List의 요소를 깊이있게 비교하여 비교해야합니다.

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 

는 심지어 다른 요소를 삽입 이미 첫 번째 요소를 살펴볼 때 구분할 수 있기 때문에 목록의 두 번째 요소를 완전히 평가하지는 않습니다.

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-heap-view 출력을 ghc-vis 그래프로 바꾸려면 다음과 같이하십시오 .-)).

Answer 2

평등이나 순서를 결정하기 위해 포함 된 모든 것을 평가할 필요가없는 키로 사용할 수있는 데이터 형식이있을 수 있습니다. 물론 목록은 그러한 유형이 아닙니다.

그러나 목록은 평등을 찾기 위해 완전히 평가되어야하지만 평등을 찾으려면 필요하지 않습니다. 즉, 우리는 그것을 기대하지 않을 것입니다.

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

영원히 계산합니다. 마찬가지로

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

여기서 두 번째 목록의 WHNF를 얻으면 첫 번째 것과 같지 않다는 것을 알면됩니다. 40+2을 계산하는 데 신경 쓸 필요가 없습니다.