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.