Auf der Spartakiade hatte ich als schwerere Aufgabe für die Teilnehmer folgendes:

Implementiere foldl unter Verwendung von foldr

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 😉