Funktion höherer Ordnung 📖 Wikipedia

Dieser Artikel oder nachfolgende Abschnitt ist nicht hinreichend mit Belegen (beispielsweise Einzelnachweisen) ausgestattet. Angaben ohne ausreichenden Beleg könnten demnächst entfernt werden. Bitte hilf Wikipedia, indem du die Angaben recherchierst und gute Belege einfügst.

Eine Funktion höherer Ordnung (englisch higher-order function) 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 um. Diese Transformation hat ihre Grundlage darin, dass für beliebige Mengen ${\displaystyle A,B,C}$ die Funktionenräume ${\displaystyle A\times B\to C}$ und ${\displaystyle A\to (B\to C)}$ miteinander identifiziert werden können.

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

${\displaystyle f\colon \mathbb {R} \to (\mathbb {N} \to \mathbb {R} ),x\mapsto (m\mapsto x+m)}$

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

Aus dem Lambda-Kalkül stammt der K-Kombinator ${\displaystyle K=(x\mapsto (y\mapsto x))}$. ${\displaystyle (K(x))(y)}$ ist für alle ${\displaystyle y}$ 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 ${\displaystyle f:(A\to \mathbb {K} )\to \mathbb {K} }$ mit ${\displaystyle \mathbb {K} \in \{\mathbb {R} ,\mathbb {C} \}}$ ist ${\displaystyle A\to \mathbb {K} }$ ein ${\displaystyle \mathbb {K} }$-Vektorraum und daher ist ${\displaystyle f}$ ein Funktional.

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).

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]

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

In[1]:= Nest[# + 3 &, 7, 2]
Out[1]:= 13

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