Dlaczego te fałdy zatrzymują się na głowie/ogonie?

Question

Czytam learnyouahaskell.com i obecnie badam fałdy. W książce znajdują się te przykłady:

maximum' :: (Ord a) => [a] -> a 
maximum' = foldr1 (\x acc -> if x > acc then x else acc) 

reverse' :: [a] -> [a] 
reverse' = foldl (\acc x -> x : acc) [] 

product' :: (Num a) => [a] -> a 
product' = foldr1 (*) 

filter' :: (a -> Bool) -> [a] -> [a] 
filter' p = foldr (\x acc -> if p x then x : acc else acc) [] 

head' :: [a] -> a 
head' = foldr1 (\x _ -> x) 

last' :: [a] -> a 
last' = foldl1 (\_ x -> x) 

Rozumiem, wszyscy z wyjątkiem head' i tail'.

Rozumiem, że funkcja binarna powinna zostać zastosowana do akumulatora i każdego elementu na liście, a następnie przejść przez całą listę. Dlaczego to zatrzymuje się na głowie (lub ogonie, odpowiednio)?

Rozumiem, _ (podkreślenie) oznacza "cokolwiek" lub "nie obchodzi mnie to", ale jak to się dzieje, przechodząc przez całą listę?

Answer 1

Rzućmy okiem na definicji foldr1 pierwsze:

foldr1 :: (a -> a -> a) -> [a]  -> a 
foldr1 f    [x]  = x 
foldr1 f    (x : xs) = f x (foldr1 f xs) 

Następnie, należy rozważyć połączenie swojej funkcji head',

head' :: [a] -> a 
head' = foldr1 (\x _ -> x) 

do listy, powiedzmy, [2, 3, 5]:

head' [2, 3, 5] 

Teraz, wypełniając w prawej-stronie head' daje

foldr1 (\x _ -> x) [2, 3, 5] 

Przypomnijmy, że [2, 3, 5] jest cukier syntaktyczny dla (2 : 3 : 5 : []). Tak, drugi przypadek dotyczy definicji foldr1 i wydajność

(\x _ -> x) 2 (foldr1 (\x _ -> x) (3 : 5 : []) 

Teraz, zmniejszając wyniki zastosowań w 2 uzyskiwanie związały się x i foldr1 (\x _ -> x) (3 : 5 : []) uzyskiwanie związany z parametrem _ ignorowane.Co pozostało jest po prawej stronie od lambda-abstrakcji z x zastąpione 2:

2 

Należy pamiętać, że ocena leniwy sprawia, że ​​zignorował argumentem foldr1 (\x _ -> x) (3 : 5 : []) pozostało unevaluated i tak i to z nadzieją odpowiedzi na swoje pytanie- rekursja zatrzymuje się, zanim przetworzyliśmy resztę listy.

Answer 2

Foldr łączy w sobie dwie pozycje - bieżącą "bieżącą sumę" i nowy przedmiot.

(\x _ -> x) bierze nowy przedmiot i odrzuca go, zachowując oryginał, więc wszystkie pozostałe elementy są ignorowane.

Niech go rozwinąć:

foldr1 (\x _ -> x) [1..100000] 
= (\x _ -> x) 1 (foldr (\x _ -> x) [2..100000]) 
= 1 

Ponieważ termin (foldr (\x _ -> x) [2..100000]) nie jest potrzebna, to nie jest analizowany (to leniwa ewaluacja w akcji, czy raczej bezczynność), więc to działa szybko.

---

Z (\_ x -> x), nowy element zostanie podjęta i stary jest ignorowany - ten utrzymuje się dzieje do końca listy, więc można dostać ostatni element. Nie omija innych, po prostu zapomina o nich wszystkich oprócz ostatniego.

Bardziej czytelna dla człowieka nazwa (\_ x -> x) odnosi się do faktu, że ignoruje swój pierwszy argument i zwraca jego drugi. Nazwijmy to secondArg.

foldl1 (\_ x -> x) [1..4] 
= let secondArg = (\_ x -> x) in foldl secondArg 1 [2..4] 
= foldl (1 `secondArg` 2) [3..4] 
= foldl ((1 `secondArg` 2) `secondArg` 3) [4] 
= foldl (((1 `secondArg` 2) `secondArg` 3) `secondArg` 4) [] 
= (((1 `secondArg` 2) `secondArg` 3) `secondArg` 4) 
= 4