In Real World Haskell , Kapitel 4. zur funktionalen Programmierung :
Schreibe Foldl mit 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)
Der obige Code hat mich sehr verwirrt, und jemand namens dps hat ihn mit einem aussagekräftigen Namen umgeschrieben, um ihn etwas klarer zu machen:
myFoldl stepL zeroL xs = (foldr stepR id xs) zeroL
where stepR lastL accR accInitL = accR (stepL accInitL lastL)
Jemand anderes, Jef G, hat dann hervorragende Arbeit geleistet, indem er ein Beispiel lieferte und Schritt für Schritt den zugrunde liegenden Mechanismus zeigte:
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
Aber ich kann das immer noch nicht ganz verstehen, hier sind meine Fragen:
- Wofür ist die ID-Funktion? Was ist die Rolle von? Warum sollten wir es hier brauchen?
- Im obigen Beispiel ist die ID-Funktion der Akkumulator in der Lambda-Funktion.
- Der Prototyp von foldr ist
foldr :: (a -> b -> b) -> b -> [a] -> b
, und der erste Parameter ist eine Funktion, die zwei Parameter benötigt, aber die Schrittfunktion in der Implementierung von myFoldl verwendet 3 Parameter. Ich bin völlig verwirrt!
step = curry $ uncurry (&) <<< (flip f) *** (.)
Antworten:
Einige Erklärungen sind angebracht!
Wofür ist die ID-Funktion? Was ist die Rolle von? Warum sollten wir es hier brauchen?
id
ist die Identitätsfunktion ,id x = x
und wird als das Äquivalent von Null verwendet wird, wenn eine Kette von Funktionen mit dem Aufbau Funktion Zusammensetzung ,(.)
. Sie finden es im Präludium definiert .Im obigen Beispiel ist die ID-Funktion der Akkumulator in der Lambda-Funktion.
Der Akkumulator ist eine Funktion, die durch wiederholte Funktionsanwendung aufgebaut wird. Es gibt kein explizites Lambda, da wir den Akkumulator nennen
step
. Sie können es mit einem Lambda schreiben, wenn Sie möchten:foldl f a bs = foldr (\b g x -> g (f x b)) id bs a
Oder wie Graham Hutton schreiben würde :
Der Prototyp von foldr ist foldr :: (a -> b -> b) -> b -> [a] -> b
Ein Haskell-Programmierer würde sagen, dass die Art von
foldr
ist(a -> b -> b) -> b -> [a] -> b
.und der erste Parameter ist eine Funktion, die zwei Parameter benötigt, aber die Schrittfunktion in der Implementierung von myFoldl verwendet 3 Parameter, ich bin völlig verwirrt
Das ist verwirrend und magisch! Wir spielen einen Streich und ersetzen den Akkumulator durch eine Funktion, die wiederum auf den Anfangswert angewendet wird, um ein Ergebnis zu erhalten.
Graham Hutton erklärt , den Trick zu drehen
foldl
infoldr
in dem obigen Artikel. Wir schreiben zunächst eine rekursive Definition vonfoldl
:foldl :: (a -> b -> a) -> a -> [b] -> a foldl f v [] = v foldl f v (x : xs) = foldl f (f v x) xs
Und überarbeiten Sie es dann über die statische Argumenttransformation auf
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)
Lassen Sie uns jetzt umschreiben
g
, um dasv
Innere zu schweben :foldl f v xs = g xs v where g [] = \v -> v g (x:xs) = \v -> g xs (f v x)
Das ist dasselbe wie das Denken
g
als Funktion eines Arguments, das eine Funktion zurückgibt:foldl f v xs = g xs v where g [] = id g (x:xs) = \v -> g xs (f v x)
Jetzt haben wir
g
eine Funktion, die rekursiv durch eine Liste geht, eine Funktion anwendenf
. Der Endwert ist die Identitätsfunktion, und jeder Schritt führt auch zu einer Funktion.Aber wir haben bereits eine sehr ähnliche rekursive Funktion auf Listen zur Hand
foldr
!Dies sieht nach einem sehr ähnlichen rekursiven Schema wie unsere
g
Funktion aus. Nun der Trick: Mit der gesamten verfügbaren Magie (auch bekannt als Bird, Meertens und Malcolm) wenden wir eine spezielle Regel an, die universelle Eigenschaft der Falte , die eine Äquivalenz zwischen zwei Definitionen für eine Funktion istg
, die Listen verarbeitet, angegeben als:Die universelle Eigenschaft von Falten besagt also, dass:
wo
g
muss für einige äquivalent zu den beiden Gleichungen seink
undv
:Aus unseren früheren Faltentwürfen wissen wir
v == id
. Für die zweite Gleichung müssen wir jedoch die Definition von berechnenk
: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'
Was durch Ersetzen unserer berechneten Definitionen von
k
undv
ergibt eine Definition von foldl als:foldl :: (a -> b -> a) -> a -> [b] -> a foldl f v xs = foldr (\x g -> (\a -> g (f v x))) id xs v
Die Rekursive
g
wird durch den Foldr-Kombinator ersetzt, und der Akkumulator wird zu einer Funktion, die über eine Kette von Kompositionenf
an jedem Element der Liste in umgekehrter Reihenfolge aufgebaut wird (also falten wir links statt rechts).Dies ist definitiv etwas fortgeschritten. Um diese Transformation, die universelle Eigenschaft von Falten , die die Transformation ermöglicht, tief zu verstehen , empfehle ich Huttons Tutorial, das unten verlinkt ist.
Verweise
quelle
k = \x g' -> (\a -> g' (f v x))
und(\x g -> (\a -> g (f v x)))
Betrachten Sie die Art von
foldr
:foldr :: (b -> a -> a) -> a -> [b] -> a
Während die Art von
step
ist so etwas wieb -> (a -> a) -> a -> a
. Da der Schritt an übergeben wird,foldr
können wir schließen, dass in diesem Fall die Falte einen Typ wie hat(b -> (a -> a) -> (a -> a)) -> (a -> a) -> [b] -> (a -> a)
.Lassen Sie sich nicht durch die unterschiedlichen Bedeutungen
a
verschiedener Signaturen verwirren . Es ist nur eine Typvariable. Denken Sie auch daran, dass der Funktionspfeil rechtsassoziativ ist, alsoa -> b -> c
dasselbe wiea -> (b -> c)
.Ja, der Akkumulatorwert für
foldr
ist eine Funktion vom Typa -> a
, und der Anfangswert istid
. Dies ist sinnvoll, daid
es sich um eine Funktion handelt, die nichts tut. Aus demselben Grund würden Sie beim Hinzufügen aller Werte in einer Liste mit Null als Anfangswert beginnen.Wie für
step
drei Argumente nehmen, versuchen Sie es wie folgt umschreiben:step :: b -> (a -> a) -> (a -> a) step x g = \a -> g (f a x)
Macht es das einfacher zu sehen, was los ist? Es wird ein zusätzlicher Parameter benötigt, da eine Funktion zurückgegeben wird und die beiden Schreibweisen gleich sind. Beachten Sie auch den zusätzlichen Parameter nach
foldr
:(foldr step id xs) z
. Der Teil in Klammern ist die Falte selbst, die eine Funktion zurückgibt, auf die dann angewendet wirdz
.quelle
(Blättern Sie schnell durch meine Antworten [1] , [2] , [3] , [4] , um sicherzustellen, dass Sie die Syntax von Haskell, Funktionen höherer Ordnung, Currying, Funktionszusammensetzung, $ -Operator, Infix- / Präfix-Operatoren, Abschnitte und Lambdas verstehen )
Universelle Eigenschaft der Falte
Eine Falte ist nur eine Kodifizierung bestimmter Arten von Rekursion. Und die Universalitätseigenschaft besagt einfach, dass Ihre Rekursion, wenn sie einer bestimmten Form entspricht, nach einigen formalen Regeln in eine Falte umgewandelt werden kann. Und umgekehrt kann jede Falte in eine solche Rekursion umgewandelt werden. Wiederum können einige Rekursionen in Falten übersetzt werden, die genau die gleiche Antwort geben, und einige Rekursionen können dies nicht, und es gibt ein genaues Verfahren, um dies zu tun.
Wenn Ihre rekursive Funktion für Listen funktioniert und wie links aussieht , können Sie sie grundsätzlich so transformieren, dass sie rechts faltet , ersetzt
f
und das ersetzt,v
was tatsächlich vorhanden ist.g [] = v ⇒ g (x:xs) = f x (g xs) ⇒ g = foldr f v
Zum Beispiel:
sum [] = 0 {- recursion becomes fold -} sum (x:xs) = x + sum xs ⇒ sum = foldr 0 (+)
Hier
v = 0
undsum (x:xs) = x + sum xs
entsprichtsum (x:xs) = (+) x (sum xs)
daherf = (+)
. 2 weitere Beispieleproduct [] = 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
Wie schreibe ich eine rekursive Funktion, die Zahlen von links nach rechts summiert?
sum [] = 0 -- given `sum [1,2,3]` expands into `(1 + (2 + 3))` sum (x:xs) = x + sum xs
Die erste rekursive Funktion, die vollständig gefunden wird, erweitert sich, bevor sie sich überhaupt summiert. Das ist nicht das, was wir brauchen. Ein Ansatz besteht darin, eine rekursive Funktion mit Akkumulator zu erstellen , die bei jedem Schritt sofort Zahlen addiert (lesen Sie mehr über die Schwanzrekursion , um mehr über Rekursionsstrategien zu erfahren):
suml :: [a] -> a suml xs = suml' xs 0 where suml' [] n = n -- auxiliary function suml' (x:xs) n = suml' xs (n+x)
Okay, hör auf! Führen Sie diesen Code in GHCi aus und stellen Sie sicher, dass Sie verstehen, wie er funktioniert. Fahren Sie dann sorgfältig und nachdenklich fort.
suml
kann nicht mit einer Falte neu definiert werden,suml'
kann es aber sein.suml' [] = v -- equivalent: v n = n suml' (x:xs) n = f x (suml' xs) n
suml' [] n = n
von der Funktionsdefinition, richtig? Undv = suml' []
aus der universellen Eigenschaftsformel. Zusammen ergibt diesv n = n
eine Funktion, die sofort alles zurückgibt, was sie empfängt :v = id
. Berechnen wirf
: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
So
suml' = foldr (\x g n -> g (n+x)) id
und sosuml = foldr (\x g n -> g (n+x)) id xs 0
.foldr (\x g n -> g (n + x)) id [1..10] 0 -- return 55
Jetzt müssen wir nur noch verallgemeinern,
+
durch eine variable Funktion ersetzen :foldl f a xs = foldr (\x g n -> g (n `f` x)) id xs a foldl (-) 10 [1..5] -- returns -5
Fazit
Lesen Sie jetzt Graham Huttons A-Tutorial über die Universalität und Ausdruckskraft von Fold . Holen Sie sich Stift und Papier und versuchen Sie, alles herauszufinden, was er schreibt, bis Sie die meisten Falten selbst erhalten. Schwitzen Sie nicht, wenn Sie etwas nicht verstehen, Sie können später jederzeit zurückkehren, aber zögern Sie auch nicht viel.
quelle
Hier ist mein Beweis,
foldl
der ausgedrückt werden kann in Bezug auffoldr
, was ich ziemlich einfach finde, abgesehen von dem Namen Spaghetti, den diestep
Funktion einführt.Der Satz ist, dass
foldl f z xs
äquivalent zu istmyfoldl f z xs = foldr step_f id xs z where step_f x g a = g (f a x)
Das erste, was hier zu beachten ist, ist, dass die rechte Seite der ersten Zeile tatsächlich als ausgewertet wird
da
foldr
braucht man nur drei parameter. Dies deutet bereits darauf hin, dass derfoldr
Wille keinen Wert berechnet, sondern eine Curry-Funktion, auf die dann angewendet wirdz
. Es sind zwei Fälle zu untersuchen, um herauszufinden, ob dies der Fallmyfoldl
istfoldl
:Basisfall: leere Liste
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)
Nicht leere Liste
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
Da in 2. die erste und die letzte Zeile in beiden Fällen dieselbe Form haben, kann die Liste bis dahin gefaltet
xs == []
werden. In diesem Fall garantiert 1. dasselbe Ergebnis. Also durch Induktion ,myfoldl == foldl
.quelle
Lesen Sie vor dem Downvoting den folgenden Absatz
Ich poste die Antwort für diejenigen, die diesen Ansatz möglicherweise besser für ihre Denkweise finden. Die Antwort enthält möglicherweise redundante Informationen und Gedanken, aber es ist das, was ich brauchte, um das Problem anzugehen. Da dies eine weitere Antwort auf dieselbe Frage ist, ist es offensichtlich, dass sie sich erheblich mit den anderen Antworten überschneidet, erzählt jedoch die Geschichte, wie ich dieses Konzept verstehen könnte.
In der Tat begann ich, diese Notizen als persönliche Aufzeichnung meiner Gedanken aufzuschreiben, während ich versuchte, dieses Thema zu verstehen. Ich habe den ganzen Tag gebraucht, um den Kern zu berühren, wenn ich ihn wirklich habe.
Mein langer Weg zum Verständnis dieser einfachen Übung
Einfacher Teil: Was müssen wir bestimmen?
Was passiert mit dem folgenden Beispielaufruf?
foldl f z [1,2,3,4]
kann mit dem folgenden Diagramm visualisiert werden (das auf Wikipedia ist , aber ich habe es zuerst auf einer anderen Antwort gesehen ):
_____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
(Als Randnotiz, wenn die Verwendung der
foldl
einzelnen Anwendungen vonf
nicht ausgeführt wird und die Ausdrücke genau so angezeigt werden, wie ich sie oben geschrieben habe; im Prinzip könnten sie berechnet werden, wenn Sie von unten nach oben gehen, und genau dasfoldl'
tut es.)Die Übung fordert uns im Wesentlichen heraus,
foldr
anstattfoldl
die Schrittfunktion (also verwenden wirs
stattf
) und den anfänglichen Akkumulator (also verwenden wir?
stattz
) entsprechend zu ändern . Die Liste bleibt gleich, sonst wovon reden wir?Der Aufruf an
foldr
muss so aussehen:foldr s ? [1,2,3,4]
und das entsprechende Diagramm ist dieses:
_____what does the last call return? / s / \ 1 s / \ 2 s / \ 3 s / \ 4 ? <--- what is the initial accumulator?
Der Anruf führt zu
s 1 (s 2 (s 3 (s 4 ?)))
Was sind
s
und?
? Und was sind ihre Typen? Es sieht so aus, als wäres
es eine Funktion mit zwei Argumenten, ähnlichf
, aber lassen Sie uns nicht zu Schlussfolgerungen springen. Lassen wir auch?
einen Moment beiseite und beobachten, dass diesz
ins Spiel kommen muss, sobald es1
ins Spiel kommt. Wie kann jedochz
der Aufruf der Funktion "Vielleicht zwei Argumente"s
, nämlich der Aufruf , ins Spiel kommens 1 (…)
? Wir können diesen Teil des Rätsels lösen, indems
wir ein wählen, das 3 Argumente anstelle der 2, die wir zuvor erwähnt haben, akzeptiert, so dass der äußerste Aufruf dazus 1 (…)
führt, dass eine Funktion ein Argument annimmt , an das wir übergeben könnenz
!Dies bedeutet, dass wir den ursprünglichen Aufruf möchten, der auf erweitert wird
f (f (f (f z 1) 2) 3) 4
gleichwertig sein mit
s 1 (s 2 (s 3 (s 4 ?))) z
oder mit anderen Worten, wir wollen die teilweise angewendete Funktion
s 1 (s 2 (s 3 (s 4 ?)))
äquivalent zu der folgenden Lambda-Funktion sein
(\z -> f (f (f (f z 1) 2) 3) 4)
Wieder sind die "einzigen" Stücke, die wir brauchen,
s
und?
.Wendepunkt: Funktionszusammensetzung erkennen
Lassen Sie uns das vorherige Diagramm neu zeichnen und rechts schreiben, was jeder Aufruf
s
entsprechen soll: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?
Ich hoffe, aus der Struktur des Diagramms geht hervor, dass sich
(…)
auf jeder Zeile die rechte Seite der darunter liegenden Zeile befindet. Besser ist es die Funktion, die vom vorherigen (unten) Aufruf an zurückgegeben wurdes
.Es sollte auch klar sein, dass ein Aufruf
s
mit Argumentenx
undy
die (vollständige) Anwendungy
auf die teilweise Anwendungf
auf das einzige Argument istx
. Da die teilweise Anwendung vonf
tox
als Lambda geschrieben werden kann(\z -> f z x)
, führt die vollständige Anwendungy
auf das Lambda(\z -> y (f z x))
, das ich in diesem Fall umschreiben würde alsy . (\z -> f z x)
; die Wörter in einen Ausdruck zu übersetzen, dens
wir bekommens x y = y . (\z -> f z x)
(Dies ist
s x y z = y (f z x)
dasselbe wie das Buch, wenn Sie die Variablen umbenennen.)Das letzte Bit ist: Was ist der anfängliche "Wert"
?
des Akkumulators? Das obige Diagramm kann umgeschrieben werden, indem die verschachtelten Aufrufe zu Kompositionsketten erweitert werden: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?
Wir sehen hier, dass
s
sich aufeinanderfolgende Teilanwendungen von einfach "stapeln"f
, aber dasy
ins x y = y . (\z -> f z x)
legt nahe, dass die Interpretation vons 4 ?
(und wiederum allen anderen) eine führende Funktion verfehlt, die mit dem Lambda ganz links zusammengesetzt werden soll.Das ist nur unsere
?
Aufgabe: Es ist Zeit, ihm einen Grund für seine Existenz zu geben und nicht nur einen Platz im Aufruf an einzunehmenfoldr
. Was können wir wählen, um die resultierenden Funktionen nicht zu ändern? Antwort:id
Das Identitätselement in Bezug auf den Kompositionsoperator(.)
.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
Die gesuchte Funktion ist also
myFoldl f z xs = foldr (\x g a -> g (f a x)) id xs z
quelle
Es gibt weder einen Königsweg zur Mathematik noch durch Haskell. Lassen
h z = (foldr step id xs) z where step x g = \a -> g (f a x)
Was zum Teufel ist das
h z
? Nehmen Sie das anxs = [x0, x1, x2]
.Wenden Sie die Definition von foldr an:
h z = (step x0 (step x1 (step x2 id))) z
Wenden Sie die Definition von Schritt an:
Ersatz in die Lambda-Funktionen:
Übernehmen Sie die Definition der ID:
Übernehmen Sie die Definition von foldl:
Ist es eine königliche Straße oder was?
quelle
Dies könnte helfen, ich habe versucht, auf eine andere Weise zu erweitern.
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 = ...
quelle
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)
Zumindest hat mir das geholfen. Auch ist es nicht ganz richtig.
quelle
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)
.Diese Antwort macht die folgende Definition in drei Schritten leicht verständlich.
-- 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)
Schritt 1. Transformieren Sie die Falte der Funktionsbewertung in eine Funktionskombination
foldl f z [x1 .. xn] = z & f1 & .. & fn = fn . .. . f1 z
. in demfi = \z -> f z xi
.(Mit
z & f1 & f2 & .. & fn
es bedeutetfn ( .. (f2 (f1 z)) .. )
.)Schritt 2. Drücken Sie die Funktionskombination auf eine
foldr
Weise ausfoldr (.) id [f1 .. fn] = (.) f1 (foldr (.) id [f2 .. fn]) = f1 . (foldr (.) id [f2 .. fn])
. Entfalte den Rest, um ihn zu bekommenfoldr (.) id [f1 .. fn] = f1 . .. . fn
.Wenn wir feststellen, dass die Reihenfolge umgekehrt ist, sollten wir die umgekehrte Form von verwenden
(.)
. Definieren Sierc f1 f2 = (.) f2 f1 = f2 . f1
dannfoldr rc id [f1 .. fn] = rc f1 (foldr (.) id [f2 .. fn]) = (foldr (.) id [f2 .. fn]) . f1
. Entfalte den Rest, um ihn zu bekommenfoldr rc id [f1 .. fn] = fn . .. . f1
.Schritt 3. Transformieren Sie die Fold-On-Funktionsliste in die Fold-On-Operandenliste
Finden Sie
step
das machtfoldr step id [x1 .. xn] = foldr rc id [f1 .. fn]
. Es ist leicht zu findenstep = \x g z -> g (f z x)
.In 3 Schritten ist die Definition der
foldl
Verwendungfoldr
klar:Beweisen Sie die Richtigkeit:
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)
Wenn Sie etwas unklar finden, fügen Sie bitte einen Kommentar hinzu. :) :)
quelle