Brauchen Sie Hilfe beim Verständnis der faulen Bewertung Verhalten von Haskell

Question

Ich habe zwei Version von NQUEENS Problem geschrieben und ich denke, sie sollten ähnliche Effizienz haben, aber es ist nicht so. Ich denke, dass es wegen des faulen Bewertungsverhaltens von Haskell ist. Kann jemand bitte erklären, wie es für das folgende Beispiel funktioniert,

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) 

Sie sie 8 durch den Aufruf nqueens1 8 8 oder nqueens2 8 auswerten kann es für eine Platte der Größe arbeitet 8.

Während nqueens2 zu bewerten recht effizient nqueens1 hat Leistungsprobleme. Ich glaube, das liegt daran, dass der rekursive Aufruf (nqueens n (k-1)) mehrfach ausgewertet wird. Nach meinem Verständnis von Haskells fauler Bewertung sollte dies nicht der Fall sein.

Bitte helfen Sie mir, dieses Verhalten zu verstehen.

Vielen Dank im Voraus.

Answer 1

Ja, der rekursive Aufruf wird mehrfach ausgewertet. Speziell wird es einmal für jeden Wert für i ausgewertet.

Wenn Sie dies vermeiden wollen, können Sie die Generatoren neu anordnen, so dass der q <- Teil vor dem i <- Teil kommt:

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

Dies wird jedoch die Reihenfolge der Ergebnisse ändern. Wenn das nicht akzeptabel ist, können Sie let verwenden das Ergebnis des rekursiven Aufrufs einmal zu berechnen und sie dann wie folgt verwenden:

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