Dlaczego `foldl1` kończy się pamięć, a` foldr1` działa dobrze?

Question

Napisałem funkcję last przy użyciu foldl1 i foldr1.

lastr :: [a] -> a 
lastr = foldr1 (flip const) 

lastl :: [a] -> a 
lastl = foldl1 (flip const) 

Po prostu działają dobrze na krótkie listy. Ale kiedy próbowałem z bardzo długą listą, [1..10^8], lastr zwraca rozwiązanie w 6,94 s, ale zabrakło mu pamięci.

Definicja foldr1 i foldl1 są (w moim rozumieniu)

foldr1 f [x] = x 
foldr1 f (x:xs) = f x $ foldr1 f xs 

i

foldl1 f [x] = x 
foldl1 f (x:y:ys)=foldl1 f $ f x y : ys 

Widziane z nich foldl1 wydaje się zużywają mniej pamięci niż foldr1 ponieważ foldr1 musi mieć wyraz jak f x1 $ f x2 $ f x3 $ f x4 $..., podczas gdy foldl1 może po prostu obliczyć f x y za każdym razem i przechowywać go jako główny element listy, zamiast trzymać go, aż osiągnie 10^8.

Czy ktoś mógłby mi powiedzieć, co jest nie tak z moją argumentacją?

Answer 1

Prawa zakładka może rozpocząć produkcję natychmiast, jeśli funkcja łączenia jest leniwa w drugim argumencie. Uproszczony przykład:

foldr1 (++) ["one", "two", "three", ...] 
    ~> "one" ++ foldr1 (++) ["two", "three", ...] 

i pierwsza część wyniku jest natychmiast dostępny bez dalszej oceny drugiego argumentu (++). To musi być ocenione dopiero po zużyciu pierwszej części. Często pierwsza część może być już zebrana.

W przykładzie z f = flip const jako funkcją łączącą, mamy inną sytuację, to jest ścisły ⁽¹⁾ w drugim argumencie, ale nie trzeba go w ogóle oceniać. I ignoruje to pierwsze. Jest to również dobre w przypadku prawych fałd. Tu idzie

foldr1 f [x1, x2, x3, ... ] 
    ~> f x1 (foldr1 f [x2, x3, ... ]) 

i teraz najbardziej zewnętrzna f może od razu ocenić

~> foldr1 f [x2, x3, ... ] 
    ~> f x2 (foldr1 f [x3, ... ]) 
    ~> foldr1 f [x3, ... ] 

i na każdym kroku, najbardziej zewnętrzna f zawsze można natychmiast ocenić (całkowicie), a jeden element listy wyrzucone.

Jeżeli lista jest podana przez generator, który może utworzyć go w stałym miejscu, gdy kolejno spożywane

last = foldr1 (flip const) 

może działać w stałej przestrzeni.

Po lewej stronie są różne rzeczy. Ponieważ jest to rekursywny ogon, nie można zwrócić niczego, zanim fałda osiągnie koniec listy. W szczególności, lewa fałda nigdy nie może kończyć się na nieskończonej liście.

Teraz, patrząc w naszym przypadku f = flip const znajdujemy

foldl1 f [x1, x2, x3, x4, ...] 
    ~> foldl f x1 [x2, x3, x4, ... ] 
    ~> foldl f (f x1 x2) [x3, x4, ... ] 
    ~> foldl f (f (f x1 x2) x3) [x4, ... ] 

Oczywiście byłoby możliwe natychmiast ocenić f x1 x2 do x2, a następnie f x2 x3 = x3, ale jest to możliwe tylko dla tej szczególnej f.

Ponieważ foldl jest ogólną funkcją wyższego rzędu, nie może ocenić pośrednich wyników, zanim będą one potrzebne, ponieważ możliwe jest, że pośrednie wyniki nigdy nie są potrzebne - i w rzeczywistości nigdy nie są potrzebne tutaj, na końcu lista, dostaje wyrażenie

f (f (f (f ...y3) y2) y1) y0 
    ~> y0 

a następnie najbardziej zewnętrzna f można ocenić bez patrzenia na ogromne thunk zagnieżdżonych f s, która buduje pierwszy argument.

foldl (odpowiednio foldl1) nie może wiedzieć, że ocena wyników pośrednich byłaby o wiele bardziej efektywna.

Surowe lewej fałdy, foldl' i foldl1' zrobić, to ocena wyników pośrednich słaby główki normalnej postaci (konstruktora wartości najbardziej zewnętrznej lub lambda) i

last = foldl1' (flip const) 

byłby również bardzo skuteczne.

Ale, ponieważ wyniki pośrednie są oceniane dalej niż z foldr, będą one nieco mniej wydajne, i, co ważniejsze, jeśli każdy element listy jest ⊥ wersja foldl1' wróci ⊥:

foldl1' f [x1, ⊥, x3, x4] 
    ~> foldl' f x1 [⊥, x3, x4] 
    ~> case f x1 ⊥ of 
      pattern -- that causes ⊥ 
    ~> ⊥ 

mając na uwadze, że wersja foldr1 nie ma z tym problemu, ponieważ w ogóle nie sprawdza elementów listy ani wyników pośrednich.

---

⁽¹⁾ że f jest ścisłe w drugim argumencie oznacza

f x ⊥ = ⊥ 

Ponieważ f prostu powraca drugi argument jest to wyraźnie inaczej.