Why does this solution to the "queens" dilemma run so much slower than the other in Haskell?

Question

In my computer science class we were using Haskell to solve the "queens" problem in which you must find all possible placements of n queens in an nxn board. This was the code we were given:

queens n = solve n
    where
        solve 0 = [ [] ]
        solve k = [ h:partial | partial <- solve(k-1), h <- [0..(n-1)], safe h partial ]
        safe h partial = and [ not (checks h partial i) | i <- [0..(length partial)-1] ]
        checks h partial i = h == partial!!i || abs(h-partial!!i) == i+1

However, the first time I entered it I accidentally swapped the order in solve k and found that it still gave a correct solution but took much longer:

queens n = solve n
where
    solve 0 = [ [] ]
    solve k = [ h:partial | h <- [0..(n-1)], partial <- solve(k-1), safe h partial ]
    safe h partial = and [ not (checks h partial i) | i <- [0..(length partial)-1] ]
    checks h partial i = h == partial!!i || abs(h-partial!!i) == i+1

Why does this second version take so much longer? My thought process is that the second version does recursion at every step while the first version does recursion only once and then backtracks. This is not for a homework problem, I'm just curious and feel like it will help me better understand the language.

Answer 1

Simply put,

[ ... | x <- f 42, n <- [1..100] ]

will evaluate f 42 once to a list, and for each element x in such list it will generate all ns from 1 to 100. Instead,

[ ... | n <- [1..100], x <- f 42 ]

will first generate an n from 1 to 100, and for each of them call f 42. So f is now being called 100 times instead of one.

This is no different from what happens in imperative programming when using nested loops:

for x in f(42):    # calls f once
   for n in range(1,100): 
      ...
for n in range(1,100): 
   for x in f(42): # calls f 100 times
      ...

The fact that your algorithm is recursive makes this swap particularly expensive, since the additional cost factor (100, above) accumulates at each recursive call.

You can also try to bind the result of f 42 to some variable so that it does not need to be recomputed, even if you nest it the other way around:

[ ... | let xs = f 42, n <- [1..100], x <- xs ]

Note that this will keep the whole xs list in memory for the whole loop, preventing it from being garbage collected. Indeed, xs will be fully evaluated for n=1, and then reused for higher values of n.