Die neue Ranges Bibliothek

Ein kleiner Zeitsprung und wir sind im Jahr 2020. Mit C++20 wird - soweit sich die Zukunft voraussagen lässt - C++ um die neue Ranges-Bibliothek erweitert. Mit der Range-Bibliothek von Eric Niebler wird das Arbeiten mit den Containern deutlich komfortabler und mächtiger. 

Komfortabler, da die Algorithmen der Standard Template Library (STL) direkt auf den Containern agieren können und keinen Anfangs- und Enditerator benötigen. Mächtiger, da mit der Range-Bibliothek C++20 Bedarfsauswertung, deutlich verbesserte Funktionskomposition und Range Comprehension erhält.

Zuerst zum Komfort.

Komfort

Iteratoren sind das verbindende Glied zwischen den generischen Algorithmen und Containern der STL. So gibt jede Container auf Anfrage einen Iterator, der auf sein erstes Element, und einen Iterator, der unmittelbar hinter sein letzte Element verweist, zurück. Dieser halboffene Intervall definiert den Bereich, auf dem der Algorithmus agiert. In C++20 ist dieser halboffene Intervall mit der Range-Bibliothek nicht mehr notwendig, so dass der Algorithmus direkt auf dem Container angewandt werden kann:

std::vector<int> vec{2, 5, 3, 1, 4};
std::sort(vec.begin(), vec.end());   
std::sort(vec);                   // C++20

Weiter geht es in diesem Artikel mit den funktionalen Featuren der Ranges-Bibliothek.

Bedarfsauswertung

Haskell ist durch und durch lazy (siehe Artikel Rekursion, Verarbeitung von Listen und Bedarfsauswertung). Bedarfsauswertung (eng. lazy evaluation) erlaubt es in Haskell, Algorithmen auf unendlichen Datenstrukturen zu definieren, die nur endlich viele Elemente nachfragen. Damit ist es auf sehr elegante Weise möglich, den Algorithmus zur Berechnung einer unendlichen Datenstruktur von seiner Anwendung zu trennen.
Bedarfsauswertung ist eine wichtige Charakteristik funktionaler Programmierung. Mit C++20 wird sie in C++ hoffähig. Damit lässt sich die auskommentierte Zeile Haskell-Code in Zeile 13 direkt in C++ übersetzen:

 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

// lazyEvaluation.cpp

#include <range/v3/all.hpp>
#include <iostream>
#include <tuple>

using namespace ranges;

int main(){

  std::cout << std::endl;

  // take 5 [1..]  -- [1,2,3,4,5]

  auto num = view::take(view::ints(1), 5);
  ranges::for_each(num, [](int i){ std::cout << i << " "; });

  std::cout << "\n\n";

  auto pairs= view::zip_with([](int i, char c){ return std::make_pair(i, c); } , view::ints(0), "ranges");

  ranges::for_each(pairs, [](std::pair<int,char> p){ std::cout << "(" <<  p.first << ":" << p.second << ")"; });

  std::cout << "\n\n";

}

Der Ausdruck view::ints(1) in Zeile 15 erzeugt eine unendliche Folge von natürlichen Zahlen, beginnend mit der 1. Entscheidend ist, dass nur 5 natürliche Zahlen benötigt werden. In der anschließenden for_each-Schleife werden die fünf natürlichen Zahlen mit Hilfe der Lambda-Funktion ausgegeben. Zugegeben, das geht schöner. Zum einen lässt sich der Algorithmus mit Funktionskomposition deutlich eleganter formulieren: auto num= view::ints(1) | view::take(5). Dazu gleich mehr. Zum anderen wird der zukünftige C++20 Standard die direkt Ausgabe des Ranges mittels der Range-basierte for-Anweisung unterstützen: for (n: num) std::cout << num << " ".

Die Funktion view::zip_with, bekannt aus der funktionalen Programmierung, nimmt mehreren Listen und eine Lambda-Funktion an und verknüpft diese mit Hilfe der Lambda-Funktion zu einer neuen Liste. So verknüpft in der Zeile 22 die Lambda-Funktion die unendliche Folge von natürlichen Zahlen, beginnend mit der 0, mit dem endlichen String "ranges". Das Ergebnis ist eine endlicher Tupel, dessen Paare mit first bzw. second adressiert werden können.

Funktionskomposition

Funktionskomposition in Haskell besitzt eine große Ähnlichkeit mit dem Zusammenstecken von Legobausteinen. Die neu komponierten Funktionen drücken ihre Funktionalität sehr kompakt aus und sind für das geübte Auge wie Prosa zu lesen. Dabei basiert die Mächtigkeit der Funktionskomposition in Haskell auf drei Komponenten.

Haskells Funktionen

1. erfüllen genau eine Aufgabe,
2. agieren auf der zentralen Datenstruktur Liste und
3. verwenden den Punkt (.) zur Komposition von Funktionen.

Ähnlich verhält es sich mit der neuen Range-Bibliothek. Sie besitzt einen reichen Satz an Funktionen, der durch Haskell inspiriert ist, agiert auf der zentralen Datenstruktur Range und verwenden das aus der Unix-Shell oder auch Windows PowerShell bekannte Pipe-Symbol (|) zur Komposition von Funktionen.

Und weiter geht mein Vergleich von Haskell und C++20. Der Haskell Code ist wiederum auskommentiert:

 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
31
32
33
34
35

// functionCompositionRanges.cpp

#include <range/v3/all.hpp>
#include <numeric>
#include <iostream>

using namespace ranges;

int main(){

  std::cout << std::endl;

  // odds= takeWhile (< 1000) . filter odd . map (^2)
  // odds [1..]                 -- [1,9,25, ... , 841,961]

  auto odds= view::transform([](int i){ return i*i;} ) |
             view::remove_if([](int i){ return i % 2 == 0; } ) |
             view::take_while([](int i){ return i < 1000;} );
  auto oddNumbers= view::ints(1) | odds;

  ranges::for_each(oddNumbers,[](int i){ std::cout << i << " "; });

  std::cout << "\n\n";

  // total= sum $ take 100 $ map (\x -> x*x) [100..1000] -- 2318350

  auto total= ranges::accumulate(view::ints(100, 1000) |
                                 view::transform([](int x){ return x*x; }) |
                                 view::take(100), 0);

  std::cout << "total: " << total << std::endl;

  std::cout << std::endl;

}

 Während die Verarbeitung der Funktionskomposition in Haskell in Zeile 13 von rechts nach links erfolgt, findet sie C++ in den Zeilen 16 - 19 von links nach rechts statt. Der C++ Ausdruck in Zeile 27 - 29 ist relativ anspruchsvoll zu lesen. Er akkumuliert (ranges::accumulate) die ersten 100 Zahlen (view::take(100)) aus den Zahlen von 100 - 1000 (view::ints(100,1000)), indem er jede Zahl auf ihr Quadrat (view::transform([](int x){ return x*x; }) abbildet. Als Startwert kommt die 0 zum Einsatz.

Die Abbildung zeigt das Programm in Aktion.

Range Comprehension

List Comprehension ist Syntactic Sugar der süßesten Art für die funktionalen Algorithmen map und filter und erlaubt es, zur Laufzeit direkt eine neue Liste zu erzeugen. Die funktionale Programmiersprache Miranda führt List Comprehension ein, durch Haskell wurde sie bekannt. Dass List Comprehension sehr an die mathematische Schreibweise von Mengen erinnert, ist natürlich kein Zufall, basiert doch die funktionale Programmiersprache Haskell auf mathematischen Konzepten.

Die Abbildung stellt die aus der Mathematik bekannte Set Comprehension zur Definiton einer Menge der List Comprehension gegenüber.

Mit der Range-Bibliothek unterstützt C++20 Range Comprehension. Diese ist zwar nicht so leicht verdaulich wie List Comprehension, steht dieser aber in ihrer Funktionalität in keiner Weise nach.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// rangeComprehension.cpp

#include <range/v3/all.hpp>
#include <iostream>

using namespace ranges;

int main(){

  std::cout << std::endl;

  // odds= [ x*x | x <-[1..] , odd x  ]
  // takeWhile (<1000) odds --  -- [1,9,25, ... , 841,961]

  auto odds= view::ints(1) | view::for_each([](int i){ return yield_if(i%2 == 1, i*i); });

  ranges::for_each(odds | view::take_while([](int i){ return i < 1000; }) , [](int i){
    std::cout << i << " ";
  });

  std::cout << "\n\n";

}

Die auskommentierte List Comprehension in Zeile 12 bringt ihre Funktionalität direkt auf den Punkt. Fordere die natürlichen Zahlen an (x<-[1..]), behalte die Elemente x, die ungerade sind (odd x) und bilde diese auf ihr Quadrat ab (x*x). Dabei entspricht odd x der filter-, x*x der map-Funktion. Anschließend wird die Liste evaluiert, solange deren Elemente kleiner als 1000 sind (takeWhile(<1000)).
Der gleiche Algorithmus kommt in C++ zum Einsatz. Das erste Argument des yield_if(i%2 == 1, i*i) Ausdrucks stellt die filter-, das zweite die map-Funktion dar. Die Elemente der Range Comprehension odds werden bis 1000 angefordert: view::take_while([](int i){ return i < 1000; }.

Zum Abschluss die Ausgabe des Programms.

Kommen in einer Range Comprehension mehrere Erzeuger von natürlichen Zahlen oder filter-Funktionen zum Einsatz, so ist diese sehr verständnisresistent. Das zeigt schön mein Vergleich des Pythagoreisches Tripels in Haskell und C++. Das Pythagoreisches Tripel besteht aus den natürlichen Zahlen, die als Länge eines rechtwinkeligen Dreieckes vorkommen können.

triples =[(x, y, z)|z <-[1..], x <-[1..z],y <-[x..z] ,x^2 + y^2 == z^2]

auto triples = 
  view::for_each(view::ints(1),[](int z){
    return view::for_each(view::ints(1, z),[=](int x){
      return view::for_each(view::ints(x, z),[=](int y){
        return yield_if(x*x + y*y == z*z, std::make_tuple(x, y, z));
      });
    });
  });

Die Views Algorithmen (view::for_each) der Range-Bibliothek zeichnen sich dadurch aus, dass sie leichtgewichtige Wrapper über der zugrunde liegenden Range sind. Sie wenden ihre Argumente nur auf Anfrage aus und können diese nicht verändern. Mit Actions (action::remove_if) enthält die Range-Bibliothek zusätzlich einen Satz an Algorithmen, die ihre Argumente verändern und neue Ranges erzeugen können. Im Gegensatz zu den Views werten sie Argumente sofort aus.

Wie geht's weiter?

Damit die Algorithmen der Range-Bibliothek typsicher sind, verwendet Eric Niebler die Type-Traits Bibliothek. Das ist mit C++20 nicht mehr notwendig, den mit C++20 wird C++ um Concepts Lite erweitert. Damit ist aber schon unmittelbar klar, über was ich meinen nächsten Artikel schreibe.

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.