Funktion höherer Ordnung

Vorlage:Hinweisbaustein Eine Funktion höherer Ordnung () ist in der Informatik eine Funktion, die Funktionen als Argumente erhält und/oder Funktionen als Ergebnis liefert. Der Begriff wird insbesondere im Lambda-Kalkül verwendet, der theoretischen Grundlage der Funktionalen Programmierung.

Der Curry-Operator ist ein Beispiel für eine Funktion höherer Ordnung. Er wandelt Funktionen mit mehreren Argumenten in mehrere einparametrige Funktionen umwandelt. Diese Transformation hat ihre Grundlage darin, dass für beliebige Mengen <math>A,B,C</math> die Funktionenräume <math>A \times B \to C</math> und <math>A \to (B \to C)</math> miteinander identifiziert werden können.

Folgende Funktion stellt ein Beispiel für eine Funktion höherer Ordnung dar:

<math>f\colon \mathbb{R} \to (\mathbb{N} \to \mathbb{R}), x \mapsto (m \mapsto x+m)</math>

Diese Funktion bildet jeden reellen <math>x</math>-Wert auf eine Funktion ab, die eine (übergebene) natürliche Zahl zu <math>x</math> addiert. Beispielsweise ist <math>f(10{,}5) = (m \mapsto 10{,}5+m)</math>. <math>m</math> wird wiederum auf <math>x+m</math> abgebildet. Beispielsweise ist <math>(f(10{,}5))(1) = 11{,}5</math>.

Aus dem Lambda-Kalkül stammt der K-Kombinator <math>K = (x \mapsto (y \mapsto x))</math>. <math>(K(x))(y)</math> ist für alle <math>y</math> konstant.

Ein bekanntes Beispiel für eine Funktion höherer Ordnung ist der Differentialoperator, weil er Funktionen auf Funktionen abbildet (Ableitung und Stammfunktion). Weitere wichtige Beispiele sind die so genannten Distributionen. Im Fall <math>f: (A \to \mathbb{K}) \to \mathbb{K}</math> mit <math>\mathbb{K} \in \{\R,\Complex\}</math> ist <math>A \to \mathbb{K}</math> ein <math>\mathbb{K}</math>-Vektorraum und daher ist <math>f</math> ein Funktional.

Beispiel aus der funktionalen Programmierung

In den meisten funktionalen Programmiersprachen, wie z. B. Haskell, ist die Funktion höherer Ordnung map definierbar. Sie erhält als Argument eine Funktion f und gibt eine Funktion zurück, die f auf jedes Element einer übergebenen Liste anwendet. Es ist zu beachten, dass map Funktionen beliebigen Typs als Argument erhalten kann (angedeutet durch die Typvariablen a und b).

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

map (\x -> x ^ 2) [1, 2, 3, 4] -- wird ausgewertet zu [1, 4, 9, 16] </syntaxhighlight>

In einer multiparadigmatischen Programmiersprache wie Wolfram Language kann eine Funktion höherer Ordnung folgendermaßen aussehen:

<syntaxhighlight lang="mathematica"> In[1]:= Nest[# + 3 &, 7, 2] Out[1]:= 13 </syntaxhighlight>

Weblinks

• Simon Thompson: Type Theory and Functional Programming. (PDF; 1,3 MB)