jambit ToiletPaper: Rekursion mit anonymen Funktionsobjekten

Recursion With Anonymous Function Objects

Problem: How to call an anonymous method recursively?

In the recent past, C++ (since C++11), Java (since version 8) and many other languages have been extended by "lambdas". In practice, this is a shortened notation to define an anonymous class with a functional interface and at the same time instantiate an object of this class. But how to call an anonymous method recursively?!?

Solution: The fixed-point combinator

Even though it is possible to create lambdas à la std::function<void()> f = [f]() { /* ... */ f(); }; in C++, it only works with an additional indirection (e.g. via std::function) and not inline (e.g. as parameter). For Java, it does not look any better. A more elegant way is to use the "Y combinator" (you might search the internet for "fixed-point combinator"): You replace the recursive function with a higher-order function that calls its parameter instead of itself. You put this function into the Y combinator, which repeatedly calls the function with itself as parameter.

And what does this mysterious combinator look like? Here are possible implementations in C++ (for any number of parameters of any type) and Java (with currying for the function and an additional parameter):

C++ (for any number of parameters of any type)
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 (with currying for the function and an additional 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);
  }
}

Example

Let's have a look at the standard example for recursion, the factorial. As a function (in C++), and as a lambda in C++17/Java, it looks like in the image.

The trailing return type is unfortunately needed in C++, because otherwise the compiler triggers "auto type deduction", which leads to a cyclic dependency.

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

Further Aspects

---

Author: 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.