Benutzer:West of House/FP2

Die allgemeingültigen Konzepte der funktionalen Programmierung entstammen der Mathematik der 30er und 40er Jahre. Von besonderer Bedeutung sind der Lambda-Kalkül und die Kategorientheorie. Der Lambda-Kalkül ist ein operatives Regelwerk, mit dessen Hilfe die Bedeutung von symbolischen Ausdrücken bestimmt werden kann. Die Kategorientheorie befasst sich mit der Beziehung zwischen mathematischen Strukturen. Man kann sie zum Beispiel verwenden, um die Struktur eines Computerprogramms auf Strukturen der Anschauung abzubilden und dadurch begründen, warum ein bestimmtes Programm eine bestimmte Aufgabe korrekt löst.

Listen

In der imperativen Programmierung übliche Datenstrukturen wie Arrays sind in der funktionalen Programmierung schwierig im Gebrauch, da sie durch Rekursion nur schwierig darstellbar sind, auch wenn es Ansätze wie das Functional Programming System gibt, die explizit mit solchen Strukturen arbeiten. Listen und Bäume sind hingegen sehr gut mit der Funktionalen Programmierung verträglich.

Sei $A$ ein beliebiger Datentyp. Dann ist der Typ $A^{*}$ der beliebig langen Listen mit mindestens 0 Elementen des Typs $A$ gegeben durch die Rekursion $A^{*}=Nil|Cons(A,A^{*})$. Dabei ist $Nil$ die leere Liste und $Cons:A\times A^{*}\to A^{*}$ eine zweistellige Operation, die aus einem Wert $a$ und einer Liste $L$ neue Liste $M$ konstruiert, indem sie $a$ vorne an $L$ anhängt.

Man kann diesen rekursiven Aufbau benutzen, um Funktionen $h:A^{*}\to B$ zu schreiben, die eine Liste zerlegen und dabei einen Wert ermitteln. Eine solche Funktion $h$ heißt Katamorphismus.

Katamorphismen

Sei $B$ ein Datentyp, $b\in B$ ein Wert und $\otimes :A\times B\to B$ eine Abbildung. Dann ist durch

${\begin{aligned}h:A^{*}&\to B\\Nil&\mapsto b\\Cons(a,L)&\mapsto a\otimes h(L)\end{aligned}}$

der Katamorphismus (zu griech. κατά = entlang, herab) mit Inititialwert $b$ und Verknüpfung $\otimes$ gegeben. In der üblichen Notation mit Bananenklammern wird er als $h=(|b,\otimes |)$ geschrieben. Im Sinne der funktionalen Programmierung ist die Zirkumfix-Operation $(|\cdot ,\cdot |)$ eine Funktion höherer Ordnung. In funktionalen Programmiersprachen gibt es zur Berechnung von Katamorphismen die Funktion reduce oder fold. Ein Katamorphismus, der obiger Definition folgt, ist rechtshändig. Er entspricht der folgenden Programmschleife, die eine Liste von ihrem Ende her traversiert:

${\begin{aligned}&x:=b\\&For\;i:=Length(L){\text{ Downto }}1{\text{ Do}}\\&\;\;x:=L_{i}\otimes x\\&End\\&Return(x)\\\end{aligned}}$

Ein linkshändiger Katamorphismus würde beim Index 1 beginen.

Viele grundlegende Verfahren der Programmierung sind Katamorphismen. So berechnet $(|0,+|)$ die Summe einer Zahlenliste, $(|\epsilon ,\cdot |)$ hängt Strings aneinander und $(|0,Inc|)$ mit $Inc:(n,k)\mapsto k+1$ berechnet die Länge einer Liste. Eine Funktion, die eine Liste $l$ nach Elementen filtert, die die Eigenschaft $p$ erfüllen, kann mit der Funktion $filter$ aus $p$ errechnet werden, die wie folgt definiert ist: $filter:p\mapsto (|Nil,f|)$ mit $f:Cons(a,L)\mapsto Cons(a,L)$ falls $p(a)$ und $f:Cons(a,L)\mapsto L$ sonst.

Ist die Operation $h$ assoziativ mit dem neutralem Element $\emptyset$, dann ist der Katamorphismus $(|\emptyset ,h|)$ die eindeutige Erweiterung der Operation $h$ auf beliebig viele Argumente. Das ist eine ützliche Eigenschaft, die viel Arbeit in der praktischen Programmierung einsparen kann. Ist zum Beispiel eine zweistellige Funktions-Komposition $f\circ g$ bereits implementiert, so lässt sich die Komposition $\bigodot _{i=1}^{n}f_{i}$ von $n$ Funktionen als $(|id,\circ |)$ darstellen (dabei ist $id$ die identische Abbildung).

Anamorphismen

Während Katamorphismen Listen zu Einzelwerten „eindampfen“, bauen Anamorphismen Listen aus Einzelwerten auf. Die Begriffe sind dual zueinander.

Es sei $p:B\to \{w,f\}$ ein Prädikat und $g:B\to A\cup B$ eine Abbildung. Ein Anamorphismus $h:B\to A^{*}$ ist dann so definiert:

${\begin{aligned}h:b&\mapsto Nil{\text{ falls }}p(b)=w\\b&\mapsto Cons(a,h(b')){\text{ mit }}[a,b']=g(b){\text{ falls }}p(b)=f\end{aligned}}$

Der Anamorphismus mit Generator $g$ und Prädikat $p$ wird mit Linsenklammern notiert: $h=[(g,p)]$.

Hylomorphismen

Sei $(|z,f|)$ ein Katamorphismus und $[(p,g)]$ ein Anamorphismus. Dann ist die Abbildung $(|z,f|)\circ [(p,g)]$ ein sogenanter sogenannter Hylomorphismus (griech. υλη = Holz, Material). Er ist in der Lage, einen ganzen Verarbeitungszyklus darzustellen, innerhalb dessen eine Struktur durch einen Anamorphisus ausgerollt und durch einen Katamorphismus eingedampft wird. Es möglich, die durch den Anamorphisus erzeugte Zwischenstruktur algebraisch zu entfernen, sodass sich eine Darstellung des Hylomorphismus ergibt, die auf diese verzichtet. In der Praxis bedeutet dies eine erhebliche Speicherplatzersparnis.

Es problemlos möglich, einen komplexeren Algorithmus wie den Minimax-Algorithmus, der den besten Zug in einem Zweipersonenspiel findet, als Hylomorphismus darzustellen.