需要帮助来理解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]

但是,这将改变结果的顺序.如果这是不可接受的,您可以使用let一次计算递归调用的结果,然后像这样使用它:

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