Funktionen höherer Ordnung

Funktionale Programmierung ist ein Programmierparadigma, das Datenverarbeitung als Auswertung mathematischer Funktionen behandelt. Der Gegensatz dazu ist imperative Programmierung, die den Schwerpunkt auf Zustandsänderungen legt und die den derzeit am häufigsten verwendeten Programmiersprachen zugrunde liegt.

In funktionalen Programmiersprachen sind Funktionen ein wichtiges Konzept. Die Strukturierung des Programmcodes erfolgt mit Hilfe von Funktionen. Deshalb werde ich hier eine Reihe von Artikel veröffentlichen, die sich mit Funktionen in funktionalen Programmierspachen beschäftigen.

Funktionen höherer Ordnung

In funktionalen Programmiersprachen können Funktionen als Parameter an andere Funktionen übergeben oder als Rückgabewert verwendet werden. Solche Funktionen nennt man Funktionen höherer Ordnung.

Delegates ermöglichen es, dass man auch in C# Funktionen höherer Ordnung entwickeln kann. In der .NET-Klassenbibliothek finden sich einige Beispiele dafür, z.B. hat die Klasse System.Collections.Generic.List<T> eine Methode Sort, die als einzigen Parameter einen Delegate erwartet, der den Vergleich durchführen soll. Auch in LINQ gibt es einige Extension-Methods, die Delegates als Parameter bekommen.

Map, Filter und Fold

In funktionalen Programmiersprachen werden die drei Funktionen map, filter und fold häufig verwendet, um mit Listen und ähnlichen Datenstrukturen zu arbeiten. Alle drei Funktionen erwarten neben einer Liste eine Funktion als Parameter. Damit handelt es sich um Funktionen höherer Ordnung.

Map

Map wendet die angegebene Funktion auf jedes Element der Liste an und gibt eine Liste der Ergebnisse zurück. LINQ kennt die Extension-Method Select, die IEnumerable<T> erweitert und etwas Ähnliches macht:

[[code]]czo4OTpcInZhciBudW1iZXJzID0gbmV3W10geyAxLCAyLCAzLCA0LCA1IH07DQp2YXIgZG91YmxlZE51bWJlcnMgPSBudW1iZXJzLlN7WyYqJl19ZWxlY3QgKHggPT4geCAqIHgpO1wiO3tbJiomXX0=[[/code]]

In F# sieht das so aus:

let numbers = [1; 2; 3; 4; 5]
let doubledNumbers = List.map (fun x -> x * x) numbers

let ist das wichtigste Schlüsselwort für das Programmieren in F#. Es wird verwendet, um Daten, berechnete Werte, Funktionen und Prozeduren zu definieren. Links steht üblicherweise der Bezeichner. Nach dem Gleichheitszeichen folgt ein Ausdruck.

Die Zeile let numbers = [1; 2; 3; 4; 5] weist dem Namen “numbers” die Liste [1; 2; 3; 4; 5] als Wert zu. In F# wird eine Liste in eckigen Klammern eingeschlossen und die einzelnen Listenelemente werden durch einen Strichpunkt (Semikolon) getrennt.

Die zweite Zeile ruft die Funktion map des Moduls List auf. Man sieht, dass es nicht notwendig ist, die Parameter in Klammern anzugeben. Der erste Parameter ist die Funktion, die auf jedes Listenelement angewandt werden soll. In unserem Beispiel ist das die anonyme Methode fun x -> x * x. In F# wird eine anonyme Methode mit dem Schlüsselwort fun deklariert. Danach folgen die Funktionsargumente und nach dem Pfeil folgt der Funktionskörper. Der zweite Parameter ist die Liste “numbers”. Das Ergebnis wird an den Namen “doubledNumbers” gebunden.

Filter

Mit filter lässt sich eine Liste nach einem bestimmten Kriterium filtern. Das Kriterium wird als Funktion angegeben, die true für alle Elemente zurückgeben soll, die in die Ergebnisliste aufgenommen werden sollen. Das Äquivalent in LINQ heißt Where.

var numbers = new[] { 1, 2, 3, 4, 5 };
var evenNumbers = numbers.Where (x => (x % 2) == 0);

Hier wieder das Beispiel in F#:

let numbers = [1; 2; 3; 4; 5]
let evenNumbers = List.filter (fun x -> (x % 2) = 0) numbers

An diesem Beispiel sieht man, dass Lambda-Ausdrücke und anonyme Methoden nicht immer besser lesbar sind. Um die Lesbarkeit zu erhöhen, können wir die obigen Beispiele umschreiben:

In C#:

bool IsEven (int x)
{
    return (x % 2) == 0;
}
 
var numbers = new [] { 1, 2, 3, 4, 5 };
var evenNumbers = numbers.Where (IsEven);

Und in F#:

let IsEven x = (x % 2) = 0
let numbers = [1; 2; 3; 4; 5]
let evenNumbers = List.filter IsEven numbers

Die erste Zeile definiert die Funktion IsEven, die einen Parameter x akzeptiert. Nach dem ersten Gleichheitszeichen folgt der Funktionskörper: (x % 2) = 0. Dieser Ausdruck berechnet den Rest der Division von x durch 2 und vergleicht ihn mit 0. Sowohl beim let-Binding als auch beim Vergleich wird in F# ein einzelnes Gleichheitszeichen verwendet.

Fold

Fold berechnet einen akkumulierten Wert über alle Elemente einer Liste. Die Funktion gibt an, wie ein neuer akkumulierter Wert aus dem alten Wert und einem Listenelement ermittelt wird. Das LINQ-Äquivalent ist Aggregate.

var numbers = new[] { 1, 2, 3, 4, 5 };
var sum = numbers.Aggregate (0, (s, x) => s + x);

Dieses Beispiel berechnet die Summe der Zahlen im Array. Um besser zu verstehen, wie Fold funktioniert, hier die Einzelschritte:

Bei Aufruf: s = 0, Liste: 1, 2, 3, 4, 5

1. s = 0 + 1, Liste: 2, 3, 4, 5

2. s = (0 + 1) + 2, Liste: 3, 4, 5

3. s = ((0 + 1) + 2) + 3, Liste: 4, 5

4. s = (((0 + 1) + 2) + 3) + 4 = 10, Liste: 5

5. s = ((((0 + 1) + 2) + 3) + 4) + 5 = 15, Liste: -

Die Variable sum im obigen Beispiel hat also den Wert ((((0 + 1) + 2) + 3) + 4) + 5 = 15.

Hier in F#:

let numbers = [1; 2; 3; 4; 5]
let sum = List.fold (fun s x -> s + x) 0 numbers

Es gibt in F# die Möglichkeit, den Operator + als Funktion anzugeben. Statt 4 + 9 kann man also (+) 4 9 schreiben. Damit kann im obigen Beispiel die letzte Zeile so geschrieben werden:

let sum = List.fold (+) 0 numbers

Es gibt zwei verschiedene Arten von Folds: left Fold und right Fold. In früheren F#-Versionen gab es die zwei Funktionen List.fold_left und List.fold_right. Diese wurden jedoch umbenannt und heißen jetzt fold (left fold) und foldBack (right fold). LINQs Aggregate-Funktion arbeitet wie ein left Fold.

Fazit

Funktionen höherer Ordnung sind ein wichtiges Mittel in der funktionalen Programmierung für die Wiederverwendung von Code. Gemeinsam mit anderen Konzepten ermöglichen sie den deklarativen Stil der funktionalen Programmierung.