Fold Expressions

Mit Fold Expressions lassen sich die aus Haskell bekannten Funktionen foldl, foldr, foldl1 und foldr1, die eine Liste sukzessive auf einen Wert reduzieren, direkt in C++ umsetzen.

Fold Expressions

C++11 kennt Variadic Templates. Das sind Template, die eine beliebige Anzahl von Template-Argumente annehmen können. Diese beliebige Anzahl wird in dem Parameter Pack gehalten. Neu ist mit C++17, dass ein Parameter Pack direkt über einem binären Operator reduziert werden kann. Damit lassen sich die aus Haskell bekannten Funktionen foldl, foldr, foldl1 und foldr1, die eine Liste sukzessive auf einen Wert reduzieren, direkt in C++ umsetzen.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

// foldExpression.cpp

#include <iostream>

bool allVar(){
  return true;
}

template<typename T, typename ...Ts>
bool allVar(T t, Ts ... ts){
  return t && allVar(ts...);
}

template<typename... Args>
bool all(Args... args) { return (... && args); }

int main(){

  std::cout << std::boolalpha;

  std::cout << "allVar(): " << allVar() << std::endl;
  std::cout << "all(): " << all() << std::endl;

  std::cout << "allVar(true): " << allVar(true) << std::endl;
  std::cout << "all(true): " << all(true) << std::endl;

  std::cout << "allVar(true, true, true, false): " << allVar(true, true, true, false) << std::endl;
  std::cout << "all(true, true, true, false): " << all(true, true, true, false) << std::endl;

}

Die beiden Funktions-Templates allVar und all geben zur Compilezeit genau dann true zurück, wenn alle Argumente true sind. allVar wendet Variadic Templates, all Variadic Templates in Kombination mit Fold Expression an. Zuerst zu allVar. Variadic Templates verwenden Rekursion um ihre Argumente zu evaluieren. So stellt die Funktion allVar in Zeile 5 die Randbedingung dar, falls das Parameter Pack leer ist. Die eigentliche Rekursion findet in dem Funktions-Template allVar in der Zeile 9 statt. Durch die drei Punkte - Ellipse genannt - wird das Parameter Pack definiert. Parameter Packs erlauben zwei Operationen. Sie können ge- und entpackt werden. Gepackt wird das Parameter Pack in Zeile 9, entpackt in den Zeilen 10 und 11. Die Zeile 11 verlangt besondere Aufmerksamkeit. In ihr wird der Kopf des Parameter Packs t mit der Rest des Parameter Packs ts mit dem binären Operator && verknüpft. Der Aufruf allVar(ts...) stößt dabei die Rekursion an. Dieser Aufruf enthält ein Parameter Pack, dass sukzessive um sein erstes Element reduziert wird. Dies geht mit C++17 deutlich einfacher. In C++17 kann der Parameter Pack direkt über einem binären Operator reduziert werden.

Die Abbildung zeigt die beiden Algorithmen in der Anwendung. 

Zwei Variationen

Nun zu den zwei Variationen der Fold Expression, die zu den vier verschiedenen Formen der Fold Expression führen. Zum einen können Fold Expression

1. abhängig vom binären Operator einen Default-Wert besitzen,
2. zum anderen können sie das Parameter-Pack von links oder rechts beginnend prozessieren.

Ein feiner Unterschied besteht zwischen den zwei Algorithmen allVar und all. all besitzt bereits den Defaultwert true für das leere Parameter Pack. 

C++17 unterstützt 32 binäre Operatoren in Fold Expression: "+ - * / % ^ & | = < > << >> += -= *= /= %= ^= &= |= <<= >>= == != <= >= && || , .* ->*" . Einige binären Operatoren besitzen bereits Defaultwerte:

Für binäre Operatoren, für die keine Default-Wert definiert ist, muss, für binäre Operationen, für die ein Default-Wert definiert ist, kann ein Startwert angegeben werden.    
Ob ein Parameter Pack von links oder von rechts prozessiert wird, hängt davon ab, ob die Ellipse links oder rechts vom Parameter Pack ist. Das gleiche trifft auf Fold Expression mit Startwert zu.

Die folgende Tabelle stellt die vier Variationen und deren Haskell Pendants vor. Der C++17-Standard fordert, das Fold Expression mit Startwert die gleichen binären Operatoren op verwenden.

Die C++- und Haskell-Variationen unterscheiden sich in zwei Punkten. Kommt bei den C++ Variationen ein Default-Wert zum Einsatz, verwendet Haskell den ersten prozessierte Wert als Startwert. Die C++-Varianten prozessieren ihr Parameter Pack zur Compilezeit, die Haskell-Varianten ihre Listen zur Laufzeit des Programms.

 Der kleine Codeschnipsel stellt den äquivalenten Algorithmus aus dem ersten Beispiel mit einem Startwert vor.

template<typename... Args>
bool all(Args... args) { return (true && ... && args); }

Wie geht's weiter?

Während mit Fold Expression der wohl ureigenste funktionale Algorithmus in C++17 direkt unterstützt wird, erweitert die Range-Bibliothek C++20 um drei mächtige funktionale Konzepte. Im nächsten Artikel geht es um Eric Nieblers neue Ranges Bibliothek, mit der Bedarfsauswertung, deutlich verbesserte Funktionskomposition und Range Comprehension ein Zuhause in funktionalem C++ finden.

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.