Need help in understanding the lazy evaluation behavior of Haskell

Question

I have written two version of nqueens problem and I think they should have similar efficiency but it is not so. I think that it is due to lazy evaluation behavior of Haskell. Can someone please explain how it works for the following example,

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)

You can evaluate them by calling nqueens1 8 8 or nqueens2 8 8 to evaluate it for a board of size 8.

While nqueens2 works quite efficiently nqueens1 has performance issues. I believe it is because the recursive call (nqueens n (k-1)) is being evaluated multiple times. From my understanding of Haskells lazy evaluation this should not be the case.

Please help me in understanding this behavior.

Thanks in advance.

Answer 1

Yes, the recursive call is evaluated multiple times. Specifically it is evaluated once for each value for i.

If you want to avoid this, you can rearrange the generators so that the q <- part comes before the i <- part:

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

However this will change the order of the results. If that's not acceptable, you can use let to calculate the result of the recursive call once and then use it like this:

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