Ho bisogno di aiuto per comprendere il comportamento di valutazione pigro di Haskell

Question

Ho scritto due versioni del problema di nqueens e penso che dovrebbero avere un'efficienza simile ma non è così. Penso che sia dovuto al comportamento di valutazione pigro di Haskell. Qualcuno può spiegare come funziona per il seguente esempio,

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) 

Si possono valutare chiamando nqueens1 8 8 8 8 o nqueens2 per valutare per un consiglio di formato 8.

Mentre nqueens2 funziona abbastanza efficientemente nqueens1 ha problemi di prestazioni. Credo che sia perché la chiamata ricorsiva (nqueens n (k-1)) viene valutata più volte. Dalla mia comprensione della valutazione pigra di Haskells non dovrebbe essere così.

Per favore aiutami a capire questo comportamento.

Grazie in anticipo.

Answer 1

Sì, la chiamata ricorsiva viene valutata più volte. Nello specifico viene valutato una volta per ciascun valore per i.

Se si vuole evitare questo, è possibile riorganizzare i generatori in modo che la parte q <- viene prima della parte i <-:

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

Tuttavia, questo cambierà l'ordine dei risultati. Se questo non è accettabile, è possibile utilizzare let per calcolare il risultato della chiamata ricorsiva una volta e poi usare in questo modo:

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