jambit ToiletPaper: Rekursion mit anonymen Funktionsobjekten

Rekursion mit anonymen Funktionsobjekten

Problem: Wie soll man eine anonyme Methode rekursiv aufrufen?

In der jüngeren Vergangenheit wurden C++ (ab C++11), Java (ab Version 8) und viele andere Sprachen um “Lambdas” erweitert. In der Praxis handelt es sich dabei um eine verkürzte Notation, um eine anonyme Klasse mit einem funktionalen Interface zu definieren und gleichzeitig ein Objekt dieser Klasse zu instanziieren. Aber wie soll man eine anonyme Methode rekursiv aufrufen?!?

Lösung: Der fixed-point combinator

In C++ kann man zwar Lambdas à la std::function<void()> f = [f]() { /* ... */ f(); }; definieren, aber nicht inline (z.B. als Parameter), und auch nur mit einer zusätzlichen Indirektion (z.B. via std::function). Für Java sieht's nicht besser aus. Eleganter geht es mit dem “Y-Kombinator” (wobei man im Internet besser nach “fixed-point combinator" sucht): Man ersetzt die rekursive Funktion durch eine Funktion höherer Ordnung, die statt sich selbst ihren Parameter aufruft. Diese Funktion füttert man dann in besagten Kombinator, welcher die Funktion immer wieder mit sich selbst als Parameter aufruft.

Und wie sieht dieser mysteriöse Kombinator jetzt aus? In C++ (für beliebige Parameter) bzw. Java (mit Currying für den ersten Parameter, die Funktion) zum Beispiel so:

C++ (für beliebige Parameter beliebigen Typs)
template <typename F>
class Y {
  F f;
public:
  constexpr Y(F f) : f(std::forward<F>(f)) {}
  template <typename...Ts>
  constexpr decltype(auto) operator()(Ts&&...ts) {
    return f(*this,
        std::forward<Ts>(ts)...);
  }
};
Java (mit Currying für die Funktion, und einem weiteren Parameter)
class Y<T, R> implements Function<T, R> {
  private Function<Function<T, R>,
          Function<T, R>> f;
  public Y(Function<Function<T, R>,
           Function<T, R>> f) {
    this.f = f;
  }
  public R apply(T t) {
    return f.apply(this).apply(t);
  }
}

Beispiel

Schauen wir uns das Standardbeispiel für Rekursion an, nämlich die Fakultät. Als Funktion (in C++), sowie als Lambda in C++17 und Java sieht das so wie im Bild aus.

Den trailing return type braucht man in C++ leider, weil der Compiler sonst “auto type deduction“ triggert, was zu einer zyklischen Abhängigkeit führt.

Fakultät als Funktion (in C++), sowie als Lambda in C++17/Java

Weiterführende Aspekte

---

Autor: Andreas Swoboda / Software Engineer / Business Division Banking & Insurance

Recursion With Anonymous Function Objects

Wir verwenden Cookies, um unsere Webseite für Sie zu optimieren. Mit dem Besuch unserer Webseite erklären Sie sich damit einverstanden. // Our website is using cookies to improve your experience. By continuing to browse the site, you are agreeing to our use of cookies.

Weitere Informationen finden Sie in unserer Datenschutzerklärung. // For more information, please refer to our privacy policy.