Programmierung · Konzepte · Haskell

Was ist eine Funktion höherer Ordnung?

In den meisten Sprachen ist eine Funktion etwas, das man aufruft. In der funktionalen Programmierung ist eine Funktion auch ein Wert: Man kann sie in einer Variablen ablegen, an eine andere Funktion übergeben und eine als Ergebnis zurückbekommen. Eine Funktion höherer Ordnung ist genau die, die eines der beiden letzten Dinge tut. Dieser Leitfaden erklärt, was eine Funktion höherer Ordnung ist, warum map, filter und fold die klassischen Beispiele sind, wie sie Schleifen ersetzen und wie sie in Haskell aussehen.

Die kurze Definition

Eine Funktion höherer Ordnung ist eine Funktion, die eine oder mehrere Funktionen als Argument nimmt, eine Funktion als Ergebnis zurückgibt oder beides. Eine Funktion, die keines von beidem tut — die nur einfache Werte wie Zahlen oder Zeichenketten nimmt und zurückgibt — heißt Funktion erster Ordnung. Der Begriff „höhere Ordnung“ bedeutet schlicht, dass sie auf Funktionen arbeitet, so wie eine gewöhnliche Funktion auf Daten arbeitet.

Das funktioniert nur in einer Sprache, in der Funktionen Werte erster Klasse sind: Dinge, die man benennen, übergeben und zurückgeben kann, genau wie eine Ganzzahl. Haskell, JavaScript, Python, Swift und viele andere behandeln Funktionen so, und das macht Funktionen höherer Ordnung überhaupt erst möglich.

Die drei Klassiker: map, filter und fold

Fast jede funktionale Codebasis stützt sich auf drei Funktionen höherer Ordnung. Jede nimmt eine Funktion als Argument und wendet sie auf eine Sammlung an:

• map wendet eine Funktion auf jedes Element einer Liste an und gibt eine neue Liste der Ergebnisse zurück. map (+1) [1,2,3] ergibt [2,3,4] — die Funktion (+1) ist das Argument.
• filter behält nur die Elemente, für die eine Funktion wahr zurückgibt. filter even [1,2,3,4] ergibt [2,4] — hier ist even die übergebene Funktion.
• fold (auch reduce genannt) reduziert eine Liste auf einen einzigen Wert, indem es die Elemente paarweise verknüpft. foldr (+) 0 [1,2,3] addiert sie zu 6 — der Verknüpfungsschritt (+) ist das Funktionsargument.

In jedem Fall lieferst du das kleine Stück Logik — erhöhen, „ist gerade“, addieren — und die Funktion höherer Ordnung übernimmt das Durchlaufen der Liste. Du beschreibst, was mit jedem Element geschehen soll, nicht die Mechanik des Wie beim Durchlaufen.

Wie sie Schleifen ersetzen

In einer imperativen Sprache schriebe man eine Schleife mit Zähler, Akkumulator und explizitem Index. Dieselbe Absicht, mit einer Funktion höherer Ordnung ausgedrückt, passt in eine einzige Zeile, weil die Iteration bereits in map oder fold eingebaut ist. Deshalb stützt sich rein funktionaler Code, der veränderliche Schleifenzähler vermeidet, so stark auf diese Funktionen und auf Rekursion — beide zusammen decken die Arbeit ab, die anderswo Schleifen erledigen. List-Comprehensions sind oft eine lesbare Kurzform für dieselbe Kombination aus map und filter.

Eine Funktion zurückgeben: hier wird es mächtig

Die andere Hälfte der Definition — Funktionen, die Funktionen zurückgeben — ist genauso verbreitet. Eine Funktion kann eine neue, spezialisierte Funktion bauen und zurückgeben. Ein klassisches Beispiel ist ein „Multiplikator-Erzeuger“: Du gibst ihm eine Zahl, und er gibt eine Funktion zurück, die ihre Eingabe mit dieser Zahl multipliziert. Rufe ihn mit 3 auf, und du erhältst eine „mal drei“-Funktion, die du wie jede andere verwenden kannst. Der Erzeuger ist höherer Ordnung, weil sein Ergebnis selbst eine Funktion ist.

In Haskell ist das durch Currying in die Sprache eingewoben: Jede Funktion mit mehreren Argumenten ist in Wahrheit eine Kette von Funktionen mit je einem Argument, von denen jede die nächste zurückgibt. Deshalb funktioniert map (+1) — (+1) ist die Additionsfunktion mit einem bereits gelieferten Argument, die eine Funktion zurückgibt, die noch das andere erwartet. Diese partielle Anwendung sind Funktionen höherer Ordnung in Aktion, oft ohne dass man es bemerkt.

Funktionen höherer Ordnung in Haskell

Haskell macht die Idee in seinen Typsignaturen sichtbar. Der Typ von map wird als map :: (a -> b) -> [a] -> [b] geschrieben. Lies von links nach rechts: Das erste Argument (a -> b) ist selbst eine Funktion — das ist der Teil höherer Ordnung — gefolgt von einer Liste von a, die eine Liste von b erzeugt. Die Pfeile machen auf dem Papier sichtbar, dass eine Funktion übergeben wird. Dasselbe Muster erscheint in filter :: (a -> Bool) -> [a] -> [a] und in der gesamten Standardbibliothek.

Oft übergibst du diese Funktionen inline als Lambdas, kleine anonyme Funktionen, die mit einem Backslash geschrieben werden, etwa map (\x -> x * x) [1,2,3], um jedes Element zu quadrieren. Ob du eine benannte Funktion, einen Operatorabschnitt wie (*2) oder ein Lambda übergibst — es ist derselbe Mechanismus: eine Funktion, die als Wert in eine Funktion höherer Ordnung reist.

Warum sie wichtig sind

Funktionen höherer Ordnung erlauben es, die gemeinsame Form einer Berechnung herauszulösen — „mit jedem Element etwas tun“, „die passenden behalten“, „alle verknüpfen“ — und sie mit unterschiedlicher, eingesteckter Logik wiederzuverwenden. Das Ergebnis: weniger wiederholter Code, Code, der näher an seiner Absicht liest, und kleine, testbare, komponierbare Logikbausteine. Sie sind der Baustein, auf dem ein Großteil der funktionalen Programmierung von Haskell ausgedrückt wird, und kombiniert mit Haskells verzögerter Auswertung erlauben sie sogar, über konzeptionell unendliche Listen zu mappen und zu filtern.

Die ehrlichen Kompromisse

Funktionen höherer Ordnung erfordern etwas Eingewöhnung: Ein foldr oder eine Kette aus map . filter zu lesen ist eine Fertigkeit, und tief verschachtelte Lambdas können schwer nachvollziehbar werden. Funktionen überallhin zu übergeben kann zudem einen Stack-Trace weniger eindeutig machen, wenn etwas schiefgeht. Der Gewinn — deutlich weniger sich wiederholender Iterationscode und neu kombinierbare Logik — erklärt, warum sie sich weit über funktionale Sprachen hinaus verbreitet haben, bis in das alltägliche JavaScript, Python und Swift. Mit Maß eingesetzt, machen sie Code kürzer und klarer; übertrieben eingesetzt, können sie ihn verschleiern wie jedes andere Werkzeug.

Häufig gestellte Fragen

Stöbere in weiteren klaren Erklärungen in unserem Leitfaden-Index.