하스켈의 게으른 평가 동작을 이해하는 데 도움이 필요합니다

Question

두 가지 버전의 문제가 생겼습니다. 비슷한 효율성을 가져야한다고 생각합니다. 그렇지만 그렇지 않습니다. 나는 그것이 하스켈의 게으른 평가 행동 때문이라고 생각한다. 그것은 다음과 같은 예를 들어 어떻게 작동하는지 사람이 꽤 작동 nqueens2 동안 크기 8

의 보드를 평가하기 위해 nqueens1 8 8 8 8 nqueens2를 호출하여

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))이 여러 번 평가되기 때문입니다. 하스켈의 게으른 평가에 대한 나의 이해에서 보면, 그렇게해서는 안된다.

이 동작을 이해하는 데 도움을주십시오. 사전에

감사합니다.

Answer 1

예, 재귀 호출은 여러 번 평가됩니다. 특히 i에 대한 각 값에 대해 한 번 평가됩니다. 당신이 피하고 싶은 경우 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]