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.

"Lazy evaluation" is about evaluating things late -- not about avoiding evaluating something many times. — Daniel Wagner
@DanielWagner Actually the difference between lazy evaluation and call-by-name is exactly that certain expressions that would be evaluated multiple times using call-by-name are only evaluated once using lazy evaluation. That's not related to the problem here though. — sepp2k
@sepp2k You're right, I should have been more precise, either by saying "call-by-name" instead of "lazy evaluation" or by saying "memoization" instead of "avoiding evaluating something many times". — Daniel Wagner
Note, for what it's worth that ghc with -O2 seems to see through the difference. — applicative

sepp2k sepp2k · Accepted Answer · 2012-07-01T13:35:57

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]

Need help in understanding the lazy evaluation behavior of Haskell

1 Answers