Funktionen höherer Ordnung

Funktionen höherer Ordnung sind die Pendants zu First-Class Funktionen, denn Funktionen höherer Ordnung können Funktionen als Argument annehmen oder als Ergebnis zurückgeben.

Funktionen höherer Ordnung

Die Klassiker: map, filter und fold

Jede Programmiersprache, die das Programmieren im funktionalen Stil erlaubt, unterstützt zu mindest die drei Funktionen map, filter und fold. Während map eine Funktion auf jedes Element einer Liste anwendet, entfernt filter die Elemente einer Liste, die einem Prädikat nicht genügen. fold ist die mächtigste der drei Funktionen. fold wendet eine binäre Operation sukzessive auf alle Paare einer Liste an, bis diese Liste auf ein Element reduziert ist.

Das geht auch anschaulicher:

Die Namensvariationen

Die Aussage, das jede Programmiersprache, die das Programmieren im funktionalen Stil erlaubt, zu mindest die drei Funktionen map, filter und fold unterstützt, gilt mit der kleinen Einschränkung, dass die Namen der Funktionen in den verschiedenen Programmiersprachen deutlich variieren. Die Tabelle stellt die Namen der drei Haskell-Funktionen den entsprechenden Funktionen in C++ und Python gegenüber.

Zwei Punkte sind besonders erwähnenswert. Zum einen besitzt Haskell vier verschiedene Variationen von fold. Die Variationen bestehen darin, ob die binäre Operation am Anfang oder Ende der Liste beginnt, oder ob sie einen oder keinen Startwert besitzt. Zum anderen ergibt Stringkonkatenation von map und reduce (fold) MapReduce. Das ist kein Zufall, basiert doch das gleichnamige Google-Framework auf einer map- und einer reduce-Phase und damit auf den Ideen der Funktionen map und reduce (fold).

Am einfachsten lassen sich die drei Funktionen in der Anwendung studieren. Dabei sollen als Eingabedaten eine Liste (vec) mit den natürlichen Zahlen 0 einschließlich 9 und eine Liste (str) mit den Worten "Programming","in","a","functional","style." dienen. Im Falle von C++ ist die Liste ein std::vector.

// Haskell
vec = [1..9]
str = ["Programming","in","a","functional","style."]

// Python
vec=range(1, 10)
str=["Programming", "in", "a", "functional", "style."]

// C++
std::vector<int> vec{1, 2, 3, 4, 5, 6, 7, 8, 9}
std::vector<string> str{"Programming", "in", "a", "functional", "style."}

Die Ergebnisse werde ich der Einfachheit halber direkt in den Codeabschnitten in der Listen-Syntax von Haskell darstellen.

map

map wendet eine aufrufbare Einheit auf jedes Element einer Liste an. Eine aufrufbare Einheit ist alles, was sich wie eine Funktion verhält. Dies kann eine Funktion, ein Funktionsobjekt oder auch eine Lambda-Funktion in C++ sein. Der ideale Kandidat bei Funktionen höherer Ordnung ist eine Lambda-Funktion. Dies aus zwei Gründen. Zum einen ist die Funktionalität kompakt ausgedrückt und somit gut verständlich. Zum anderen definieren Lambda-Funktionen ihre Funktionalität genau an der Stelle, an der sie benötigt wird. Durch diese Codelokalität erhält der Compiler maximale Einsicht in den Sourcecode und kann daher sehr gut optimieren. In der Regel erzeugt er so performanteren ausführbaren Code als für eine Funktion oder ein Funktionsobjekt:

// Haskell
map(\a -> a * a) vec
map(\a -> length a) str

// Python
map(lambda x :x*x , vec)
map(lambda x : len(x), str)

// C++
std::transform(vec.begin(), vec.end(), vec.begin(),
              [](int i){ return i*i;} );
std::transform(str.begin(), str.end(), std::back_inserter(vec2),
     [](std::string s){ return s.length ();} );

// [1,4,9,16,25,36,49,64,81]
// [11,2,1,10,6]

Natürlich unterscheidet sich die Syntax für Lambda-Funktionen in Haskell, Python und C++. So wird eine Lambda-Funktion in Haskell durch einen Slash \a -> a * a und in Python durch das Schlüsselwort lambda eingeleitet, hingegen in C++ durch eckige Klammern: [](int i){ return i*i; }. Diese Unterschiede sind aber nur syntaktischer Natur. Interessanter ist da aber schon, dass in Haskell Funktionsargumente ohne Klammern aufgerufen werden und dass Haskell und Python eine neue Liste erzeugt, während C++ es erlaubt, den bestehenden std::vector zu überschreiben oder einen neuen zu füllen.

filter

filter belässt nur die Elemente in der Liste, die dem Prädikat genügen. Dabei ist ein Prädikat eine aufrufbare Einheit, die für ihre Argumente einen Wahrheitswert zurückgibt. Genau das zeigt das Listing.

// Haskell
filter (\x-> x <3 || x> 8) vec
filter (\x -> isupper (head x)) sts

// Python
filter(lambda x: x<3 or x>8 , vec)
filter(lambda x: x[0].isupper(), str)

// C++
auto it = std::remove_if(vec.begin(), vec.end (),
     [](int i){return ((i <3) or (i> 8))!});
auto it2 = std::remove_if(str.begin(),  str.end (), 
     [](std::string s) {return !(std::isupper (s[0]));});

// [1,2,9]
// ["Programming"]

Die Funktionskomposition isUpper(head x) prüft bei jedem Wort, ob der erste Buchstabe (head x) ein Großbuchstabe (isUpper) ist. Da std::remove_if in C++ die Elemente des std::vectors entfernt, die dem Prädikat genügen, muss ich den logischen Ausdruck invertieren: return !(std::isupper(s[0])). std::remove_if gibt nur das neue logische Ende seiner Eingabesequenz zurück. 

fold

fold ist die mächtigste der drei Funktionen höherer Ordnung. Lässt sich mit fold doch map und filter implementieren. Das Codeschnipsel stellt in Haskell, Python und C++ die Berechnung der Fakultät von 9 und Stringkonkatenation mit foldl, reduce bzw. std::accumulate vor.

// Haskell
foldl (\a b -> a * b) 1 vec
foldl (\a b -> a ++ ":" ++ b ) "" str

//Python
reduce(lambda a , b: a * b, vec, 1)
reduce(lambda a, b: a + ":" + b, str, "")

// C++
std::accumulate(vec.begin(), vec.end(), 1,
                [](int a, int b){ return a*b; });  
std::accumulate(str.begin(), str.end(), string(""),
                [](std::string a,std::string b){ return a+":"+b; });

// 362800 
// ":Programming:in:a:functional:style."

foldl benötigt wie sein Python Pedant reduce und sein C++ Pendant std::accumulate einen Startwert. Dies ist im Fall der Berechnung der Fakultät die 1, dies ist im Fall der Stringkonkatenation der leere String "". Während Haskell zwei Pluszeichen in ihrer Lambda-Funktionen verlangt, um die Strings zusammen zu addieren, ist in Python und C++ das einfache Pluszeichen ausreichend: a+":"+b.

Welche Strategie wendet nun std::accumulate für sein Ergebnis an? Die Abbildung stellt dies exemplarisch dar.

In der ersten Iteration wird der Startwert 1 zusammen mit dem ersten Wert von v als Argument für die Lambda-Funktion verwendet: 1*1= 1. Dieses Ergebnis 1 ist nun das erste Argument für die Lambda-Funktion in der zweiten Iteration zusammen mit dem zweiten Element von v. 1*2= 2. Die 2 wird in der dritten Iteration mit dem nächsten Element des Vektors 3 prozessiert: 2*3= 6. Mit der letzten Iteration steht das Ergebnis 24 zur Verfügung.

Wie geht's weiter?

Rein funktionale Programmiersprachen wie Haskell zeichnen sich vor allem dadurch aus, dass ihre Daten unveränderlich sind. Damit sind in Haskell keine for, while oder until Schleifen möglich. Welche Konsequenzen das hat, zeigt der nächste Artikel

Go to Leanpub/cpplibrary "What every professional C++ programmer should know about the C++ standard library".   Hole dir dein E-Book. Unterstütze meinen Blog.