Lenistwo i rekurencja ogona w Haskell, dlaczego to się zawiesza?

Question

mam tego dość prostą funkcję, aby obliczyć średnią z elementów dużego listy, przy użyciu dwóch akumulatorów do przechowywania sumę dotychczas i liczyć do tej pory:

mean = go 0 0 
    where 
     go s l []  = s/fromIntegral l 
     go s l (x:xs) = go (s+x) (l+1) xs 

main = do 
    putStrLn (show (mean [0..10000000])) 

Teraz w ścisłym języku, byłoby być rekursywnym rekwizytem i nie byłoby problemu. Jednakże, jak Haskell jest leniwy, moje googlowanie doprowadziło mnie do zrozumienia, że ​​(s + x) i (l + 1) zostaną przekazane w rekurencji jako strzały. Więc cała ta sprawa i wywala oparzenia:

Stack space overflow: current size 8388608 bytes. 

Po dalszym googlowania znalazłem seq i $!. Co wydaje mi się, że nie rozumiem, ponieważ wszystkie moje próby wykorzystania ich w tym kontekście okazały się daremne, a komunikaty o błędach mówią coś o nieskończonych typach.

Wreszcie znalazłem -XBangPatterns, który rozwiązuje to wszystko przez zmianę wywołanie rekurencyjne:

go !s !l (x:xs) = go (s+x) (l+1) xs 

Ale nie jestem zadowolony z tego, jak -XBangPatterns jest obecnie rozszerzenie. Chciałbym wiedzieć, jak dokonać oceny ścisłej bez korzystania z -XBangPatterns. (! A może nauczyć się czegoś zbyt)

Wystarczy więc zrozumieć mój brak zrozumienia, oto co próbowałem (starając się, że skompilowany tylko, że jest):

go s l (x:xs) = go (seq s (s+x)) (seq l (l+1)) xs 

Z tego co rozumiem, nast powinien tu wymusić ocenę argumentów s i l, unikając w ten sposób problemu spowodowanego przez tony. Ale wciąż dostaję przepełnienie stosu.

Answer 1

pisałem obszernie na ten temat:

• Real World Haskell, ch 24: controlling evaluation
• On recursion and strictness in Haskell

Po pierwsze, tak, jeśli chcesz, aby szczegółową ocenę akumulatory używać seq i pobyt w Haskell 98 :

mean = go 0 0 
    where 
    go s l []  = s/fromIntegral l 
    go s l (x:xs) = s `seq` l `seq` 
         go (s+x) (l+1) xs 

main = print $ mean [0..10000000] 

*Main> main 
5000000.0 

Po drugie: surowość analiza rozpocznie się, jeśli dać pewne adnotacje typu, i skompilować z -O2:

mean :: [Double] -> Double 
mean = go 0 0 
where 
    go :: Double -> Int -> [Double] -> Double 
    go s l []  = s/fromIntegral l 
    go s l (x:xs) = go (s+x) (l+1) xs 

main = print $ mean [0..10000000] 

$ ghc -O2 --make A.hs 
[1 of 1] Compiling Main    (A.hs, A.o) 
Linking A ... 

$ time ./A 
5000000.0 
./A 0.46s user 0.01s system 99% cpu 0.470 total 

ponieważ „Pokój” jest opakowaniem nad ścisłym typu atomowy Podwójne #, z optymalizacje na i precyzyjny typ, GHC przeprowadza analizę ścisłości i stwierdza, że ​​ścisła wersja będzie w porządku.

import Data.Array.Vector 

main = print (mean (enumFromToFracU 1 10000000)) 

data Pair = Pair !Int !Double 

mean :: UArr Double -> Double 
mean xs = s/fromIntegral n 
    where 
    Pair n s  = foldlU k (Pair 0 0) xs 
    k (Pair n s) x = Pair (n+1) (s+x) 

$ ghc -O2 --make A.hs -funbox-strict-fields 
[1 of 1] Compiling Main    (A.hs, A.o) 
Linking A ... 

$ time ./A 
5000000.5 
./A 0.03s user 0.00s system 96% cpu 0.038 total 

Zgodnie z opisem w rozdziale RWH powyżej.

Answer 2

Masz rację, rozumiejąc, że seq s (s+x) wymusza ocenę s. Ale to nie wymusza s+x, dlatego nadal budujesz uderzenia.

Za pomocą $! można wymusić ocenę dodawania (dwa razy, dla obu argumentów).W ten sposób uzyskuje się ten sam efekt za pomocą wzorów huk:

mean = go 0 0 
where 
    go s l []  = s/fromIntegral l 
    go s l (x:xs) = ((go $! s+x) $! l+1) xs 

---

Zastosowanie funkcji $! przesunie go $! (s+x) do równowartości:

let y = s+x 
in seq y (go y) 

Zatem y jest najpierw zmuszony do słaba głowa normalna forma, co oznacza, że ​​stosowana jest najbardziej zewnętrzna funkcja. W przypadku y, najbardziej zewnętrzną funkcją jest +, w ten sposób y jest w pełni oszacowany na liczbę przed przekazaniem do go.

---

Aha, i prawdopodobnie dostałeś komunikat o błędzie typu nieskończonego, ponieważ nie masz nawiasów we właściwym miejscu. Mam ten sam błąd po raz pierwszy napisał swój program w dół :-)

Ponieważ operator $! jest prawo zrzeszania się, bez nawiasu go $! (s+x) $! (l+1) oznacza to samo co: go $! ((s+x) $! (l+1)), co jest oczywiście błędne.

Answer 3

Funkcja seq wymusza ocenę pierwszego parametru po wywołaniu funkcji. Po przekazaniu seq s (s+x) jako parametru funkcja seq nie jest wywoływana natychmiast, ponieważ nie ma potrzeby oceny wartości tego parametru. Chcesz, aby wywołanie do seq było oceniane przed wywołaniem rekursywnym, aby to z kolei mogło wymusić ocenę jego parametru.

Zwykle odbywa się to związek to:

go s l (x:xs) = s `seq` l `seq` go (s+x) (l+1) xs 

To składniowym odmianą seq s (seq l (go (s+x) (l+1) xs)). Tutaj wywołania do seq są najbardziej zewnętrznymi wywołaniami funkcji w wyrażeniu. Z powodu lenistwa Haskella powoduje to, że są one najpierw oceniane: seq jest wywoływany z nadal nieocenionymi parametrami s i seq l (go (s+x) (l+1) xs), ocena parametrów jest odroczona do punktu, w którym ktoś faktycznie próbuje uzyskać dostęp do ich wartości.

Teraz seq może wymusić ocenę pierwszego parametru przed zwróceniem pozostałej części wyrażenia. Następnym krokiem w ocenie będzie drugie seq. Jeśli połączenia z seq są pochowane gdzieś w jakimś parametrze, mogą nie zostać wykonane przez długi czas, pokonując ich cel.

Przy zmianie pozycji seq s program wykonuje się poprawnie, bez nadmiernej ilości pamięci.

Innym rozwiązaniem tego problemu byłoby po prostu włączenie optymalizacji w GHC podczas kompilacji programu (-O lub -O2). Optymalizator rozpoznaje zbędne lenistwo i tworzy kod, który nie przydziela niepotrzebnej pamięci.