Pisanie foldl za pomocą foldr

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:

1. Do czego służy funkcja id? Jaka jest rola? Po co nam to tutaj?
2. W powyższym przykładzie funkcja id jest akumulatorem w funkcji lambda?
3. 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!

Kilka wyjaśnień jest w porządku!

Do czego służy funkcja id? Jaka jest rola? Po co nam to tutaj?

idJest to funkcja tożsamości , id x = xi 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 :

5.1 foldlOperator

Teraz uogólnijmy z sumlprzykładu i rozważmy standardowy operator, foldlktóry przetwarza elementy listy w kolejności od lewej do prawej, używając funkcji fdo łączenia wartości i wartości vjako wartości początkowej:

foldl :: (β → α → β) → β → ([α] → β)
foldl f v [ ] = v
foldl f v (x : xs) = foldl f (f v x) xs

Używając tego operatora, sumlmożna zmienić po prostu przez suml = foldl (+) 0. Wiele innych funkcji można w prosty sposób zdefiniować za pomocą foldl. Na przykład funkcja standardowa reversemoże zostać przedefiniowana za pomocą foldl:

reverse :: [α] → [α]
reverse = foldl (λxs x → x : xs) [ ]

Ta definicja jest bardziej wydajna niż nasza oryginalna definicja z użyciem zwijania, ponieważ pozwala uniknąć nieefektywnego operatora dołączania (++)do list.

Proste uogólnienie obliczeń w poprzedniej sekcji dla funkcji sumlpokazuje, jak przedefiniować funkcję foldlpod względem fold:

foldl f v xs = fold (λx g → (λa → g (f a x))) id xs v

W przeciwieństwie do tego, nie można przedefiniować foldw kategoriach foldl, ponieważ foldljest on ścisły w końcu argumentu listy, ale foldtak nie jest. Istnieje wiele przydatnych „twierdzeń o dualności” dotyczących foldi foldl, a także kilka wskazówek dotyczących decydowania, który operator najlepiej nadaje się do określonych zastosowań (Bird, 1998).

Prototyp foldr to foldr :: (a -> b -> b) -> b -> [a] -> b

Haskell programista powie, że typ z foldrjest (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ć foldlsię foldrw powyższym artykule. Zaczynamy od zapisania rekurencyjnej definicji foldl:

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ąć do vwewną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 gfunkcji 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 gfunkcję, 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,!

2 Operator składania

foldOperator ma swoje korzenie w teorii rekursji (Kleene, 1952), podczas gdy zastosowanie foldjako centralnego pojęcia w terminach języka programowania z powrotem do operatora redukcji APL (Iverson, 1962), a później do operatora wstawiania FP (Backusa , 1978). W Haskell foldoperator list można zdefiniować w następujący sposób:

fold :: (α → β → β) → β → ([α] → β)
fold f v [ ] = v
fold f v (x : xs) = f x (fold f v xs)

Oznacza to, że biorąc pod uwagę funkcję ftypu α → β → βi wartość vtypu β, funkcja fold f vprzetwarza listę typów, [α]aby nadać wartość typu β, zastępując konstruktor nil []na końcu listy wartością v, a każdy konstruktor cons (:)na liście przez funkcję f. W ten sposób foldoperator hermetyzuje prosty wzorzec rekursji do przetwarzania list, w którym dwa konstruktory list są po prostu zastępowane innymi wartościami i funkcjami. Szereg znanych funkcji na listach ma prostą definicję przy użyciu fold.

Wygląda to na bardzo podobny schemat rekurencyjny do naszej gfunkcji. 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 funkcji gprzetwarzającej listy, wyrażoną jako:

g [] = v
g (x:xs) = f x (g xs)

wtedy i tylko wtedy gdy

g = fold f v

Tak więc uniwersalna właściwość fałd stwierdza, że:

    g = foldr k v

gdzie gmusi być równoważne dwóm równaniom, dla niektórych ki v:

    g []     = v
    g (x:xs) = k x (g xs)

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 ki vdaje 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 gsą zastąpione combinator foldr i akumulator będzie funkcją zbudowana poprzez łańcuch kompozycji fna 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

• Haskell Wiki: Foldl jako foldr
• Tutorial o uniwersalności i wyrazistości fałdu , Graham Hutton, J. Functional Programming 9 (4): 355–372, lipiec 1999.
• Malcolm, G. Algebraiczne typy danych i transformacja programu. , Doktorat, Uniwersytet w Groningen.

Rozważ rodzaj foldr:

foldr :: (b -> a -> a) -> a -> [b] -> a

Podczas gdy typ stepjest podobny b -> (a -> a) -> a -> a. Ponieważ krok jest przekazywany do foldr, 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 aw różnych podpisach; to tylko zmienna typu. Pamiętaj też, że strzałka funkcji jest skojarzona w prawo, więc a -> b -> cjest to to samo, co a -> (b -> c).

Więc tak, wartość akumulatora dla the foldrjest funkcją typu a -> a, a wartość początkowa to id. Ma to sens, ponieważ idjest 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 stepbranie 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 stosowana z.

^{(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 fi vza 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 = 0i sum (x:xs) = x + sum xsjest odpowiednikiem sum (x:xs) = (+) x (sum xs), dlatego f = (+). Jeszcze 2 przykłady

product []     = 1
product (x:xs) = x * product xs  ⇒  product = foldr 1 (*)

length []     = 0
length (x:xs) = 1 + length xs    ⇒  length = foldr (\_ a -> 1 + a) 0

Ćwiczenie:

1. Wdrożenie map, filter, reverse, concati concatMaprekurencyjnie, tak jak wyżej funkcji na lewym boku.

2. Zamień te 5 funkcji na foldr zgodnie z powyższym wzorem , czyli podstawiając fi vwe wzorze krotnie po prawej stronie .

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. sumlnie można przedefiniować za pomocą fałdy, ale suml'można.

suml' []       = v    -- equivalent: v n = n
suml' (x:xs) n = f x (suml' xs) n

suml' [] n = nz definicji funkcji, prawda? I v = suml' []z uniwersalnej formuły własności. Razem daje to v n = n, że funkcja natychmiast powraca cokolwiek to odbiera: v = id. Obliczmy f:

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 samym suml = 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.

Oto mój dowód, który foldlmożna wyrazić w kategoriach foldr, który uważam za całkiem prosty, poza nazwą spaghetti, którą stepwprowadza funkcja.

Zdanie foldl f z xsjest równoważne z

myfoldl 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

(foldr step_f id xs) z

ponieważ foldrma tylko trzy parametry. To już wskazuje, że funkcja foldrbędzie obliczać nie wartość, ale funkcję curried, która jest następnie stosowana z. Istnieją dwa przypadki, w celu zbadania, aby dowiedzieć się, czy myfoldljest foldl:

1. 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)
   

2. 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.

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łóż to xs = [x0, x1, x2].
Zastosuj definicję foldr:

h z = (step x0 (step x1 (step x2 id))) z 

Zastosuj definicję kroku:

= (\a0 -> (\a1 -> (\a2 -> id (f a2 x2)) (f a1 x1)) (f a0 x0)) z

Podstaw do funkcji lambda:

= (\a1 -> (\a2 -> id (f a2 x2)) (f a1 x1)) (f z x0)

= (\a2 -> id (f a2 x2)) (f (f z x0) x1)

= id (f (f (f z x0) x1) x2)

Zastosuj definicję id:

= f (f (f z x0) x1) x2

Zastosuj definicję zawinięcia:

= foldl f z [x0, x1, x2]

Czy to droga królewska, czy co?

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 foldlkażdej aplikacji fnie 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 to foldl'robi.)

Ćwiczenie zasadniczo wymaga od nas użycia foldrzamiast foldlodpowiedniej zmiany funkcji step (więc używamy szamiast f) i akumulatora początkowego (więc używamy ?zamiast z); lista pozostaje taka sama, w przeciwnym razie o czym mówimy?

Wezwanie do foldrmusi 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ą si ?? A jakie są ich typy? Wygląda na sto, że jest to funkcja dwuargumentowa, podobnie f, ale nie przechodźmy do wniosków. Ponadto, zostawmy ?na chwilę na bok i niech zaobserwować, że zmusi wchodzić w grę, gdy tylko 1wchodzi w grę; jak jednak może zwejść do gry w wywołaniu funkcji może dwuargumentowej s, a mianowicie w wywołaniu s 1 (…)? Możemy rozwiązać tę część zagadki, wybierając opcję, sktóra przyjmuje 3 argumenty, a nie 2, o których wspominaliśmy wcześniej, tak aby najbardziej zewnętrzne wywołanie s 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 si ?.

Punkt zwrotny: rozpoznaj kompozycję funkcji

Przerysujmy poprzedni diagram i napiszmy po prawej stronie, czemu każde wywołanie sma 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 funkcji s.

Powinno być również jasne, że wywołanie do sz argumentami xi yjest (pełnym) zastosowaniem ydo częściowego zastosowania fdo jedynego argumentu x. Ponieważ częściowe zastosowanie fto xmożna zapisać jako lambda (\z -> f z x), pełne zastosowanie ydo niego daje lambdę (\z -> y (f z x)), którą w tym przypadku przepisałbym jako y . (\z -> f z x); przetłumaczenie słów na wyrażenie, sktóre otrzymujemy

s 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 spo prostu „gromadzi” kolejne częściowe zastosowania f, ale yin s x y = y . (\z -> f z x)sugeruje, że interpretacja s 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 wezwaniu foldr. 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

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 = ...

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.

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órym fi = \z -> f z xi.

(Używając z & f1 & f2 & .. & fntego oznacza fn ( .. (f2 (f1 z)) .. ).)

Krok 2. Wyraź w określony foldrsposób kombinację funkcji

foldr (.) 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 (.). Zdefiniuj rc f1 f2 = (.) f2 f1 = f2 . f1zatem foldr 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, stepco czyni foldr step id [x1 .. xn] = foldr rc id [f1 .. fn]. Łatwo to znaleźć step = \x g z -> g (f z x).

W 3 krokach definicja foldlużywania foldrjest jasna:

  foldl f z xs
= fn . .. . f1 z
= foldr rc id fs z
= foldr step id xs z

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. :)