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

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

Katamorphismen

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

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

der Katamorphismus (zu griech. κατά = entlang, herab) mit Initialwert ${\displaystyle b}$ und Verknüpfung ${\displaystyle \otimes }$ gegeben. In der üblichen Notation mit Bananenklammern wird er als ${\displaystyle h=(|b,\otimes |)}$ geschrieben. Im Sinne der funktionalen Programmierung ist die Zirkumfix-Operation ${\displaystyle (|\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:

${\displaystyle {\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 beginnen.

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

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

Anamorphismen

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

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

${\displaystyle {\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 ${\displaystyle g}$ und Prädikat ${\displaystyle p}$ wird mit Linsenklammern notiert: ${\displaystyle h=[(p,g)]}$. Ein Beispiel für einen einfachen Anamorphismus ist die Funktion ${\displaystyle \iota =[(i\mapsto (i<1),i\mapsto [i,i-1])]}$. Sie errechnet aus einer natürlichen Zahl ${\displaystyle n}$ die (umgedrehte) Liste der ersten ${\displaystyle n}$ natürlichen Zahlen ${\displaystyle \iota (n)=[n,n-1,n-2,..,1]}$.

Hylomorphismen

Sei ${\displaystyle (|z,f|)}$ ein Katamorphismus und ${\displaystyle [(p,g)]}$ ein Anamorphismus. Dann ist die Abbildung ${\displaystyle (|z,f|)\circ [(p,g)]}$ ein sogenannter Hylomorphismus (griech. υλη = Holz, Material). Hylomorphismen sind in der Lage, einen ganzen Verarbeitungsprozess darzustellen, innerhalb dessen eine Struktur durch einen Anamorphismus entwickelt und durch einen Katamorphismus wieder eingedampft wird. Diese Darstellung ermöglicht es, die durch den Anamorphismus erzeugte Zwischenstruktur algebraisch zu entfernen. Die daraus resultierende, eigenständige Darstellung des Hylomorphismus ohne Zwischenstruktur führt in der Praxis zu einer erheblichen Reduktion des benötigten Speicherplatzes.

Es ist problemlos möglich, einen komplexeren Algorithmus wie den Minimax-Algorithmus, der den besten Zug in einem Zweipersonenspiel wie Schach findet, als Hylomorphismus darzustellen. Der Hylomorphismus ${\displaystyle$ !=(|1,\times |)\circ ([(i\mapsto (i<1),i\mapsto [i,i-1])]} , der den Katamorphismus ${\displaystyle (|1,\times |)}$ zur Berechnung eines Zahlenprodukts mit dem oben genannten Anamorphismus ${\displaystyle \iota }$ kombiniert, berechnet die Fakultät einer Zahl.

Common Lisp

(defun ringarea (r1 r2)
    (flet ((sq (x)
        (* x x)))
    (* pi (- (sq r1)
        (sq r2)))))

F# und OCaml

let ringarea (r1, r2) =
    let pi = 3.14 in
    let sq x = x*x in
    pi * (sq r1 - sq r2)

Haskell

ringArea :: (Floating a) => a -> a -> a
ringArea r1 r2 = pi * (sq r1 - sq r2) where
    sq x = x * x

Der Typ der Funktionen sq, ringArea ist polymorph und wird durch die Angabe der Typklasse Floating eingegrenzt. Die explizite Spezifikation des Typs ist optional und kann ebenso gut durch den Haskell-Compiler inferenziert werden. Pi ist in Haskell vordefiniert.

Joy

DEFINE

pi == 3.14;

sq == dup *;

ringarea == sq swap sq swap - pi *.

Joy benutzt die umgekehrte polnische Notation. Man beachte, dass hier alle Variablen Funktionen bezeichnen (auch pi ist eine Funktion).

Julia

pi = 3.14;
sq(x::Number) = x * x;
ringarea(R::Number, r::Number) = pi * (sq(R) - sq(r));

Python

from math import pi
squared = lambda x: x ** 2
ringarea = lambda r1, r2: pi * (squared(r1) - squared(r2))

Matlab

squared = @(x) x.^2;
ringarea = @(x,y) pi * (squared(x) - squared(y))

Scala

val squared: Double => Double = x => x * x
val ringArea: (Double, Double) => Double =
    (outerRadius, innerRadius) =>
        math.Pi * (squared(outerRadius) - squared(innerRadius))

Kotlin

val sq: (Double) -> Double = { x -> x * x }
val ringarea = { R: Double, r: Double -> PI * (sq(R) - sq(r)) }

Es gibt entweder die Möglichkeit, den Funktionstyp separat anzugeben (oben), oder die Parametertypen innerhalb des Lambdas zu definieren (unten).

Java

UnaryOperator<Double> sq = d -> d * d;
BinaryOperator<Double> ringArea = (outerRadius, innerRadius) -> Math.PI * (sq.apply(outerRadius) - sq.apply(innerRadius));

Scheme

(define (ring-area r1 r2)
    (define pi 3.14)
    (define (sq x)
        (* x x))
    (* pi (- (sq r1)
        (sq r2))))

SML

let
    val pi = 3.14
    val sq = fn (x: real) => x * x
in
    fun ringarea(R, r) = pi * (sq R - sq r)
end

Der Typ von x muss hier explizit angegeben werden, da ein SML97-Übersetzer sonst den Typ int inferieren würde. Das zugrundeliegende Problem ist das der Überladung von Operatoren; dieses Problem wurde erst mit Einführung von Typklassen gelöst, allerdings in Haskell und verwandten Sprachen.

Swift

let pi = 3.14
let square = { (x: Double) -> Double in x * x }
let ringarea = { (r1: Double, r2: Double) -> Double in
    pi * (square(r1) - square(r2))
}

XSLT

XSLT dient dem Transformieren von XML (insbesondere in XHTML) und hat zusammen mit XML stark an Bedeutung gewonnen. Sie ist funktional, wie Dimitre Novatchev gezeigt hat. Die im folgenden Beispiel definierte Funktion kehrt die Reihenfolge der Wörter einer Zeichenkette um. Typisch für funktionale Programmiersprachen ist der rekursive Aufruf. Der zweite Absatz zeigt, wie die Funktion verwendet wird.

<xsl:function name="str:reverse" as="xs:string">
  <xsl:param name="sentence" as="xs:string"/>
  <xsl:choose>
    <xsl:when test="contains($sentence, ' ')">
      <xsl:sequence select="concat(str:reverse(
        substring-after($sentence, ' ')),
        ' ',
        substring-before($sentence, ' '))"/>
    </xsl:when>
    <xsl:otherwise>
      <xsl:sequence select="$sentence"/>
    </xsl:otherwise>
  </xsl:choose>
</xsl:function>

<xsl:template match="/">
<output>
  <xsl:value-of select="str:reverse('DOG BITES MAN')"/>
</output>
</xsl:template>