需要帮助来理解 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））被多次评估。根据我对哈斯克尔懒惰评估的理解，情况不应该如此。

请帮助我理解这种行为。

提前谢谢。

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]