Die 8 Damen in highJ


Normalerweise schreibe ich hier kaum über meine highJ-Bibliothek. Da ist auch wirklich ziemlich seltsames Zeug drin, und seit Clinton Selke mitmacht, auch immer mehr, was ich selbst nicht mehr so ganz verstehe.

Nun gab es vor kurzem die Anregung von Clinton, die MonadRec-Implementierung aus PureScript zu übersetzen, weil man damit Stacküberläufe verhindern kann, wenn man mit Monaden(-transformern) arbeitet. Heute nun habe ich meine Listen-Monade nun um besagte MonadRec erweitert, und mich gefragt, wie ich das ganze denn testen soll. Zu meiner eigenen Überraschung habe ich einen wohlbekannten Anwendungsfall gefunden.

Hier ist das Ergebnis:

public static List<String> eightQueens() {
    Predicate<List<Integer>> isValid = pos ->
        ! List.of(pos.tail(),
            List.zipWith(pos.tail(), List.range(1), x -> y -> x+y),
            List.zipWith(pos.tail(), List.range(1), x -> y -> x-y))
        .contains(list -> list.contains(pos.head()));

    Function<List<Integer>, _<List.µ, Either<List<Integer>,String>>> fn =
        pos -> pos.size() == 8
            ? List.of(Either.newRight(
                Strings.mkString("[", ",", "]", pos.reverse())))
            : List.range(1,1,8).map(pos::plus)
               .filter(isValid).map(Either::newLeft);

    return List.monadPlus.tailRec(fn, List.empty());
}

Wer zu meinem Beitrag Und wieder mal die Damen… springt, kann dort das eher bescheidene Ergebnis des titanischen Ringens mit der funktionalen API von Java 8 bewundern. Man merkt richtig, wie einem dort die geeigneten Werkzeuge fehlen, oder zumindest schwer erreichbar sind. Und das lässt den Code schwerfällig und plump erscheinen.

Mit dem obigen Schnipsel bin ich recht zufrieden. Sicher, es sieht erst einmal ungewöhlich aus. Und ich will hier auch gar nicht im Detail erklären, wie der Code funktioniert, das ist gar nicht der Punkt. Worauf ich hinaus will ist, dass das Beispiel zeigt, was selbst in den Grenzen von Java 8 möglich ist, wenn man sich auf eine entsprechende „Infrastruktur“ stützen kann. Es ist auch ein Beispiel, wie unmittelbar „theoretisches Zeug“ ganz praktische Probleme erleichtern kann.

Wer trotzdem eine „high-level“-Erklärung haben will: MonadRec ist an sich nichts besonderes, es „externalisiert“ nur den Prozess der Rekursion, und erlaubt so, selbige hinter den Kulissen durch Iteration zu ersetzen (was den allseits unbeliebten Stackoverflow verhindert). Die „geheime Soße“ ist nun, dass die Liste als Monade eben nicht nur ein schnöder Container ist, sondern auch als mehrwertiges Berechnungsergebnis gesehen werden kann. Damit führt man in den simplen Mechanismus von MonadRec die Möglichkeit ein, nicht nur eindimensional die Lösung zu suchen, sondern in vielen Richtungen, und damit einen Suchraum aufzuspannen. Der Witz ist, dass sich das „einfach so“ ergibt; es ist die naheliegende und natürliche Lösung, wenn man das MonadRec-Interface für die Listen-Monade implementieren will.

Natürlich ist und bleibt meine highJ-Bibliothek experimentell, und die API ist nicht stabil. Für die praktische funktionale Programmierung in Java würde ich deshalb eher zu javaslang oder functionaljava raten.

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