imported>NDG: Änderungen von ~2025-61603-6 (Diskussion) wurden auf die letzte Version von ~2025-146076 zurückgesetzt: Test-Edit (bitte die Spielwiese nutzen)

2025-09-15T18:43:37Z

Änderungen von ~2025-61603-6 (Diskussion) wurden auf die letzte Version von ~2025-146076 zurückgesetzt: Test-Edit (bitte die Spielwiese nutzen)

Neue Seite

'''Funktionale Programmierung''' ist ein [[Programmierparadigma]], in dem [[Funktion (Programmierung)|Funktionen]] nicht nur definiert und angewendet werden können, sondern auch wie Daten miteinander verknüpft, als Parameter verwendet und als Funktionsergebnisse auftreten können. Dadurch kann ein funktionales Programm sehr weitreichend neue Berechnungsvorschriften zur Laufzeit zusammensetzen und anwenden. [[Programmiersprache]]n, die funktionale Programmierung ermöglichen, werden als funktionale Programmiersprachen bezeichnet.

Die funktionale Programmierung entspringt der mathematischen Grundlagenforschung. In den 1930er Jahren entwickelte [[Alonzo Church]] den [[Lambda-Kalkül]] als Instrument, um das Entscheidungsproblem zu bearbeiten und dazu den Begriff der berechenbaren Funktion zu definieren. Der Lambda-Kalkül selbst beschäftigt sich nicht mit bestimmten Funktionen, sondern ist nur ein Regelwerk dafür, wie die Anwendung von Funktionen auf ihre Argumente erfolgt und wie dabei mit freien und gebundenen Variablen verfahren wird.

Die besonderen Eigenschaften der funktionalen Programmierung ermöglichen es, auf die in der [[Prozedurale Programmierung|prozeduralen Programmierung]] benötigten Zustandsänderungen außerhalb eines Unterprogrammes, die auch [[Wirkung (Informatik)|Seiteneffekte]] genannt werden, zu verzichten, falls sie überhaupt möglich sind. Der Verzicht auf die Seiteneffekte vereinfacht auf der einen Seite die semantische Analyse eines Computerprogramms erheblich und eröffnet auf der anderen Seite weitreichende Möglichkeiten zur regelbasierten, algebraischen Programmtransformation und -synthese. Daraus ergibt sich die erhebliche praktische Bedeutung der funktionalen Programmierung für die Informatik.

Eine weitere Konsequenz ist, dass es in funktionaler Programmierung besonders einfach ist, Algorithmen ohne Berücksichtigung der Beschaffenheit der bearbeiteten Datenobjekte zu beschreiben und dadurch generischen Programmcode zu erstellen. Viele funktionale Verfahren sind so generisch, dass sie seit den 1950er Jahren keiner Anpassung unterworfen werden mussten.

Die erste bedeutende, in funktionaler Programmierung erstellte Software ist der von [[John McCarthy]] im Jahr 1958 erstellte, metazirkuläre [[Lisp]]-Interpreter mit Namen [[eval]], der die Semantik von LISP aus fünf einfachen Funktionen zusammengesetzt darstellt. Er findet auf einer DIN-A4-Seite Platz und ist bis heute konzeptionelle Grundlage für die Implementierung der meisten Programmiersprachen.

== Definition ==
Die funktionale Programmierung ist durch folgende Eigenschaften gekennzeichnet:

# Computerprogramme werden als Funktionen verstanden, die für eine Eingabe eine Ausgabe liefern, die nur von dieser abhängig ist.
# Funktionen werden nicht als Abfolge von Anweisungen dargestellt, sondern als ineinander verschachtelte Funktionsaufrufe.
# Funktionen sind gegenüber allen anderen Datenobjekten gleichberechtigt. Das bedeutet, dass sie als Parameter in Funktionen eingehen dürfen und ebenso als Berechnungsergebnisse aus Funktionen hervorgehen können. Insbesondere können Funktionen wie andere Datenobjekte zur Laufzeit erstellt werden oder entfallen.
# Eine Funktion kann auf Variablen Bezug nehmen, die dem Kontext angehören, in dem ihre Erstellung erfolgt ist. Dies kann sie auch dann noch tun, wenn sie den Kontext verlassen hat. Die Belegung der Variablen zum Zeitpunkt des Verlassens dieses Kontextes wird dann innerhalb dieser Funktion eingefroren. Eine so entstandene Funktion heißt Closure und die eingefrorenen Variablenbelegungen heißen Closure-Variablen.
# Funktionsdefinitionen können insbesondere bei Funktionsanwendungen ohne explizite Namensgebung literal in der Stellung des Funktionssymbols stehen. Solche Funktionen heißen anonym und werden oft salopp „Lambdas“ genannt.

== Funktionale Programmiersprachen ==
Eine ''rein funktionale Programmiersprache'' wäre strikt [[Isomorphismus|isomorph]] zum [[Lambda-Kalkül]]. Das gilt mit minimalen Einschränkungen beispielsweise für die [[esoterische Programmiersprache]] ''unlambda''.

Wichtige Vertreter funktionaler Programmiersprachen sind die Lisp-Programmiersprachenfamilie und die rein funktionale Programmiersprache Haskell.
Vornehmlich zur funktionalen Programmierung gedachte Sprachen sind:
* [[Clojure]] (2007)
* [[Elixir (Programmiersprache)|Elixir]] (2011)
* [[Erlang (Programmiersprache)|Erlang]] (1987)
* [[F-Sharp|F#]] (2002)
* [[Haskell (Programmiersprache)|Haskell]] (1990)
* [[LISP]] (1958)
* [[ML (Programmiersprache)|ML]] (1973)
* [[OCaml]] (1996)
* [[Scala (Programmiersprache)|Scala]] (2004).

Fast alle in jüngster Zeit entstandenen Programmiersprachen gestatten funktionale Programmierung. Sprachen, die funktionale Programmierung neben anderen Paradigmen ermöglichen, sind zum Beispiel Perl, ECMAScript, Dylan, Ruby und Visual Basic.NET. Python hat Einschränkungen bei der Formulierung von anonymen Funktionen. Viele eigentlich objektorientierte Sprachen wurden in jüngsten Versionen aufgerüstet wie C++ (ab Version 11), [[Object Pascal|Delphi]] (ab Version 2009) oder Java (ab Version 8). Allerdings leidet darunter die Syntax, sodass die Kompaktheit von LISP oder Haskell nicht erreicht wird.

Populäre Programmiersprachen, die keinerlei Möglichkeiten zur funktionalen Programmierung bieten, sind zum Beispiel C und VBA.

== Mathematische Konzepte ==
Die allgemeingültigen Konzepte der funktionalen Programmierung entstammen der Mathematik der 1930er und 1940er 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. Kategorientheoretisch (Kategorientheorie) sind Datentypen Objekte und Funktionen Morphismen, die zwischen diesen abbilden und für die die gewöhnliche Funktionskomposition als zweistellige, assoziative Verknüpfung und die Identitäts-Abbildung als neutrales Element definiert ist. Damit bilden die Funktionen eine „[[Gruppe (Mathematik)|Gruppe]] ohne das Gesetz vom inversen Element“.

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

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

=== Katamorphismen ===
Sei <math>B</math> ein Datentyp, <math>b\in B</math> ein Wert und <math>\otimes \colon A\times B \to B</math> eine Abbildung. Dann ist durch

:<math>
\begin{align}
h \colon A^*&\to B \\
Nil&\mapsto b \\
Cons(a,L)&\mapsto a\otimes h(L)
\end{align}
</math>

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

:<math>
\begin{align}
&x := b \\
&For\;i := Length(L) \text{ Downto } 1 \text{ Do} \\
&\;\;x := L_i \otimes x \\
&End \\
&Return(x) \\
\end{align}
</math>

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

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

Ist die Operation <math>h</math> assoziativ mit dem neutralen Element <math>\emptyset</math>, dann ist der Katamorphismus <math>(|\emptyset,h|)</math> die eindeutige Erweiterung der Operation <math>h</math> 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 <math>f\circ g</math> bereits implementiert, so lässt sich die Komposition <math>\bigodot_{i=1}^n f_i</math> von <math>n</math> Funktionen als <math>(|id,\circ|)</math> darstellen (dabei ist <math>id</math> die identische Abbildung).

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

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

:<math>
\begin{align}
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{align}
</math>

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

=== Hylomorphismen ===
Sei <math>(|z,f|)</math> ein Katamorphismus und <math>[(p,g)]</math> ein Anamorphismus. Dann ist die Abbildung <math>(|z,f|)\circ[(p,g)]</math> ein sogenannter ''Hylomorphismus'' ({{grcS|ὕλη|hýlē|de=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.<ref name="Krusenotto">Patrick M. Krusenotto: ''Funktionale Programmierung und Metaprogrammierung.'' Springer, Wiesbaden 2016, S. 217ff, S. 244 ff.</ref> 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.<ref name="Krusenotto" /> Der Hylomorphismus <math>!=(|1,\times|)\circ([(i\mapsto (i<1),i \mapsto [i,i-1])]</math>, der den Katamorphismus <math>(|1,\times|)</math> zur Berechnung eines Zahlenprodukts mit dem oben genannten Anamorphismus <math>\iota</math> kombiniert, berechnet die Fakultät einer Zahl.

== Abgrenzung von imperativer Programmierung ==
Im Gegensatz zu [[Imperative Programmierung|imperativen Programmen]], die aus ''Rechenanweisungen'' bestehen, sind funktionale Programme eine Menge von (Funktions)-''Definitionen'', die mathematisch eine [[partielle Abbildung]] von Eingabedaten auf Ausgabedaten sind und gleichzeitig selbst aus Funktionsaufrufen zusammengesetzt sind.

Ein typisches Beispiel ist die Berechnung der [[Fakultät (Mathematik)|Fakultät]] n! einer Zahl n (n! = 1 · 2 · 3 · … · n), hier eine imperative Lösung:
'''Eingabe:'''
Zahl n
'''Ausgabe:'''
Zahl b (= 1 · 2 · 3 · … · n)
'''Algorithmus:'''
b := 1 (Zuweisung)

'''solange''' n > 0 '''führe aus'''
b := n · b
n := n − 1

''Ausgabe:'' b

Charakteristisch für die imperative Programmierung sind hier die Zuweisungen (Änderung von Werten, durch das Symbol <code>:=</code> im [[Pseudocode]] repräsentiert). Zwar berechnet der Algorithmus die Fakultät der Zahl n, aber die Korrektheit dieses Rechenweges ist nicht offensichtlich.

Nun kann man die Fakultät jedoch auch mithilfe von [[Rekursion|rekursiven Funktionen]] definieren, was zur ''funktionalen'' Lösung führt.
<math>n! = f(n) = \begin{cases} n \cdot f(n-1) &\mathrm{f\ddot ur}\ \ n > 0\\ 1 &\mathrm{f\ddot ur}\ \ n = 0\end{cases}</math>

'''Funktion f(n):'''
'''wenn''' n > 0 '''dann''':
''Ausgabe'': n · f(n - 1)
'''sonst wenn''' n = 0 '''dann''':
''Ausgabe'': 1

Die funktionale Programmierung kommt also ohne Schleifen und Zuweisungen aus, benötigt dafür aber Rekursion.

== Lambda-Kalkül ==
Die theoretische Grundlage der funktionalen Programmierung ist der [[Lambda-Kalkül|λ-Kalkül]] (Lambda-Kalkül) von [[Alonzo Church]]. Jeder Ausdruck und jeder Wert wird dabei als auswertbare Funktion betrachtet, so dass die ganze Programmierung auf der Übergabe von Funktionen als Parameter an Funktionen fußt.

Der Lambda-Kalkül erlaubt es, vollständige Teilausdrücke separat auszuwerten. Dies ist der wichtigste Vorteil gegenüber der imperativen Programmierung. Dieses Konzept vereinfacht die [[Verifikation#Informatik|Programmverifikation]] und [[Programmoptimierung]], beispielsweise die Überführung der Programme in eine [[Parallele Programmierung|parallel auswertbare Form]].

== Typsystem ==
Historisch ist [[Lisp]] als die erste funktionale Programmiersprache aufzufassen. Sprachen der LISP-Familie (wie auch [[Scheme]]) sind [[Dynamische Typisierung|dynamisch typisiert]]. Seit der Entwicklung von [[Standard ML|Standard-ML (SML)]] konzentriert sich die Forschung auf dem Gebiet der funktionalen Programmiersprachen auch auf [[Statische Typisierung|statisch typisierte]] Sprachen, insbesondere auf solche, die das Typsystem nach [[Hindley-Milner|Hindley und Milner]] verwenden. Der Vorteil dieses Typsystems ist die Verfügbarkeit von [[Polymorphie (Programmierung)|parametrischem Polymorphismus]] zusammen mit [[Typinferenz]]: Programmierer müssen die Typen ihrer Funktionen und anderen Werte nicht angeben, sondern bekommen sie ''gratis'' vom Übersetzer ausgerechnet, der zugleich noch während der Übersetzung Typfehler monieren kann. Dies wird allgemein als wesentlicher Vorteil gegenüber dynamisch typisierten Sprachen (Lisp, [[Python (Programmiersprache)|Python]]) aufgefasst, die zwar ebenfalls keine Typannotationen benötigen (im Gegensatz z. B. zu [[Java (Programmiersprache)|Java]] oder [[C (Programmiersprache)|C]]), dafür aber Typfehler erst zur Laufzeit anmahnen können. Letzteres hat jedoch wiederum den Vorteil einer breiteren Anwendbarkeit bereits definierter Funktionen auf ggf. zum Entwicklungszeitpunkt noch nicht vorhergesehene neue Einsatzgebiete.

Das Hindley-Milner-System erlaubt allerdings nur [[Polymorphismus ersten Ranges]]; Erweiterungen für Polymorphismus zweiten und allgemein k-ten Ranges sind inzwischen in dem [[Haskell (Programmiersprache)|Haskell]]-Übersetzer ''GHC'' als Erweiterungen verfügbar, bedingen jedoch wieder explizite Annotationen (Typinferenz ab Polymorphismus zweiten Ranges ist [[Entscheidbarkeit|unentscheidbar]]).

== Rein funktionale Programmiersprachen ==
Rein funktionale Programmiersprachen fassen Programme als mathematische Funktion auf. Es gibt ''keine Zustandsvariablen'', die während einer Berechnung geändert werden. Um erwünschte Wirkungen (Benutzerinteraktion, Eingabe/Ausgabe-Operationen) beschreiben zu können, sind meist besondere Vorkehrungen notwendig. Die meisten funktionalen Programmiersprachen ([[Standard ML]], [[Caml]], [[Scheme]] und weitere) erlauben allerdings solche Wirkungen und sind daher keine reinen funktionalen Programmiersprachen.

Um Programmierung auch mit Wirkungen zu erlauben, ohne dabei zu einer sog. unreinen (englisch ''impure'') Sprache zu werden, wird in der Sprache [[Haskell (Programmiersprache)|Haskell]] das aus der [[Kategorientheorie]] stammende Konzept der [[Monade (Informatik)|Monaden]] verwendet (insbesondere von [[Eugenio Moggi]] und [[Philip Wadler]]), welches Wirkbehaftung durch [[Parametrischer Typ|parametrische Typen]] ausdrückt und somit das [[Typsystem]] dazu zwingt, zwischen Ausdrücken mit und Ausdrücken ohne Wirkungen zu unterscheiden. Auch in [[Clean (Programmiersprache)|Clean]] und [[Mercury (Programmiersprache)|Mercury]] wird das Typsystem verwendet, um solche Wirkungen zu kennzeichnen. Dort benutzt man allerdings das Konzept der „Uniqueness“-Typen.

== Funktionen höherer Ordnung ==
Man unterscheidet Funktionen ''erster Ordnung'' und Funktionen ''höherer Ordnung''. Bei Funktionen höherer Ordnung sind Funktionen selbst Werte. Dies erlaubt es insbesondere, Funktionen als Ergebnisse oder Argumente anderer Funktionen zu verwenden. Ein klassisches Beispiel ist der [[Differentialrechnung#Ableitungsregeln|Ableitungsoperator]], dessen Darstellbarkeit in Lisp obligatorisch für das Design dieser Sprache war: Eingabe ist eine differenzierbare Funktion, Ausgabe ist die Ableitung dieser Funktion.

Ein einfacheres Standardbeispiel für eine Funktion höherer Ordnung ist die Funktion <code>map</code>, welche als Eingabe eine Funktion <code>f</code> und eine Liste <code>l</code> erhält und die modifizierte Liste zurückgibt, die dadurch entsteht, dass die Funktion <code>f</code> auf jedes Element der Liste <code>l</code> angewendet wird. Definition von <code>map</code> in [[Haskell (Programmiersprache)|Haskell]]:

<syntaxhighlight lang="haskell">
map f [] = []
map f (x:xs) = f x : map f xs
</syntaxhighlight>

: In der ersten Zeile wird das Ergebnis für eine leere Liste [] zurückgegeben; die zweite Zeile wendet die Funktion <code>f</code> auf das erste Listenelement ''x'' an und führt dann einen [[Rekursion]]sschritt für die restliche Liste ''xs'' durch.

== {{Anker|Bedarfsauswertung}} Bedarfsauswertung und strikte Auswertung ==
Funktionale Sprachen kann man auch nach ihrer [[Auswertung (Informatik)|Auswertungsstrategie]] unterscheiden: Bei ''strikter Auswertung'' (englisch ''eager'' bzw. ''strict evaluation'') werden die Argumente von Funktionen zuerst ausgewertet. Dagegen werden bei der ''nicht-strikten Auswertung'' zunächst die Ausdrücke als Ganzes übergeben und dann ausgewertet.

Man kann zum Beispiel den Ausdruck <math>(3+5)^2</math> auf zwei Arten berechnen:

* <math>(3+5)^2 = 8^2 = 8 \cdot 8 = 64</math>
* <math>(3+5)^2 = (3+5)\cdot(3+5) = 8 \cdot 8 = 64</math>

Im ersten Fall wird der Ausdruck strikt ausgewertet, da erst die Argumente der Potenz-Funktion berechnet werden. Im zweiten Fall werden diese Argumente erst bei Bedarf ausgewertet, also nachdem die Potenzfunktion aufgelöst wurde (nicht-strikte Auswertung).

Eine Variante der nicht-strikten Auswertung ist die ''[[Bedarfsauswertung]]'' (englisch ''lazy evaluation''), bei der Ausdrücke erst ausgewertet werden, wenn deren Wert in einer Berechnung benötigt wird. Dadurch lassen sich z. B. unendlich große [[Datenstruktur]]en (die Liste aller natürlicher Zahlen, die Liste aller Primzahlen etc.) definieren und bestimmte Algorithmen vereinfachen sich.

Manche Berechnungen lassen sich mit strikter Auswertung, andere mit Bedarfsauswertung effizienter ausführen. Terminiert die strikte Auswertung eines Ausdruckes, so terminiert auch die nicht-strikte Auswertung. Hintergrund hiervon ist die [[Konfluenz (Informatik)|Konfluenz]]-Eigenschaft des jeder funktionalen Sprache zugrundeliegenden [[Lambda-Kalkül|λ-Kalküls]], die aussagt, dass das Ergebnis der Berechnung nicht von der Reihenfolge der Auswertung abhängt.

== Funktionale Algorithmen und Datenstrukturen ==
[[Algorithmus|Algorithmen]] geben vorteilhafte Verfahren für die Lösung wichtiger Probleme an (z. B. [[Sortieren]]) und sind in der Regel gut analysiert, so dass ein Entwickler auf bewährte, einschätzbare Lösungen zurückgreifen kann. Gleiches leisten [[Datenstruktur]]en für die Organisation von Daten. Sammlungen von guten Algorithmen und Datenstrukturen haben somit eine große praktische Bedeutung.

Der Verzicht auf Zuweisungen führt dazu, dass etliche klassische Algorithmen und Datenstrukturen, die regen Gebrauch von dieser Möglichkeit machen, so nicht für funktionale Sprachen verwendet werden können und nach neuen Lösungen gesucht werden muss.

[[Chris Okasaki]] schreibt:

{{Zitat
|Text=Auch wenn die meisten dieser Bücher [über Datenstrukturen] behaupten, dass sie unabhängig von einer bestimmten Programmiersprache sind, so sind sie leider nur sprachunabhängig im Sinne [[Henry Ford II|Henry Fords]]: Programmierer können jede Programmiersprache benutzen, solange sie imperativ ist.}}

Gerade rein funktionale Datenstrukturen sind von ihrer Natur her anders als die gewohnten Datenstrukturen, die meist nur eine Version ihrer Daten verwalten (ephemere Datenstrukturen), wohingegen funktionale Datenstrukturen mehrere Versionen verwalten (persistente Datenstrukturen).

== Beispiele ==
Folgende Programme definieren eine Funktion <code>ringarea</code>, die die Fläche berechnet, die zwischen den beiden konzentrischen Kreisen mit den [[Radius|Radien]] <code>R</code> und <code>r</code> bzw. <code>r1</code> und <code>r2</code> mit gemeinsamen Mittelpunkt liegt, entsprechend dem mathematischen Ausdruck: <math>A = \pi \cdot (r_1^2-r_2^2)</math>. Dazu werden die Konstante <code>pi</code> und die Hilfsfunktion <code>sq</code> definiert. Diese werden von <code>ringarea</code> dann für die Berechnung benutzt. Anmerkung: Wir setzen voraus, dass <math>r_1\geq r_2</math> gilt.

=== [[Common Lisp]] ===
<syntaxhighlight lang="common-lisp">
(defun ringarea (r1 r2)
(flet ((sq (x)
(* x x)))
(* pi (- (sq r1)
(sq r2)))))
</syntaxhighlight>

=== [[F-Sharp|F#]] und [[OCaml]] ===
<syntaxhighlight lang="ocaml">
let ringarea r1 r2 =
let pi = 3.14 in
let sq x = x *. x in
pi *. (sq r1 -. sq r2)
</syntaxhighlight>

=== [[Haskell (Programmiersprache)|Haskell]] ===
<syntaxhighlight lang="haskell">
ringArea :: (Floating a) => a -> a -> a
ringArea r1 r2 = pi * (sq r1 - sq r2) where
sq x = x * x
</syntaxhighlight>

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

=== [[Joy (Programmiersprache)|Joy]] ===
:; <code>DEFINE</code>
:: <code>pi == 3.14;</code>
:: <code>sq == dup *;</code>
:: <code>ringarea == sq swap sq swap - pi *.</code>

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

=== [[Julia (Programmiersprache)|Julia]] ===
<syntaxhighlight lang="julia">
pi = 3.14;
sq(x::Number) = x * x;
ringarea(R::Number, r::Number) = pi * (sq(R) - sq(r));
</syntaxhighlight>

=== [[Python (Programmiersprache)|Python]] ===
<syntaxhighlight lang="python">
from math import pi
squared = lambda x: x ** 2
ringarea = lambda r1, r2: pi * (squared(r1) - squared(r2))
</syntaxhighlight>

=== [[MATLAB|Matlab]] ===
<syntaxhighlight lang="matlab">
squared = @(x) x.^2;
ringarea = @(x,y) pi * (squared(x) - squared(y))
</syntaxhighlight>

=== [[Scala (Programmiersprache)|Scala]] ===
<syntaxhighlight lang="scala">
val squared: Double => Double = x => x * x
val ringArea: (Double, Double) => Double =
(outerRadius, innerRadius) =>
math.Pi * (squared(outerRadius) - squared(innerRadius))
</syntaxhighlight>

=== [[Kotlin (Programmiersprache)|Kotlin]] ===
<syntaxhighlight lang="kotlin">
val sq: (Double) -> Double = { x -> x * x }
val ringarea = { R: Double, r: Double -> PI * (sq(R) - sq(r)) }
</syntaxhighlight>
Es gibt entweder die Möglichkeit, den Funktionstyp separat anzugeben (oben), oder die Parametertypen innerhalb des Lambdas zu definieren (unten).

=== [[Java (Programmiersprache)|Java]] ===
<syntaxhighlight lang="java">
UnaryOperator<Double> sq = d -> d * d;
BinaryOperator<Double> ringArea = (outerRadius, innerRadius) -> Math.PI * (sq.apply(outerRadius) - sq.apply(innerRadius));
</syntaxhighlight>

=== [[Scheme]] ===
<syntaxhighlight lang="scheme" line="1">
(define (ring-area r1 r2)
(define pi 3.14)
(define (sq x)
(* x x))
(* pi (- (sq r1)
(sq r2))))
</syntaxhighlight>

=== [[Standard ML|SML]] ===
<syntaxhighlight lang="sml">
let
val pi = 3.14
val sq = fn (x: real) => x * x
in
fun ringarea(R, r) = pi * (sq R - sq r)
end
</syntaxhighlight>

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

=== [[Swift (Programmiersprache)|Swift]] ===
<syntaxhighlight lang="fsharp">
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))
}
</syntaxhighlight>

=== 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.<ref>{{Webarchiv|url=http://www.topxml.com/xsl/articles/fp | wayback=20081205113752 | text=The Functional Programming Language XSLT}}</ref> Die im folgenden Beispiel<ref>Aus der [https://www.w3.org/TR/2007/REC-xslt20-20070123/#stylesheet-functions W3C Recommendation XSL Transformations (XSLT) Version 2.0]</ref> 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.
<syntaxhighlight lang="xml">
<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>

</syntaxhighlight>

== Siehe auch ==
* [[International Conference on Functional Programming Contest]] (ICFP Contest)
* [[Algebraische Programmiersprache]]

== Literatur ==
* Chris Okasaki: ''Purely Functional Data Structures.'' Cambridge University Press, 1999, ISBN 0-521-66350-4.
* Patrick M. Krusenotto ''Funktionale Programmierung und Metaprogrammierung – Interaktiv in Common Lisp.'' Springer, 2016, ISBN 978-3-658-13743-4.
* Lothar Piepmeyer: ''Grundkurs funktionale Programmierung mit Scala.'' Hanser, 2010, ISBN 978-3-446-42092-2, S. 297.
* Fethi Rabhi, Guy Lapalme: ''Algorithms – A Functional Programming Approach.'' Addison-Wesley, 1999, ISBN 0-201-59604-0.

== Weblinks ==
{{Commonscat|Functional programming|Funktionale Programmierung}}
* [https://www.infosun.fim.uni-passau.de/cl/lehre/funcprog05/wasistfp.html ''Was ist funktionale Programmierung?''], Fakultät für Informatik und Mathematik der [[Universität Passau]]
* Amr Sabry: [https://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.27.7800 ''What is a Purely Functional Language?''] In: ''J. Functional Programming.'' 8(1), Januar 1998, S. 1–22.
* Carsten König'': [https://www.informatik-aktuell.de/entwicklung/programmiersprachen/was-ist-funktionale-programmierung.html Was ist funktionale Programmierung?]'', [[Informatik Aktuell (Magazin)|Informatik Aktuell]]
* Andre Schütz: [https://www.informatik-aktuell.de/entwicklung/programmiersprachen/funktionale-programmierung-mit-scala-herangehensweisen-und-konzepte.html ''Funktionale Programmierung mit Scala: Einführung''], [[Informatik Aktuell (Magazin)|Informatik Aktuell]]

== Einzelnachweise ==
<references />

[[Kategorie:Programmierparadigma]]

Funktionale Programmierung - Versionsgeschichte

imported>NDG: Änderungen von ~2025-61603-6 (Diskussion) wurden auf die letzte Version von ~2025-146076 zurückgesetzt: Test-Edit (bitte die Spielwiese nutzen)