ハスケルの遅延評価動作の理解に役立つ

Question

問題の2つのバージョンを書いていますが、それらは同様の効率を持つべきだと思いますが、そうではありません。私はそれがハスケルの怠惰な評価行動に起因すると思う。誰かがあなたがnqueens2はかなり動作しますがサイズ8

のボードのためにそれを評価するためにnqueens1 8 8またはnqueens2 8 8を呼び出すことによって、それらを評価することができ

、それは次の例のためにどのように動作するか

nqueens1 n 1 = [[i] | i <- [1..n]] 
nqueens1 n k = [ i:q | i <- [1..n], q <- (nqueens1 n (k - 1)), isSafe i q k] 

isSafe i q n = isSafeHelper i (zip q [(n-1),(n-2)..1]) 
     where isSafeHelper i [] = True 
       isSafeHelper i (x:xs) = (i /= fst x) && abs(i - (fst x)) /= abs(n - (snd x)) && 
             isSafeHelper i xs 
nqueens2 n 1 = [[i] | i <- [1..n]] 
nqueens2 n k = [ i:q | i <- [1..n], q <- boards, isSafe i q k] 
      where boards = nqueens2 n (k-1) 

を説明していただけます効率的にnqueens1にパフォーマンスの問題があります。再帰呼び出し（nqueens n（k-1））が複数回評価されているためです。 Haskellの遅延評価の私の理解から、これは当てはまりません。

この現象を理解するのを手伝ってください。

ありがとうございます。

Answer 1

はい、再帰呼び出しは複数回評価されます。具体的には、iの値ごとに1回評価されます。

あなたがこれを避けたい場合はq <-部分がi <-一部の前に来るように、あなたは発電機を並べ替えることができます。

[ i:q | q <- nqueens2 n (k - 1), i <- [1..n], isSafe i q k] 

しかしこれは、結果の順序を変更します。それが受け入れられないなら、あなたは一度、再帰呼び出しの結果を計算し、このようにそれを使用するためにletを使用することができます。

[ i:q | let rec = nqueens2 n (k - 1), i <- [1..n], q <- rec, isSafe i q k]