Institut für Informatik

Michael Wand
Christian Ali Mehmeti-Göpel

Wintersemester 2020/21 • DIGITAL

Aufgabe Higher-Order Functions

In der Vorlesung haben wir das Konzept der funktionalen Programmierung kennen gelernt. Funktionszeiger sind eine Möglichkeit, Funktionen an andere Funktionen als Argument zu übergeben. In vielen Fällen ist es jedoch unnötig globale Funktionen zu definieren, die dann per Funktionszeiger an etwa nur einer Stelle eingebunden werden. An dieser Stelle kommen Lambda-Funktionen ins Spiel, die Sie eventuell bereits aus Python kennen.

Lambda-Funktionen in C++

In C++ sehen Lambda-Funktionen folgendermaßen aus:

    [](int a, int b) -> int {return a+b;}

Dabei bezeichnet [] die „Capture-List“, () die Argumentliste, der Teil nach -> den Rückgabetypen und {} umfasst den Funktionsrumpf.

Alle Variablen in der Capture-List werden aus dem umgebenden Scope "eingefangen" und stehen der Lambda-Funktion je nach Deklaration als Kopie oder per Referenz zur Verfügung. Beispielsweise für die Variable a wird die Variable mittels

• [a] als Wert (Kopie)
• [&a] als Referenz

übergeben. Es ist auch möglich, mehrere Variablen anzugeben, etwa durch [x, &y]. Genauso können alle Variablen der umgebenden Scopes eingefangen werden, und zwar durch

• [=] als Werte (Kopie)
• [&] als Referenz.

Hier gilt außerdem:

• Der Rückgabetyp des Lambdas wird automatisch vom Compiler aus dem Ergebnis des return-Statements geschlossen. Obiger Lambda-Ausdruck lässt sich also auch schreiben als [a](int32_t b) {return a + b;}.
• Das Schlüsselwort [...](...) mutable {...} sorgt dafür, dass die Call-by-Value-Variablen der Capture-List auch in der Lambda-Funktion verändert werden können.
• Lambda-Funktionen haben selbst einen Typ, dieser wird aber vom Compiler erzeugt, man kann ihn also im Allgemeinen nicht explizit hinschreiben. Daher muss bei Variablenzuweisungen auf auto (siehe unten) oder Templates gesetzt werden.

Beispiel:

    auto sum = [](int32_t a, int32_t b){return a + b;}
    int32_t c = sum(5, 6);
    int32_t d = sum(4, 8);

Higher-Order-Functions in C++

Lambdas in Variablen zu speichern und dann damit zu arbeiten ist noch nicht sehr spannend. Interessant wird es aber vor allem dann, wenn wir Funktionen definieren wollen, die selbst wieder Funktionen generieren und/oder Funktionen als Argument(e) erhalten, Higher-Order-Functions (siehe Vorlesung).

Beispiel:

    #include <cmath>
    #include <iostream>
    #include <functional> // benötigt für den abstrakten Typ std::function

    // Diese Funktion wendet f auf das größere der beiden int32_t-Argumente an.
    // Dabei bildet f von einem int32_t auf ein double ab, was in Code nur implizit steht.
    // std::function<double(int)> steht hierbei für eine Funktion, die ein int auf ein double Abbildet. 
    // (In der Klammer können auch mehrere durch Kommata getrennte Argumente stehen).
    double transform_max(int a, int b, std::function<double(int)> f) {
        return a > b ? f(a) : f(b);
    }

    // Alternativ können Lambdas auch mithilfe von Templates einer Funktion übergebenen werden
    // Das Ganze sieht dann folgendermaßen aus:
    template <typename Func>
    double transform_max_tl(int32_t a, int32_t b, Func f) {
        return a > b ? f(a) : f(b);
    }

    // Diese Funktion generiert einne Funktion, die prüft, ob eine Zahl < max ist.
    // bool ist hierbei die Ausgabe aus der Eingabe int
    std::function<bool(int)> make_less_predicate(int max) {
        return [max](int val) -> bool {
            return val < max;
        };
    }

    auto make_less_predicate_tl(int32_t max) {
        return [max](int32_t val) -> bool {
            return val < max;
        };
    }

    int main() {

        // Lambdas können auch direkt übergeben werden, ohne erst in einer Variable
        // gespeichert zu werden. (Insbesondere, wenn man sie nur einmal verwendet)
        double t = transform_max(89, 123, [](int32_t c) -> double {
            return std::sqrt(c);
        });

        // Hinweis: Bei der templatisierten Version wird das Templateargument automatisch ermittelt.
        double t2 = transform_max_tl(89, 123, [](int32_t c) -> double {
            return std::sqrt(c);
        });

        auto less42 = make_less_predicate(42);
        auto less5 = make_less_predicate(5);
        std::cout << "Test: " << less5(8) << " " << less5(48) << std::endl;
        std::cout << "Test: " << less42(8) << " " << less42(48) << std::endl;
    }

Übrigens: Ein Prädikat ist dabei im Allgemeinen der Teil einer atomaren Aussage, der wahrheitsfunktional ist (Quelle: Wikipedia). In unseren Beispielen sind dies also Funktionen, die für beliebige Eingabe entweder wahr (true) bzw falsch (false) zurückgeben.

Aufgaben

Implementieren Sie die folgenden Higher-Order Functions und zeigen Sie ihre Verwendung an mindestens einem Beispiel.

1. void for_each(std::vector<float> &v, std::function<void(float)> f)
   Führt die übergebenen Lambda-Funktion vom Typ void(float) für jedes Element aus.
   (Dieses kann zum Beispiel jedes Element auf der Konsole ausgeben).
2. float find_if(std::vector<float> &v, std::function<bool(float)> f)
   Gibt das erste Element der übergebenen Liste aus, das das Prädikat (Funktion vom Typ bool(float)) erfüllt.
3. float count_if(std::vector<float> &v, std::function<bool(float)> f)
   Zählt die Elemente, die das Prädikat (Funktion vom Typ bool(float)) erfüllen.
4. void transform(std::vector<float> &v, std::function<float(float)> f)
   Überschreibt jedes Elment der übergebenen Liste mit dem durch die Funktion f (Typ float(float)) transformierten Element.
5. float accumulate(std::vector<float> &v, std::function<float(float,float)> f, float start = 0.0)
   Summiert die Werte der Liste mithilfe der übergebenen Funktion (Typ float(float,float)) auf.
   
   Es gilt also accumulate(v,f,0) = f(...(f(f(start,v[0]),v[1]),...),v[n]).
6. void partition(std::vector<float> &v, std::function<bool(float)> f)
   „Sortiert“ alle Elemente, die das Prädikat (Typ bool(float)) erfüllen an den Anfang der Liste und alle, die das Prädikat nicht erfüllen ans Ende der Liste.
   (Hierfür ist kein Sortieralgorithmus nötig — einfach über die Liste iterieren reicht vollkommen).
7. template <typename Func1, typename Func2> auto compose(Func1 f1, Func2 f2)
   Erhält zwei Funktionen f1 und f2 und gibt die Funktion zurück, die das Ergebnis von f2 in f1 einsetzt.
   Beide Funktionen haben den Typ float(float);
   Mathematisch ausgedrückt suchen wir die Funktion \[ f_1 \circ f_2: x \mapsto f_1(f_2(x)) \]
   
   (Hinweis: Wir möchten an dieser Stelle die Verwendung templatisierten Funktionen höherer Ordnung üben.)
8. template <typename Func> auto partial(Func f, float val)
   Erhält eine Funktionen f1 mit zwei Argumenten (z.B. Typ float(float,float)) und soll eine Funktion zurückgeben, die das zweite Argument von f festsetzt.
   Diese Funktion hat dann den Typ float(float). Mathematisch ausgedrückt suchen wir die Funktion \[ f_a: x \mapsto f(x,a). \]
   
   (Hinweis: Wir möchten an dieser Stelle die Verwendung templatisierten Funktionen höherer Ordnung üben.)
9. Bonus: Ganz ähnlich wie find_if, count_if könnten auch Funktionen wie etwa any_of, all_of, none_of implementiert werden. Diese sollen die Frage beantworten, ob ein Prädikat für irgendein/kein/alle Elemente gilt.
10. Bonus: Ganz ähnlich zu partition kann auch ein sort implementiert werden, dass basierend auf einem Comparator-Prädikat vom Typ bool(float,float) (also zwei Eingaben) die Liste sortiert — true entspricht dabei der Aussage, dass die linke Eingabe kleiner ist als die zweite Eingabe.