Necesito ayuda para comprender el comportamiento de evaluación de pereza de Haskell

Question

He escrito dos versiones del problema de nqueens y creo que deberían tener una eficacia similar, pero no es así. Creo que se debe al comportamiento de evaluación perezosa de Haskell. Por favor alguien puede explicar cómo funciona para el siguiente ejemplo,

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) 

poder evaluarlas llamando nqueens1 8 8 8 8 o nqueens2 de evaluarlo para un tablero de tamaño 8.

Mientras nqueens2 funciona bastante eficientemente nqueens1 tiene problemas de rendimiento. Creo que es porque la llamada recursiva (nqueens n (k-1)) se está evaluando varias veces. Desde mi comprensión de la evaluación perezosa de Haskells, este no debería ser el caso.

Ayúdeme a comprender este comportamiento.

Gracias de antemano.

Answer 1

Sí, la llamada recursiva se evalúa varias veces. Específicamente, se evalúa una vez para cada valor de i.

Si desea evitar esto, puede reorganizar los generadores de forma que la parte q <- viene antes de la parte i <-:

[ i:q | q <- nqueens2 n (k - 1), i <- [1..n], isSafe i q k] 

Sin embargo, esto va a cambiar el orden de los resultados. Si eso no es aceptable, se puede utilizar let para calcular el resultado de la llamada recursiva de una vez y luego usarlo como esto:

[ i:q | let rec = nqueens2 n (k - 1), i <- [1..n], q <- rec, isSafe i q k]