需要帮助了解Haskell的懒惰评估行为

Question

我已经写了两个版本的nqueens问题，我认为它们应该有相似的效率，但事实并非如此。我认为这是由于哈斯克尔的懒惰评估行为。有人能解释一下下面的例子是如何工作的吗，

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 8 8或nqueens2 8 8对其进行评估，以对大小为8的板进行评估。

虽然nqueens2工作效率很高，但nqueens1存在性能问题。我相信这是因为递归调用（nqueens n（k-1））被多次评估。根据我对Haskell懒惰评估的理解，情况不应该是这样。

请帮助我理解这种行为。

提前谢谢。

Answer 1

是的，递归调用会被计算多次。具体而言，对于i的每个值，都会对其进行一次评估。

如果您想避免这种情况，您可以重新排列生成器，以便q

[ 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]