Lista Haskella Zrozumienie i wyciek przestrzeni - haskell, wycieki pamięci, zrozumienie list, monady, leniwa ocena

Próbuję dowiedzieć się, jak rekursja w połączeniu z operacjami List Comprehension / Monadic powoduje wycieki przestrzeni.

Mam mały program testowy:

module Main where
permute :: [a] -> Integer -> [[a]]
permute _ 0 = [[]]
permute xs" n = [x:xs | x <- xs", xs <- permute xs" (n-1)]
chars1 = ["0".."9"]
main = do
putStrLn $ (permute chars1 10000)!!100000000 -- Leaks
print $ [1..]!!100000000 -- Does not leak

Teraz rozumiem, że funkcja permute można rozszerzyć jako

xs" >>= x -> (permute xs" (n-1) >>= xs -> (x:xs))

Tak dużo (permute xs" n) zostanie ułożone przed uzyskaniem wyniku. Czy rozumiem poprawnie? Jeśli tak, co mogę zrobić, aby upewnić się, że funkcja nie wycieka?

Odpowiedzi:

Ten kod jest trochę dziwny, ponieważ permute nie robi ... cóż .. rzeczy permutowanych, ale zakładając, że to jest to, co zamierzałeś, że faktycznie działa tak samo, jak twoje [0..] !! 10000 przykład, po prostu obliczenie 10000-go wyboru jest o wiele więcej pracy w kodzie!

Ważne jest to, że twój kod jest leniwy, możemy łatwo obliczyć pierwszy element permute [0..] 10 nawet jeśli jest ich wyraźnie nieskończenie wiele.

Możesz jednak myśleć o tym, że kiedy to uruchomisz, wyprodukowanie tego zajmuje naprawdę dużo czasu każdy wyjście nawet jeśli możesz mieć nadzieję, że takwyprodukować 1. postać ... poczekać trochę .. wyprodukować drugą postać .. trochę poczekać .. i tak dalej. To nie jest tak naprawdę „przeciek” w sensie Haskella i nie można go uniknąć w tym scenariuszu. Twoja lista jest zasadniczo zbudowana z

map ("0":) (permute chars (n - 1)) ++ ... ++ map ("9":) (permute chars (n - 1))

Problem polega na tym, że aby poznać pierwszy znak, musisz dowiedzieć się, z którego „bloku” będziesz wybierać, co obejmuje obliczanie długości bloku, co obejmuje ocenę permute chars (n - 1) całkowicie. Więc co się stanie, wymusisz kolejno każde wywołanie rekurencyjne, dopóki na liście wynikowej nie będzie wystarczającej liczby elementów do oceny wywołania !!. Nie jest to jednak niespodziewane. Możesz jednak znacznie przyspieszyć ten kod za pomocą jednego dość prostego triku: odwróć x i xs w zrozumieniu listy.

permute :: [a] -> Integer -> [[a]]
permute _ 0 = [[]]
permute xs" n = [x:xs | xs <- permute xs" (n-1), x <- xs"]

Zauważ, że zwiększone udostępnianie może być wteoria prowadzi do zwiększenia wykorzystania pamięci (coś może nie być GCedem w tej wersji), ale nie jestem w stanie wymyślić nie absurdalnie wymyślonego programu, który to robi.