haskell - 需要帮助理解 Haskell 的惰性求值行为

Question

我已经编写了两个版本的 nqueens 问题，我认为它们应该具有相似的效率，但事实并非如此。我认为这是由于 Haskell 的懒惰评估行为。有人可以解释一下它在以下示例中的工作原理吗，

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)) 被多次评估。根据我对 Haskells 懒惰评估的理解，情况并非如此。

请帮助我理解这种行为。

提前致谢。

Answer 1

是的，递归调用被多次评估。具体来说，它对 i 的每个值进行一次评估。 .

如果您想避免这种情况，您可以重新排列生成器，以便 q <-部分位于 i <- 之前部分:

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

但是，这将改变结果的顺序。如果这 Not Acceptable ，您可以使用 let计算一次递归调用的结果，然后像这样使用它:

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