Seit geraumer Zeit bin ich fasziniert von “recursion schemes” und habe mich in Scala und nun auch in Haskell mit ihnen beschäftigt. Aber was sind “recursion schemes” und worin liegt für mich ihre Faszination?

Auf zu neuen Ufern…

Dazu wende ich meinen Blick erstmal in die Vergangenheit prozeduraler Programmierung. Programmierer*innen hatten recht wenig Abstraktionen zur Verfügung und anfangs wurden beispielsweise Schleifen mit einer Schleifenvariablen, mehr oder minder vertrackten If Abfragen und gotos realisiert. Irgendwann kam dann ein schlauer Kopf auf die Idee, diese Muster zu abstrahieren. In Dinge wie for-Schleifen, while und do Loops. Ihre Anwendung ist für uns mittlerweile selbstverständlich und wird in der Regel verstanden und nicht hinterfragt.

Rekursion ist zur Erledigung bestimmter Aufgaben ebenso nützlich oder unentbehrlich, insbesondere in der Abwesenheit von mutable state, wie es in reinen funktionalen Programmiersprachen der Fall ist. Aber auch bei der Anwendung von Rekursionen gibt es Muster, und diese Muster lassen sich mithilfe von “recursion schemes” benutzen. Von Erik Meijer ist folgendes Zitat überliefert: “Recursion is the goto of functional programming.”. Manchmal wird es falsch interpretiert - im Sinne von Rekursion ist genauso zu vermeiden wie gotos”, aber das Gegenteil ist gemeint: abstrahiere Rekursion, so dass man sich nicht mit den Kleinkram auseinandersetzen muss.

Meinen Beispielen liegt erstmal ein ganz normaler binärer Baum zugrunde. In Haskell könnte er so definiert sein:

data Tree
  = Leaf
  | Node Int Tree Tree

Der Einfachheit halber ist es ein binärer Baum, der Ints enthält - also nicht über einen Typparameter parametrisiert wurde. Tree ist ein rekursiver Datentyp, denn der Konstruktor Node benötigt wieder zwei Unterbäume.

Mit dieser Definition ist es möglich, die Tiefe eines Baumes zu bestimmen:

depth :: Tree -> Int
depth Leaf                = 0
depth (Node _ left right) = 1 + max (depth left) (depth right)

Deutlich zu erkennen ist die rekursive Natur dieses Algorithmus. Die Tiefe eines Knotens ergibt sich aus 1 plus dem Maximum aus der noch zu bestimmenden Tiefe der Teilbäume (depth left) und (depth right). Aber was wäre, wenn wir die Formulierung “aus der noch zu bestimmenden Tiefe” aus unserem Algorithmus streichen könnten? Wenn wir also einfach annehmen könnten, diese “noch zu bestimmende Tiefe” wäre bereits ermittelt? Oder anders gesagt, wenn ein Node seine Tiefen bereits kennen würde?

Wir könnten dann unseren Algorithmus in etwa so schreiben:

depth :: Tree -> Int
depth Leaf                = 0
depth (Node _ left_depth right_depth) = 1 + max left_depth right_depth

Aber natürlich kompiliert das nicht, weil ein Node nun einmal 2 Unterbäume verlangt, und keinen Platz für 2 Ints zur Bestimmung der Tiefe bereitstellt.

Uns hilft dabei ein sehr eleganter Kniff, in dem wir den Datentyp Tree umschreiben und an jeder Stelle, wo im “Original” ein Tree vorkommt, einfach einen Typparameter verwenden.

data TreeF a
  = LeafF
  | NodeF Int a a

catamorphism

Diese Herleitung ist im übrigen (in Haskell) automatisierbar. TreeF hat noch weitere wichtige Eigenschaften - es lässt sich zum Beispiel ein Funktor für TreeF definieren und es gibt die Funktionen project und embed mit deren Hilfe sich ein Tree in ein TreeF Tree und umgekehrt verwandeln lässt. All dies kriegt man mit ein wenig Template Magic umsonst. Mithilfe unseres neuen Datentyps lässt sich unsere originäre Idee einen Schritt weiterbringen:

depthAlgebra :: TreeF Int -> Int
depthAlgebra LeafF                            = 0
depthAlgebra (NodeF _ left_depth right_depth) = 1 + max left_depth right_depth

Die Funktion habe ich nun depthAlgebra, genannt. Eine Algebra oder genauer F-Algebra hat die Gestalt: f a -> a. Die Struktur eines Datentyps wird zerstört - es ist das gleiche, was ein fold macht. Im Lingo der “recursion schemes” ist dieser fold ein catamorphismus (von cata = Katastrophe = Häuser sind nach Erdbeben zusammengefaltet). Wie meist in der wundervollen Welt der Programmierung, die sich um Wahrheit kümmert, gibt es auch das Gegenteil. Eine Co-Algebra in der Gestalt von a -> f a nennt sich ein unfold oder anamorphismus (von ana wie in Anabolika wie in Powerpulver wird zu strukturierter Muskelmasse).

Unsere depthAlgebra lässt sich auch schon einsetzen:

depth :: Tree -> Int
depth = cata depthAlgebra

Ganz analog zu der Bestimmung der Tiefe eines Baumes lassen sich Algebras erstellen, die die Größe bestimmen, oder prüfen, ob ein bestimmtes Element im Baum enthalten sind. Lustig ist auch die Funktion elems, die alle Elemente eines Baumes als Liste zurückgibt - hier die Definition der dazu passenden Algebra:

elems :: Tree -> [Int]
elems = cata elemsAlgebra

elemsAlgebra :: TreeF [Int] -> [Int]
elemsAlgebra LeafF                   = []
elemsAlgebra (NodeF elem left right) = left ++ [elem] ++ right

Ich finde das einfach irre, weil die ganze Rekursion (vermeintlich) futsch ist. left und right sind nun einfach Listen, die ich zusammenfügen kann. Die bisherigen Beispiele für catamorphismen, ob es nun das Bestimmen der Länge, Tiefe, ob ein Element im Baum enthalten ist oder das Bestimmen der Elemente eines Baums, haben eine Gemeinsamkeit. Zur Bestimmung brauche ich keinerlei Kenntnis über Details der Struktur der Teilbäume. Mir reicht die Teiltiefe, Teillänge, die Teilelemente oder das Enthalten-sein eines Elementes in den Teilen. Andere rekursive Probleme verlangen ab und an andere Morphismen, aber dazu kommen wir noch.

Behind the scenes

Bisher haben wir die Funktion cata einfach hingenommen und nicht weiter erklärt. Das probiere ich nun ein wenig weiter auszuführen. Schreibt man die Signatur von cata so um, dass sie nicht polymorph ist, sondern speziell für unser Tree/depthTree Problem geschrieben wurde, so erhält man:

cataTree :: (TreeF Int -> Int) -> Tree -> Int
cataTree alg = c where
  c :: Tree -> Int
  c = alg . fmap c . project

cataTree bekommt als Eingabe also eine F-Algebra und einen Baum. Intern wird eine Hilfsfunktion c definiert, die es faustdick hinter den Ohren hat, aber tatsächlich recht simpel ist. Unser Eingabebaum wird mit Hilfe von project zunächst in einen TreeF Tree verwandelt. TreeF ist ein Funktor, d.h. wir dürfen über diese Struktur mappen. Stellen wir uns vor, unsere Eingabe wäre der leere Baum gewesen, dann würden wir jetzt ein LeafF vorfinden (der leere Baum vom Typ TreeF Leaf). Diesen gibt uns fmap als Baum vom Typ TreeF Int zurück und die Algebra TreeF Int -> Int verwandelt diesen in in Int und wir bekommen 0 als Ergebnis zurück.

Wäre unser Eingabebaum ein wenig komplizierter (bspw. Node 3 Leaf (Node 5 Leaf Leaf)), passiert folgendes:

• der Eingangsbaum wird mit Hilfe von project in ein TreeF Tree verwandelt.
• fmap stösst auf den NodeF mit Unterbäumen
• fmap möchte und kann diese Unterbäume vom Typ Tree mappen, und ruft wieder c auf
• die Rekursion startet
• der Unterbaum wird wieder projiziert
• fmap kann nichts weiter tun, da wir nun ein LeafF vorfinden. LeafF ist also die Abbruchbedingung unserer Rekursion.
• das passiert mit beiden Leafs und die Algebras liefern nun ein TreeF Int mit NodeF _ 0 0
• das geht in der Rekursion weiter nach oben, und die Algebra erkennt den NodeF-Fall und addiert 1

Epilog

“Die spinnen die Römer…” wäre ein Satz, der nun nicht ganz zu Unrecht fallen dürfte. Aber spinnen die Römer wirklich? Welche Vorteile bringen mir diese “recursion schemes” eigentlich? Der gewichtigste ist vielleicht folgender: Es ist außergewöhnlich schwierig, rekursive Funktionen so zu schreiben, dass sie eine Datenstruktur nur einmal durchforsten, um zu einem Ergebnis zu gelangen. Gemeint ist Folgendes: Möchte ich von einem Baum alle Elemente haben, die Tiefe, die Größe, und Wissen, ob die 3 im Baum enthalten ist, dann kann ich das mit Algebras in einen Aufwasch machen. Mit “herkömmlichen” Funktionen traversiere ich den Baum etliche Male (es sei denn ich schreibe eine einzelne Funktion dafür (!)). Die Anwendung der Schemata gestaltet sich aber noch etwas schwierig. Ich denke, das liegt einfach darin, dass uns Beispiele fehlen. Das gab es halt noch nicht, als man Listings für den C64 abgetippt hat. Diese kleine Reihe, die ich gerne fortführen möchte, soll einfach dazu dienen, einige Beispiele zu versammeln. Mal in Haskell, mal in Scala - mal mit mehr Mathematik, mal weniger.