Java 8 und der Y-Kombinator


So schön Lambda-Ausdrücke auch sind, sie haben wenigstens eine Achillesferse: Rekursion. Betrachten wir folgendes Beispiel, das schon seit Java 5 funktionieren würde (ein entsprechendes Function-Interface einmal vorausgesetzt):

...
Function<Integer, Long> fac = new Function<Integer, Long>() {
    @Override
    public Long apply(Integer n) {
        return n == 0 ? 1L : n * apply(n-1);
    }
};

System.out.println(fac.apply(10)); //--> 3628800
...

So weit, so gut und auch so langweilig: Die gute alte Fakultät. Aber wie lässt sich die Definition der anonymen Klasse durch einen Lambda-Ausdruck ersetzen? Hier zwei Beispiele dafür, wie es schon einmal nicht geht:

//Compiler-Fehler: "Variable fac might not have been initialized"
Function<Integer, Long> fac = n -> n == 0 ? 1L : n * fac.apply(n-1);  

//this verweist hier auf die umgebende Klasse, nicht auf den Lambda-Ausdruck selbst
Function<Integer, Long> fac = n -> n == 0 ? 1L : n * this.apply(n-1);  

Wir müssen also tiefer in die Trickkiste greifen. Man bräuchte einen Weg, um die Rekursion sozusagen „explizit“ zu machen. Erfreulicherweise ist dieses Problem schon lange gelöst und gehört zur Folklore der funktionalen Sprachen: Man verwendet einen Fixpunkt-Kombinator wie den Y-Kombinator. Ich will an dieser Stelle nicht genauer auf die Funktionsweise eingehen, hauptsächlich um zu verhindern, dass mein Gehirn schmilzt, aber auch, weil man unter Magiern keine Tricks verrät. Deshalb hier eine sehr direkte Umsetzung dieses Konzepts (z.B. ohne weitere Vorkehrungen, um einen Stacküberlauf zu verhindern):

...
public static <X,Y> Function<X,Y> yCombinator(Function<Function<X,Y>,Function<X,Y>> f) {
   return x -> f.apply(yCombinator(f)).apply(x);
}
...

Function<Integer,Long> fac = yCombinator(f -> n -> n == 0 ? 1L : n * f.apply(n-1));

System.out.println(fac.apply(10)); //--> 3628800

Wer mehr dazu erfahren will, sollte sich den Wikibook-Eintrag zu Haskell’s fix-Funktion anschauen. Aber selbst wenn man die „Magie“ nicht im Detail nachvollziehen kann oder will, ist es nützlich zu wissen, dass es diesen Trick gibt. Es ist auch ein schönes Beispiel dafür, dass es sich lohnen kann, einmal über den objektorientierten Tellerrand zu schauen, um die tollen neuen Features von Java 8 auch wirklich ausnutzen zu können.

Update

Vielleicht ist folgende Schreibweise mit BiFunction lesbarer:


public static <X,Y> Function<X,Y> yCombinator(BiFunction<X,Function<X,Y>,Y> f) {
    return x -> f.apply(x, yCombinator(f));
}
...
//Anwendung
Function<Integer,Long> fac = yCombinator((n,f) -> n == 0 ? 1L : n * f.apply(n-1));
System.out.println(fac.apply(10));
Advertisements

Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s