Rekursion, Verarbeitung von Listen und Bedarfsauswertung

Die verbleibenden drei Charakteristiken der funktionalen Programmierung sind recht schnell erzählt: Rekursion, Verarbeitung von Listen und Bedarfsauswertung

Rekursion

Rein funktionale Sprachen kennen keine veränderlichen Daten. Anstelle von Schleifen verwenden sie Rekursion. Die Meta-Funktion aus dem Artikel Reine Funktionen hat es bereits gezeigt. Zur Übersetzungszeit kommen statt Schleifen Rekursionen zum Einsatz. So lässt sich die Faktorial Funktion in C++ 

template <int N>
struct Fac{
  static int const value= N * Fac<N-1>::value;
};

template <>
struct Fac<0>{
  static int const value = 1;
};

in Haskell deutlicher kompakter schreiben:

Verarbeitung von Listen

LISt Processing (LISP) ist charakteristisch für funktionale Programmiersprachen. Da die Liste die universelle Datenstruktur ist, ist sie die ideale Grundlage für Funktionskomposition.

Die Verarbeitung von Listen folgt dem funktionalen Muster:

1. Verarbeite das erste Element der Liste.
2. Verarbeite rekursive den Rest der Liste, der um das erste Element reduziert ist.

Da die Verarbeitung von Listen so idiomatisch für funktionale Programmierung ist, haben sich für das erste Element der Liste und den Rest der Liste Namenskonventionen etabliert: (x,xs), (head,tail) oder (car,cdr).

Das funktionale Muster zur Verarbeitung von Listen lässt sich direkt in Haskell und C++ umsetzen. 

Zuerst die kompakte Haskell Variante, die die Summe der Zahlen von 1 bis 5 ermittelt:

mySum []     = 0
mySum (x:xs) = x + mySum xs
mySum [1,2,3,4,5]  -- 15

Und nun die C++ Variante.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

template<int ...> 
struct mySum;

template<>
struct mySum<>{
  static const int value= 0;
};

template<int head, int ... tail>
struct mySum<head,tail...>{
  static const int value= head + mySum<tail...>::value;
};

int sum= mySum<1,2,3,4,5>::value;  // 15

Während das Haskell-Programm selbst für das imperative Auge einfach zu konsumieren ist, ist das C++-Programm doch deutlich schwerer zu verdauen. Die C++-Syntax verlangt es, dass das primäre oder auch allgemeine Template zumindest deklariert wird. In Zeile 4 folgt das vollständig spezialisierte Klassen-Template (Meta-Funktion), das bei leere Argumentliste angewandt wird. Enthält die Template-Argumentliste ein oder mehrere Elemente, kommt das teilweise spezialisierte Klassen-Template in Zeile 9 zum Einsatz. Noch ein paar Worte zu den drei Punkten, Ellipse genannt. Durch diese kann das Klassen-Template in Zeile 14 beliebig viele Template Argumente annehmen. Dabei packen die drei Punkte in Zeile 1 und 9 das Template-Parameterpack, dabei entpacken die drei Punkte in Zeile 10 und 11 das Funktions-Parameterpack.

Sowohl Haskell als auch C++ verwenden Pattern Matching, um die richtige Funktion anzuwenden.

Pattern Matching

Hier gibt es aber einen feinen Unterschied. In Haskell folgt der Match der First-Match Strategie, so dass der spezielle Fall zuerst definiert werden muss.C++ hingegen folgt in dem Klassen-Template der Best-Match Strategie. Mit Hilfe von Pattern Matching lässt sich die Multiplikation zweier ganzer Zahlen elegant auf deren sukzessive Addition zurückführen. 

Der Eleganz halber zuerst Haskell:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

mult n 0 = 0
mult n 1 = n
mult n m = (mult n (m - 1)) + n



mult 3 2 = (mult 3 (2 - 1)) + 3
         = (mult 3 1 ) + 3
         = 3 + 3
         = 6

Die Zeilen 7 - 10 stellen die Multiplikation der zwei Zahlen 3 und 2 exemplarisch dar. Dabei wird die Zeile 1 dann angewandt, wenn m == 0 ist. Für den Fall, dass m == 1 ist, kommt die Zeile 2 und für den allgemeinen Fall die Zeile 3 zum Einsatz.

C++ folgt einer sehr ähnlichen Strategie. Der Unterschied zu Haskell ist, dass C++ deutlich verboser ist und der allgemeine Fall zuerst definiert werden muss.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

template <int N, int M>
struct Mult{
static const int value= Mult<N, M-1>::value + N;
};
template <int N>
struct Mult<N, 1> {
static const int value= N;
};

template <int N>
struct Mult<N, 0> {
static const int value= 0;
};

std::cout << Mult<3, 2>::value << std::endl;    // 6

Bedarfsauswertung

Die Geschichte zur Bedarfsauswertung in C++ ist kurz. Das ändert sich aber mit der Ranges-Bibliothek von Eric Niebler in C++20. Bedarfsauswertung oder auch Lazy-Evaluation ist der Standard in Haskell. Bedarfsauswertung bedeutet, dass ein Ausdruck immer nur dann ausgewertet wird, wenn er benötigt wird. Diese Strategie besitzt zwei große Vorteile:

1. Durch Bedarfsauswertung lässt sich Zeit und Speicher sparen. 
2. Algorithmen können auf unendlichen Datenstrukturen formulieren. Natürlich ist es zur Laufzeit nur möglich, endliche viele Elemente anzufordern.

Das folgende Codeschnipsel zeigt drei beeindruckende Beispiele in Haskell mit ansteigender Komplexität:

1
2
3
4
5
6
7
8

length [2+1, 3*2, 1/0, 5-4]  -- 4

successor i= i: (successor (i+1))
take 5 ( successor 1 )     -- [1,2,3,4,5]

odds= takeWhile (< 1000) . filter odd . map (^2)
[1..]= [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 ... Control-C  
odds [1..]                 -- [1,9,25, ... , 841,961]  

In der ersten Zeile berechnet length die Länge der Liste, obwohl das Argument 1/0 kein gültiger Ausdruck ist. successor i in Zeile 3 definiert die unendliche Zahlenfolge der natürlichen Zahlen. Da mit take 5 aber nur die ersten fünf angefordert werden, ist der Ausdruck wohldefiniert. Wohldefiniert ist aber nicht der Ausdruck [1..] in Zeile 7, der alle natürlichen Zahlen anfordert. Daher muss die Programmausführung mit Control-C abgebrochen werden. Natürlich lässt sich [1..] anwenden, wenn nur endliche viele Elemente angefordert werden. Genau das findet in odds [1..] statt. odds in Zeile 6 stellt die Mächtigkeit der Funktionskomposition in Haskell beeindruckend dar. Der Punkt (.) ist das Zeichen für die Funktionskomposition. Der Ausdruck kann direkt mit ein bisschen Übung von rechts nach links gelesen werden: Wende zuerst die Quadrat-Funktion an, filtere danach alle gerade Elemente heraus und fahre solange fort, solange die Zahlen kleiner als 1000 sind. Die letzte Zeile stellt alle geraden Quadrat-Zahlen kleiner als 1000 vor.

C++ wendet standardmäßig Eager-Evaluation an. Das heißt bildlich gesprochen, dass C++ im Gegensatz zu Haskell die Ausdrücke von innen nach außen evaluiert. Mit der Kurzschlussauswertung (eng. short circuit evaluation) in logischen Ausdrücken ist C++ aber ein bisschen lazy. Steht in einem logischen Ausdruck das Ergebnis des Gesamtausdruckes vorzeitig fest, wertet die C++-Laufzeit den Gesamtausdruck nicht mehr vollständig aus.
Daher lässt sich das folgende Programmfragment ausführen, obwohl 1/0 nicht definiert ist:

if ( true or (1/0) ) std::cout << "short circuit evaluation" << std::endl;

Wie geht's weiter?

Mit dem nächsten Artikel zur Funktionalen Programmierung In C++ betrete ich die Zukunft von C++. Fold expressions basieren auf Variadic Templates und erlauben es in C++17, das auch Haskell bekannte fold-Algorithmenfamilie zur Compilezeit in C++ anzuwenden.

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.