W Real World Haskell , rozdział 4. o programowaniu funkcjonalnym :
Napisz foldl z foldr:
-- file: ch04/Fold.hs
myFoldl :: (a -> b -> a) -> a -> [b] -> a
myFoldl f z xs = foldr step id xs z
where step x g a = g (f a x)
Powyższy kod bardzo mnie zmylił, a ktoś o nazwisku dps przepisał go z wymowną nazwą, aby była nieco bardziej przejrzysta:
myFoldl stepL zeroL xs = (foldr stepR id xs) zeroL
where stepR lastL accR accInitL = accR (stepL accInitL lastL)
Ktoś inny, Jef G, wykonał świetną robotę, podając przykład i pokazując krok po kroku podstawowy mechanizm:
myFoldl (+) 0 [1, 2, 3]
= (foldR step id [1, 2, 3]) 0
= (step 1 (step 2 (step 3 id))) 0
= (step 1 (step 2 (\a3 -> id ((+) a3 3)))) 0
= (step 1 (\a2 -> (\a3 -> id ((+) a3 3)) ((+) a2 2))) 0
= (\a1 -> (\a2 -> (\a3 -> id ((+) a3 3)) ((+) a2 2)) ((+) a1 1)) 0
= (\a1 -> (\a2 -> (\a3 -> (+) a3 3) ((+) a2 2)) ((+) a1 1)) 0
= (\a1 -> (\a2 -> (+) ((+) a2 2) 3) ((+) a1 1)) 0
= (\a1 -> (+) ((+) ((+) a1 1) 2) 3) 0
= (+) ((+) ((+) 0 1) 2) 3
= ((0 + 1) + 2) + 3
Ale nadal nie mogę tego w pełni zrozumieć, oto moje pytania:
- Do czego służy funkcja id? Jaka jest rola? Po co nam to tutaj?
- W powyższym przykładzie funkcja id jest akumulatorem w funkcji lambda?
- Prototyp foldr to
foldr :: (a -> b -> b) -> b -> [a] -> b
, a pierwszym parametrem jest funkcja, która potrzebuje dwóch parametrów, ale funkcja step w implementacji myFoldl używa 3 parametrów, jestem kompletnie zdezorientowany!
step = curry $ uncurry (&) <<< (flip f) *** (.)
Odpowiedzi:
Kilka wyjaśnień jest w porządku!
Do czego służy funkcja id? Jaka jest rola? Po co nam to tutaj?
id
Jest to funkcja tożsamości ,id x = x
i służy jako ekwiwalent zera podczas budowania łańcucha funkcji o składzie funkcyjnym ,(.)
. Można to znaleźć w Preludium .W powyższym przykładzie funkcja id jest akumulatorem w funkcji lambda?
Akumulator to funkcja, która jest budowana poprzez wielokrotne stosowanie funkcji. Nie ma wyraźnego lambda, ponieważ wymienić akumulator,
step
. Jeśli chcesz, możesz napisać to z lambdą:foldl f a bs = foldr (\b g x -> g (f x b)) id bs a
Lub, jak napisałby Graham Hutton :
Prototyp foldr to foldr :: (a -> b -> b) -> b -> [a] -> b
Haskell programista powie, że typ z
foldr
jest(a -> b -> b) -> b -> [a] -> b
.a pierwszy parametr to funkcja, która potrzebuje dwóch parametrów, ale funkcja step w implementacji myFoldl używa 3 parametrów, jestem kompletnie zdezorientowany
To zagmatwane i magiczne! Robimy sztuczkę i zastępujemy akumulator funkcją, która z kolei jest stosowana do wartości początkowej, aby uzyskać wynik.
Graham Hutton wyjaśnia trik, aby włączyć
foldl
sięfoldr
w powyższym artykule. Zaczynamy od zapisania rekurencyjnej definicjifoldl
:foldl :: (a -> b -> a) -> a -> [b] -> a foldl f v [] = v foldl f v (x : xs) = foldl f (f v x) xs
A następnie refaktoryzuj go za pomocą statycznej transformacji argumentów na
f
:foldl :: (a -> b -> a) -> a -> [b] -> a foldl f v xs = g xs v where g [] v = v g (x:xs) v = g xs (f v x)
Przepiszmy teraz
g
, aby wypłynąć dov
wewnątrz:foldl f v xs = g xs v where g [] = \v -> v g (x:xs) = \v -> g xs (f v x)
Co jest tym samym, co myślenie o
g
funkcji jednego argumentu, która zwraca funkcję:foldl f v xs = g xs v where g [] = id g (x:xs) = \v -> g xs (f v x)
Teraz mamy
g
funkcję, która rekurencyjnie chodzi po liście, zastosuj jakąś funkcjęf
. Ostatnią wartością jest funkcja tożsamości, a każdy krok skutkuje również funkcją.Ale mamy już bardzo podobną funkcję rekurencyjną na listach
foldr
,!Wygląda to na bardzo podobny schemat rekurencyjny do naszej
g
funkcji. A teraz sztuczka: używając całej dostępnej magii (czyli Birda, Meertensa i Malcolma) stosujemy specjalną regułę, uniwersalną właściwość fold , która jest równoważnością dwóch definicji funkcjig
przetwarzającej listy, wyrażoną jako:Tak więc uniwersalna właściwość fałd stwierdza, że:
gdzie
g
musi być równoważne dwóm równaniom, dla niektórychk
iv
:Wiemy z naszych wcześniejszych projektów składania
v == id
. Jednak w przypadku drugiego równania musimy obliczyć definicjęk
:g (x:xs) = k x (g xs) <=> g (x:xs) v = k x (g xs) v -- accumulator of functions <=> g xs (f v x) = k x (g xs) v -- definition of foldl <= g' (f v x) = k x g' v -- generalize (g xs) to g' <=> k = \x g' -> (\a -> g' (f v x)) -- expand k. recursion captured in g'
Co, zastępując nasze obliczone definicje
k
iv
daje definicję foldl jako:foldl :: (a -> b -> a) -> a -> [b] -> a foldl f v xs = foldr (\x g -> (\a -> g (f v x))) id xs v
Rekurencyjne
g
są zastąpione combinator foldr i akumulator będzie funkcją zbudowana poprzez łańcuch kompozycjif
na każdym elemencie listy, w odwrotnej kolejności (więc krotnie lewo zamiast prawej).Jest to zdecydowanie bardziej zaawansowane, więc aby dogłębnie zrozumieć tę transformację, uniwersalną właściwość fałd , która umożliwia transformację, polecam tutorial Huttona, do którego link znajduje się poniżej.
Bibliografia
źródło
k = \x g' -> (\a -> g' (f v x))
i(\x g -> (\a -> g (f v x)))
Rozważ rodzaj
foldr
:foldr :: (b -> a -> a) -> a -> [b] -> a
Podczas gdy typ
step
jest podobnyb -> (a -> a) -> a -> a
. Ponieważ krok jest przekazywany dofoldr
, możemy wywnioskować, że w tym przypadku fałda ma typ(b -> (a -> a) -> (a -> a)) -> (a -> a) -> [b] -> (a -> a)
.Nie daj się zmylić różnymi znaczeniami
a
w różnych podpisach; to tylko zmienna typu. Pamiętaj też, że strzałka funkcji jest skojarzona w prawo, więca -> b -> c
jest to to samo, coa -> (b -> c)
.Więc tak, wartość akumulatora dla the
foldr
jest funkcją typua -> a
, a wartość początkowa toid
. Ma to sens, ponieważid
jest to funkcja, która nic nie robi - z tego samego powodu zaczynasz od zera jako wartości początkowej podczas dodawania wszystkich wartości na liście.Jeśli chodzi o
step
branie trzech argumentów, spróbuj przepisać to w ten sposób:step :: b -> (a -> a) -> (a -> a) step x g = \a -> g (f a x)
Czy to ułatwia zobaczenie, co się dzieje? Pobiera dodatkowy parametr, ponieważ zwraca funkcję, a dwa sposoby jej zapisania są równoważne. Należy również zwrócić uwagę na dodatkowy parametr po sobie
foldr
:(foldr step id xs) z
. Część w nawiasach to samo zawinięcie, które zwraca funkcję, do której jest następnie stosowanaz
.źródło
(szybko przejrzyj moje odpowiedzi [1] , [2] , [3] , [4], aby upewnić się, że rozumiesz składnię Haskella, funkcje wyższego rzędu, curry, skład funkcji, operator $, operatory wrostków / przedrostków, sekcje i lambdy )
Uniwersalna właściwość fałdy
Krotnie właśnie ujednolicenie niektórych rodzajów rekursji. A własność uniwersalności po prostu stwierdza, że jeśli rekursja jest zgodna z pewną formą, można ją przekształcić w zwinięcie zgodnie z pewnymi formalnymi regułami. I odwrotnie, każdy fałd może zostać przekształcony w tego rodzaju rekursję. Ponownie, niektóre rekursje można przetłumaczyć na fałdy, które dają dokładnie taką samą odpowiedź, a niektóre nie mogą, i jest do tego dokładna procedura.
Zasadniczo, jeśli rekurencyjna funkcja działa na listach an wygląda na lewo , można przekształcić go złożyć ONE prawo , zastępując
f
iv
za to, co faktycznie jest.g [] = v ⇒ g (x:xs) = f x (g xs) ⇒ g = foldr f v
Na przykład:
sum [] = 0 {- recursion becomes fold -} sum (x:xs) = x + sum xs ⇒ sum = foldr 0 (+)
Tutaj
v = 0
isum (x:xs) = x + sum xs
jest odpowiednikiemsum (x:xs) = (+) x (sum xs)
, dlategof = (+)
. Jeszcze 2 przykładyproduct [] = 1 product (x:xs) = x * product xs ⇒ product = foldr 1 (*) length [] = 0 length (x:xs) = 1 + length xs ⇒ length = foldr (\_ a -> 1 + a) 0
Foldl via foldr
Jak napisać funkcję rekurencyjną, która sumuje liczby od lewej do prawej?
sum [] = 0 -- given `sum [1,2,3]` expands into `(1 + (2 + 3))` sum (x:xs) = x + sum xs
Pierwsza funkcja rekurencyjna, która przychodzi do znalezienia, w pełni rozwija się, zanim jeszcze zacznie się sumować, nie tego potrzebujemy. Jednym podejściem jest utworzenie funkcji rekurencyjnej, która ma akumulator , która natychmiast sumuje liczby na każdym kroku (przeczytaj o rekurencji ogonowej, aby dowiedzieć się więcej o strategiach rekurencyjnych):
suml :: [a] -> a suml xs = suml' xs 0 where suml' [] n = n -- auxiliary function suml' (x:xs) n = suml' xs (n+x)
W porządku, przestań! Uruchom ten kod w GHCi i upewnij się, że rozumiesz, jak to działa, a następnie postępuj ostrożnie i starannie.
suml
nie można przedefiniować za pomocą fałdy, alesuml'
można.suml' [] = v -- equivalent: v n = n suml' (x:xs) n = f x (suml' xs) n
suml' [] n = n
z definicji funkcji, prawda? Iv = suml' []
z uniwersalnej formuły własności. Razem daje tov n = n
, że funkcja natychmiast powraca cokolwiek to odbiera:v = id
. Obliczmyf
:suml' (x:xs) n = f x (suml' xs) n -- expand suml' definition suml' xs (n+x) = f x (suml' xs) n -- replace `suml' xs` with `g` g (n+x) = f x g n
W ten sposób
suml' = foldr (\x g n -> g (n+x)) id
, a tym samymsuml = foldr (\x g n -> g (n+x)) id xs 0
.foldr (\x g n -> g (n + x)) id [1..10] 0 -- return 55
Teraz wystarczy uogólnić, zastąpić
+
zmienną funkcją:foldl f a xs = foldr (\x g n -> g (n `f` x)) id xs a foldl (-) 10 [1..5] -- returns -5
Wniosek
Teraz przeczytaj samouczek Grahama Huttona na temat uniwersalności i ekspresji fałdy . Weź trochę długopisu i papieru, spróbuj obliczyć wszystko, co pisze, aż sam uzyskasz większość fałd. Nie przejmuj się, jeśli czegoś nie rozumiesz, zawsze możesz wrócić później, ale też nie zwlekaj zbytnio.
źródło
Oto mój dowód, który
foldl
można wyrazić w kategoriachfoldr
, który uważam za całkiem prosty, poza nazwą spaghetti, którąstep
wprowadza funkcja.Zdanie
foldl f z xs
jest równoważne zmyfoldl f z xs = foldr step_f id xs z where step_f x g a = g (f a x)
Pierwszą ważną rzeczą, na którą należy zwrócić uwagę, jest to, że prawa strona pierwszej linii jest faktycznie oceniana jako
ponieważ
foldr
ma tylko trzy parametry. To już wskazuje, że funkcjafoldr
będzie obliczać nie wartość, ale funkcję curried, która jest następnie stosowanaz
. Istnieją dwa przypadki, w celu zbadania, aby dowiedzieć się, czymyfoldl
jestfoldl
:Podstawowy przypadek: pusta lista
myfoldl f z [] = foldr step_f id [] z (by definition of myfoldl) = id z (by definition of foldr) = z foldl f z [] = z (by definition of foldl)
Lista niepusta
myfoldl f z (x:xs) = foldr step_f id (x:xs) z (by definition of myfoldl) = step_f x (foldr step_f id xs) z (-> apply step_f) = (foldr step_f id xs) (f z x) (-> remove parentheses) = foldr step_f id xs (f z x) = myfoldl f (f z x) xs (definition of myfoldl) foldl f z (x:xs) = foldl f (f z x) xs
Ponieważ w 2. pierwszym i ostatnim wierszu w obu przypadkach ma taki sam kształt, można go użyć do zawinięcia listy do momentu
xs == []
, w którym 1. zagwarantuje ten sam wynik. Tak więc przez indukcjęmyfoldl == foldl
.źródło
Nie ma Królewskiej Drogi do Matematyki ani nawet przez Haskell. Pozwolić
h z = (foldr step id xs) z where step x g = \a -> g (f a x)
Co to do cholery jest
h z
? Załóż toxs = [x0, x1, x2]
.Zastosuj definicję foldr:
h z = (step x0 (step x1 (step x2 id))) z
Zastosuj definicję kroku:
Podstaw do funkcji lambda:
Zastosuj definicję id:
Zastosuj definicję zawinięcia:
Czy to droga królewska, czy co?
źródło
Przed przystąpieniem do głosowania w dół przeczytaj poniższy akapit
Publikuję odpowiedź dla tych osób, które mogą uznać to podejście za lepiej dopasowane do ich sposobu myślenia. Odpowiedź prawdopodobnie zawiera zbędne informacje i myśli, ale właśnie tego potrzebowałem, aby rozwiązać problem. Co więcej, ponieważ jest to kolejna odpowiedź na to samo pytanie, oczywiste jest, że w znacznym stopniu pokrywa się ona z innymi odpowiedziami, jednak opowiada o tym, jak mogłem uchwycić tę koncepcję.
Rzeczywiście, zacząłem zapisywać te notatki jako osobisty zapis moich przemyśleń, próbując zrozumieć ten temat. Zajęło mi cały dzień, zanim dotknąłem jej rdzenia, jeśli naprawdę to mam.
Moja długa droga do zrozumienia tego prostego ćwiczenia
Łatwa część: co musimy ustalić?
Co dzieje się z następującym przykładem wywołania
foldl f z [1,2,3,4]
można zwizualizować za pomocą następującego diagramu (który jest na Wikipedii , ale pierwszy raz zobaczyłem go w innej odpowiedzi ):
_____results in a number / f f (f (f (f z 1) 2) 3) 4 / \ f 4 f (f (f z 1) 2) 3 / \ f 3 f (f z 1) 2 / \ f 2 f z 1 / \ z 1
(Na marginesie, gdy używanie
foldl
każdej aplikacjif
nie jest wykonywane, a wyrażenia są rozumiane tak, jak napisałem je powyżej; w zasadzie można je obliczyć w miarę przechodzenia od dołu do góry i właśnie tofoldl'
robi.)Ćwiczenie zasadniczo wymaga od nas użycia
foldr
zamiastfoldl
odpowiedniej zmiany funkcji step (więc używamys
zamiastf
) i akumulatora początkowego (więc używamy?
zamiastz
); lista pozostaje taka sama, w przeciwnym razie o czym mówimy?Wezwanie do
foldr
musi wyglądać następująco:foldr s ? [1,2,3,4]
a odpowiedni diagram jest następujący:
_____what does the last call return? / s / \ 1 s / \ 2 s / \ 3 s / \ 4 ? <--- what is the initial accumulator?
Wezwanie kończy się
s 1 (s 2 (s 3 (s 4 ?)))
Jakie są
s
i?
? A jakie są ich typy? Wygląda nas
to, że jest to funkcja dwuargumentowa, podobnief
, ale nie przechodźmy do wniosków. Ponadto, zostawmy?
na chwilę na bok i niech zaobserwować, żez
musi wchodzić w grę, gdy tylko1
wchodzi w grę; jak jednak możez
wejść do gry w wywołaniu funkcji może dwuargumentowejs
, a mianowicie w wywołanius 1 (…)
? Możemy rozwiązać tę część zagadki, wybierając opcję,s
która przyjmuje 3 argumenty, a nie 2, o których wspominaliśmy wcześniej, tak aby najbardziej zewnętrzne wywołanies 1 (…)
spowodowało, że funkcja przyjmowała jeden argument, do którego możemy przejśćz
!Oznacza to, że chcemy pierwotnego wywołania, które rozszerza się do
f (f (f (f z 1) 2) 3) 4
być równoważne
s 1 (s 2 (s 3 (s 4 ?))) z
lub, innymi słowy, chcemy częściowo zastosowanej funkcji
s 1 (s 2 (s 3 (s 4 ?)))
być odpowiednikiem następującej funkcji lambda
(\z -> f (f (f (f z 1) 2) 3) 4)
Ponownie, jedyne, czego potrzebujemy, to
s
i?
.Punkt zwrotny: rozpoznaj kompozycję funkcji
Przerysujmy poprzedni diagram i napiszmy po prawej stronie, czemu każde wywołanie
s
ma odpowiadać:s s 1 (…) == (\z -> f (f (f (f z 1) 2) 3) 4) / \ 1 s s 2 (…) == (\z -> f (f (f z 2) 3) 4) / \ 2 s s 3 (…) == (\z -> f (f z 3) 4) / \ 3 s s 4 ? == (\z -> f z 4) / \ 4 ? <--- what is the initial accumulator?
Mam nadzieję, że ze struktury diagramu jasno wynika, że
(…)
w każdym wierszu znajduje się prawa strona linii poniżej; lepiej, jest to funkcja zwrócona z poprzedniego (poniżej) wywołania funkcjis
.Powinno być również jasne, że wywołanie do
s
z argumentamix
iy
jest (pełnym) zastosowaniemy
do częściowego zastosowaniaf
do jedynego argumentux
. Ponieważ częściowe zastosowanief
tox
można zapisać jako lambda(\z -> f z x)
, pełne zastosowaniey
do niego daje lambdę(\z -> y (f z x))
, którą w tym przypadku przepisałbym jakoy . (\z -> f z x)
; przetłumaczenie słów na wyrażenie,s
które otrzymujemys x y = y . (\z -> f z x)
(To jest to samo
s x y z = y (f z x)
, co książka, jeśli zmienisz nazwy zmiennych).Ostatni bit to: jaka jest początkowa „wartość”
?
akumulatora? Powyższy diagram można przepisać, rozszerzając zagnieżdżone wywołania, aby stały się łańcuchami kompozycji:s s 1 (…) == (\z -> f z 4) . (\z -> f z 3) . (\z -> f z 2) . (\z -> f z 1) / \ 1 s s 2 (…) == (\z -> f z 4) . (\z -> f z 3) . (\z -> f z 2) / \ 2 s s 3 (…) == (\z -> f z 4) . (\z -> f z 3) / \ 3 s s 4 ? == (\z -> f z 4) / \ 4 ? <--- what is the initial accumulator?
Widzimy tutaj, że
s
po prostu „gromadzi” kolejne częściowe zastosowaniaf
, aley
ins x y = y . (\z -> f z x)
sugeruje, że interpretacjas 4 ?
(i kolejno wszystkich innych) pomija funkcję wiodącą, którą należy skomponować z lambdą znajdującą się najbardziej po lewej stronie.To tylko nasza
?
funkcja: nadszedł czas, aby dać mu powód do jego istnienia, oprócz zajmowania miejsca w wezwaniufoldr
. Co możemy wybrać, aby nie zmieniać wynikowych funkcji? Odpowiedź:id
, ten element neutralny w stosunku do operatora kompozycji(.)
.s s 1 (…) == id . (\z -> f z 4) . (\z -> f z 3) . (\z -> f z 2) . (\z -> f z 1) / \ 1 s s 2 (…) == id . (\z -> f z 4) . (\z -> f z 3) . (\z -> f z 2) / \ 2 s s 3 (…) == id . (\z -> f z 4) . (\z -> f z 3) / \ 3 s s 4 id == id . (\z -> f z 4) / \ 4 id
Tak więc szukaną funkcją jest
myFoldl f z xs = foldr (\x g a -> g (f a x)) id xs z
źródło
To może pomóc, próbowałem rozszerzyć w inny sposób.
myFoldl (+) 0 [1,2,3] = foldr step id [1,2,3] 0 = foldr step (\a -> id (a+3)) [1,2] 0 = foldr step (\b -> (\a -> id (a+3)) (b+2)) [1] 0 = foldr step (\b -> id ((b+2)+3)) [1] 0 = foldr step (\c -> (\b -> id ((b+2)+3)) (c+1)) [] 0 = foldr step (\c -> id (((c+1)+2)+3)) [] 0 = (\c -> id (((c+1)+2)+3)) 0 = ...
źródło
foldr step zero (x:xs) = step x (foldr step zero xs) foldr _ zero [] = zero myFold f z xs = foldr step id xs z where step x g a = g (f a x) myFold (+) 0 [1, 2, 3] = foldr step id [1, 2, 3] 0 -- Expanding foldr function step 1 (foldr step id [2, 3]) 0 step 1 (step 2 (foldr step id [3])) 0 step 1 (step 2 (step 3 (foldr step id []))) 0 -- Expanding step function if it is possible step 1 (step 2 (step 3 id)) 0 step 2 (step 3 id) (0 + 1) step 3 id ((0 + 1) + 2) id (((0 + 1) + 2) + 3)
Przynajmniej mi to pomogło. Nawet to nie jest do końca w porządku.
źródło
foldr step id [1, 2, 3] 0
->step 1 (foldr step id [2, 3]) 0
->(foldr step id [2, 3]) (0 + 1)
->step 2 (foldr step id [3]) (0 + 1)
->(foldr step id [3]) ((0 + 1) + 2)
->step 3 (foldr step id []) ((0 + 1) + 2)
->(foldr step id []) (((0 + 1) + 2) + 3)
->id (((0 + 1) + 2) + 3)
.Dzięki tej odpowiedzi poniższa definicja jest łatwa do zrozumienia w trzech krokach.
-- file: ch04/Fold.hs myFoldl :: (a -> b -> a) -> a -> [b] -> a myFoldl f z xs = foldr step id xs z where step x g a = g (f a x)
Krok 1. Przekształć zwinięcie oceny funkcji na kombinację funkcji
foldl f z [x1 .. xn] = z & f1 & .. & fn = fn . .. . f1 z
. w którymfi = \z -> f z xi
.(Używając
z & f1 & f2 & .. & fn
tego oznaczafn ( .. (f2 (f1 z)) .. )
.)Krok 2. Wyraź w określony
foldr
sposób kombinację funkcjifoldr (.) id [f1 .. fn] = (.) f1 (foldr (.) id [f2 .. fn]) = f1 . (foldr (.) id [f2 .. fn])
. Rozłóż resztę, aby uzyskaćfoldr (.) id [f1 .. fn] = f1 . .. . fn
.Zauważając, że kolejność jest odwrotna, powinniśmy użyć odwróconej postaci
(.)
. Zdefiniujrc f1 f2 = (.) f2 f1 = f2 . f1
zatemfoldr rc id [f1 .. fn] = rc f1 (foldr (.) id [f2 .. fn]) = (foldr (.) id [f2 .. fn]) . f1
. Rozłóż resztę, aby uzyskaćfoldr rc id [f1 .. fn] = fn . .. . f1
.Krok 3. Przekształć zwinięcie na liście funkcji na zwinięcie na liście argumentów
Znajdź to,
step
co czynifoldr step id [x1 .. xn] = foldr rc id [f1 .. fn]
. Łatwo to znaleźćstep = \x g z -> g (f z x)
.W 3 krokach definicja
foldl
używaniafoldr
jest jasna:Udowodnij poprawność:
foldl f z xs = foldr (\x g z -> g (f z x)) id xs z = step x1 (foldr step id [x2 .. xn]) z = s1 (foldr step id [x2 .. xn]) z = s1 (step x2 (foldr step id [x3 .. xn])) z = s1 (s2 (foldr step id [x3 .. xn])) z = .. = s1 (s2 (.. (sn (foldr step id [])) .. )) z = s1 (s2 (.. (sn id) .. )) z = (s2 (.. (sn id) .. )) (f z x1) = s2 (s3 (.. (sn id) .. )) (f z x1) = (s3 (.. (sn id) .. )) (f (f z x1) x2) = .. = sn id (f (.. (f (f z x1) x2) .. ) xn-1) = id (f (.. (f (f z x1) x2) .. ) xn) = f (.. (f (f z x1) x2) .. ) xn in which xs = [x1 .. xn], si = step xi = \g z -> g (f z xi)
Jeśli uznasz, że coś jest niejasne, dodaj komentarz. :)
źródło