Auf der Spartakiade hatte ich als schwerere Aufgabe für die Teilnehmer folgendes:
Implementiere
foldl
unter Verwendung vonfoldr
Das ist ein Klassiker, der einem richtig schön das Hirn verknoten kann – ihr könnte es ja gerne (nochmal) probieren, bevor ihr weiter lest!.
Leider hatte ich keine Zeit das richtig aufzulösen, was ich jetzt nachholen will. Zur Erinnerung: Ich hatte die Signaturen so angegeben:
foldr : ('a -> 'b -> 'b) -> 'b -> 'a list -> 'b
foldl : ('b -> 'a -> 'b) -> 'b -> 'a list -> 'b
.
Es geht im Prinzip nur darum, die Klammern von rechts, nach links zu bewegen. Zum Beispiel soll ja
foldl f s [a;b;c] = f (f (f s a) b) c
ergeben, wir dürfen aber eigentlich nur irgendein g
und ein s'
mit
foldr g s' [a;b;c] = f 1 (f 2 (f 3 s'))
verwenden.
Im weiteren solltet ihr von Zeile zu Zeile versuchen die Umformungen zu verstehen – ich habe mich bemüht das in wirklich kleine Schritte zu zerlegen, wenn etwas unklar ist bitte Kommentar oder Nachricht, dann reiche ich das nach.
Der Trick ist jetzt, den Zustand s
zu verfolgen:
s -> s' = f s a -> s'' = f s' b -> s''' = f s'' c
das kann man jetzt etwas umformen:
s -> s' = (fun x -> f x a) s -> s'' = (fun x -> f x b) s' -> s''' = (fun x -> f x c) s''
und es stellt sich allmählich ein Muster heraus – machen wir weiter:
s -> s' = (fun y x -> f x y) a s -> s'' = (fun y x -> f x y) b s' -> s''' = (fun y x -> f x y) c s''
Wie sieht es aus, wenn wir Funktionskompositionen verwenden und uns die Applikation von s
auf den Schluss aufheben?
( (fun y x -> f x y) a >> (fun y x -> f x y) b >> (fun y x -> f x y) c ) s
Wegen f >> id = id
kann es ja nicht schaden noch ein id
einzufügen:
( (fun y x -> f x y) a >> (fun y x -> f x y) b >> (fun y x -> f x y) c >> id ) s
schreiben wir h = fun y x -> f x y
:
( h a >> h b >> h c >> id ) s = (h a >> h b >> h c >> id) s
ein wenig umklammern ( >>
ist ja assoziativ):
(h a >> (h b >> (h c >> id))) s
und jetzt haben wir doch schon ein nettes Muster oder?
Die Klammern sind schon richtig und wenn man genau hinsieht erkennt man unser g
und s'
für das foldr
: s'
muss offensichtlich id
werden, d.h. der neue Zustand der durchgereicht wird ist tatsächlich eine Funktion – man sagt üblicherweise Continuation. Damit müssen wir noch ein g : 'a -> 'cont -> 'cont
suchen, wie wäre es mit
g z cont = h z >> cont = (fun y x -> f x y) z >> cont = (fun y -> f z y) >> cont = fun y -> cont (f z y)
was insgesamt
g z cont y = cont (f z y) s' = id
ergibt.
Alles eingesetzt haben wir:
let foldl f s xs = foldr (fun z cont y -> cont (f z y)) id xs) s
oder (wenn ihr es ausprobieren wollt ohne foldr
erst zu implementieren/definieren):
let foldl f s xs = (List.foldBack (fun z cont y -> cont (f z y)) xs id) s
Fertig 😉