Why is this solution to the queen's dilemma so much slower than in Haskell?

Question

In my computer science class, we used Haskell to solve the "queens" problem, in which you should find all the possible placements for the n queens on the nxn board. This was the code that gave us:

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 changed the order in solution k and found that it still gave the 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 is this second version taking so much longer? My thought process is that the second version of recursion is at each step, while the first version of recursion is only once, and then back. This is not a homework problem, I am just curious, and I feel that it will help me better understand the language.

Answer 1

,

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

f 42 , x n 1 100.

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

n 1 100, f 42. , f 100 .

, :

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
      ...

, , , (100, ) .

f 42 , , :

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

, xs , . , xs n=1, n.

Answer 2

, , (. " " Wikipedia).

, , , .

!

, Haskell .

, , :

COST CENTRE          MODULE                  no.     entries  %time %alloc   %time %alloc

MAIN                 MAIN                     44           0    0.0    0.0   100.0  100.0
 main                Main                     89           0    0.3    0.0     0.3    0.0
 CAF                 Main                     87           0    0.0    0.0    99.7  100.0
  main               Main                     88           1    0.2    0.6    99.7  100.0
   queens2           Main                     94           1    0.0    0.0    55.6   48.2
    queens2.solve    Main                     95          13    3.2    0.8    55.6   48.2
     queens2.safe    Main                     96    10103868   42.1   47.5    52.3   47.5
      queens2.checks Main                    100    37512342   10.2    0.0    10.2    0.0
   queens1           Main                     90           1    0.0    0.0    43.9   51.1
    queens1.solve    Main                     91          13    2.0    1.6    43.9   51.1
     queens1.safe    Main                     92    10103868   29.3   49.5    41.9   49.5
      queens1.checks Main                     93    37512342   12.7    0.0    12.7    0.0

, .

:

, ( ):

Answer 3

, , ( - . GHC!). : , ; ,

loop x = case x of { 0 -> someDefault; _ -> do1 (loop (x-1)) }

, , , do1 , ( , do1 ). , - . -, , , :

guard b = if b then [()] else [] 

solve_good k = 
          concatMap (\partial -> 
          concatMap (\h -> 
          guard (safe h partial) >> return (h:partial)
           ) [0..n-1]
           ) (solve $ k-1)

solve_bad k = 
          concatMap (\h -> 
          concatMap (\partial -> 
          guard (safe h partial) >> return (h:partial)
           ) (solve $ k-1)
           ) [0..n-1]

- Haskell, <- concatMap, guard s. , - solve_good , concatMap . , solve_bad concatMap, , () [0..n-1]. , solve $ k-1 concatMap - , concatMap ( h), , h ( solve_good).