Cần giúp đỡ trong việc hiểu hành vi đánh giá lười biếng của Haskell

Question

Tôi đã viết hai phiên bản của vấn đề nqueens và tôi nghĩ rằng họ nên có hiệu quả tương tự nhưng nó không phải như vậy. Tôi nghĩ rằng đó là do hành vi đánh giá lười biếng của Haskell. Có thể ai đó xin vui lòng giải thích cách hoạt động cho các ví dụ sau,

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) 

Bạn có thể đánh giá chúng bằng cách gọi nqueens1 8 8 hoặc nqueens2 8 8 để đánh giá nó cho một hội đồng quản trị kích thước 8.

Trong khi nqueens2 hoạt động khá hiệu quả nqueens1 có vấn đề hiệu suất. Tôi tin rằng đó là bởi vì các cuộc gọi đệ quy (nqueens n (k-1)) đang được đánh giá nhiều lần. Từ sự hiểu biết của tôi về đánh giá lười biếng Haskells này không phải là trường hợp.

Hãy giúp tôi hiểu rõ hành vi này.

Xin cảm ơn trước.

Answer 1

Có, cuộc gọi đệ quy được đánh giá nhiều lần. Cụ thể, nó được đánh giá một lần cho mỗi giá trị cho i.

Nếu bạn muốn tránh điều này, bạn có thể sắp xếp lại các máy phát điện để các phần q <- đến trước phần i <-:

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

Tuy nhiên điều này sẽ thay đổi thứ tự của các kết quả. Nếu đó là không thể chấp nhận, bạn có thể sử dụng let để tính toán kết quả của các cuộc gọi đệ quy một lần và sau đó sử dụng nó như thế này:

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