CODEWITHSUNDEEP
haskelllazy-evaluation
prasannak
prasannak

Reputation: 493

Need help in understanding the lazy evaluation behavior of Haskell

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.

Upvotes: 7

Views: 255

Answers (1)

sepp2k
sepp2k

Reputation: 370102

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]

Upvotes: 10

Related Questions