Potrzebujesz pomocy w zrozumieniu leniwego zachowania ewaluacyjnego Haskella

Question

Napisałem dwie wersje problemu nasek i myślę, że powinny one mieć podobną wydajność, ale tak nie jest. Myślę, że wynika to z leniwego zachowania ewaluacyjnego Haskella. Może ktoś proszę wyjaśnić, jak to działa na poniższym przykładzie

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) 

można je ocenić przez wywołanie nqueens1 8 8 8 8 lub nqueens2 ocenić go na płytce o wymiarach 8.

Podczas nqueens2 działa całkiem skutecznie nqueens1 ma problemy z wydajnością. Wierzę, że jest tak, ponieważ wywołanie rekursywne (nqueens n (k-1)) jest oceniane wielokrotnie. Z mojego zrozumienia lenistwa Haskella wynika, że ​​tak nie powinno być.

Proszę mi pomóc w zrozumieniu tego problemu.

Z góry dziękuję.

Answer 1

Tak, rekursywne połączenie jest oceniane wiele razy. W szczególności jest on oceniany raz dla każdej wartości dla i.

Jeśli chcesz tego uniknąć, można zmienić generatorów, tak że q <- część pochodzi przed i <- części:

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

Jednak będzie to zmienić kolejność wyników. Jeśli to nie do przyjęcia, można użyć let obliczyć wynik rekurencyjnego wywołania raz, a następnie używać go tak:

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