Doppel-Switch in Java

Ich hasse es, wenn ich geschachtelte switch-Blöcke sehe. Es ist einfach unübersichtlich, und während man Fälle zusammenfassen kann, wo einem der zweite, „innere“ Wert egal ist, geht das für den ersten, „äußeren“ Wert nicht.

Nehmen wir als Anwendungsfall einmal ein boolesches TriState-Enum, das auch „und“- und „oder“-Operationen unterstützt. Eine mögliche Implementierung könnte so aussehen:

public enum TriState {
    TRUE, FALSE, UNKNOWN;

    private static TriState and(TriState a, TriState b) {
        switch(a) {
            case FALSE: return FALSE;
            case TRUE: return b;
            case UNKNOWN: switch(b) {
                case FALSE: return FALSE;
                default: return UNKNOWN;
            }
        }
        throw new AssertionError();
    }

    private static TriState or(TriState a, TriState b) {
        switch(a) {
            case TRUE: return TRUE;
            case FALSE: return b;
            case UNKNOWN: switch(b) {
                case TRUE: return TRUE;
                default: return UNKNOWN;
            }
        }
        throw new AssertionError();
    }
}

Man kann sich leicht vorstellen, wie bei mehr Werten die switches schnell unübersichtlich werden. Hier ein Beispiel, wie es mit DSL aussehen könnte:

public enum TriState {TRUE, FALSE, UNKNOWN;

    private static TriState and(TriState a, TriState b) {
        return switch2(a, b,
                case2(TRUE, TRUE, () -> TRUE),
                case2(FALSE, any(), () -> FALSE),
                case2(any(), FALSE, () -> FALSE),
                default2(() -> UNKNOWN)
        );
    }

    private static TriState or(TriState a, TriState b) {
            return switch2(a, b,
                    case2(FALSE, FALSE, () -> FALSE),
                    case2(TRUE, any(), () -> TRUE),
                    case2(any(), TRUE, () -> TRUE),
                    default2(() -> UNKNOWN)
            );
    }
}

Ich habe mich entschlossen, die „Leerstellen“ über einen speziellen Wert any() zu kennzeichnen. Wenn beide Werte egal sind, habe ich analog zum normalen switch als Synonym auch die Methode default2 bereitgestellt. Ich hoffe, dass das die Bedienung intuitiver macht. Hier die Implementierung des DSLs:

import java.util.Optional;
import java.util.function.BiFunction;
import java.util.function.Supplier;

public final class Switch {
    private Switch(){ /*do not instantiate*/ }

    enum Any {any}

    public static Any any() {
        return Any.any;
    }

    @SafeVarargs
    public static <A,B,R> R switch2(A a, B b, BiFunction<A, B, Optional<R>>... cases) {
        return Arrays.stream(cases)
            .map(biFunction -> biFunction.apply(a,b))
            .flatMap(opt -> opt.map(Stream::of).orElseGet(Stream::empty))
            .findFirst()
            .orElseThrow(() -> new RuntimeException("no match found"));
    }

    public static <A,B,R> BiFunction<A, B, Optional<R>> case2(A a, B b, Supplier<R> result) {
        return (_a, _b) -> a.equals(_a) && b.equals(_b) ? Optional.of(result.get()) : Optional.empty();
    }

    public static <A,B,R> BiFunction<A, B, Optional<R>> case2(A a, Any any, Supplier<R> result) {
        return (_a, _b) -> a.equals(_a) ? Optional.of(result.get()) : Optional.empty();
    }

    public static <A,B,R> BiFunction<A, B, Optional<R>> case2(Any any, B b, Supplier<R> result) {
        return (_a, _b) -> b.equals(_b) ? Optional.of(result.get()) : Optional.empty();
    }

    public static <A,B,R> BiFunction<A, B, Optional<R>> case2(Any any1, Any any2, Supplier<R> result) {
        return default2(result);
    }

    public static <A,B,R> BiFunction<A, B, Optional<R>> default2(Supplier<R> result) {
        return (_a, _b) -> Optional.of(result.get());
    }
}

Auch wenn man in anderen Sprachen noch viel „natürlichere“ DSLs schreiben kann, ist es doch immer wieder schön zu sehen, wie „erweiterbar“ Java inzwischen geworden ist, und das ohne größeren Aufwand. Ich glaube aber, dass bei vielen Java-Entwicklern das Bewusstsein fehlt, welche Möglichkeiten sie inzwischen haben. Das ist schade, aber ich hoffe sehr, dass sich das langsam ändert.

Advertisements

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.

Eine fehlende Optional-Methode und ein Workaround

Ein wirklich hässliches Pattern, um mehrere Dinge auszuprobieren, bis eines davon klappt, ist:

int x = ...
int y = ...
int z = ...

Integer result = null;
if (x % 2 == 0) {
    result = x / 2;
}
if (result == null && y % 2 == 0) {
    result = y / 2;
}
if (result == null && z % 2 == 0) {
    result = z / 2;
}
String s = result == null
    ? "all numbers were odd"
    : "the result is " + result;

Eigentlich sollte Optional uns in diesen Fällen die Null-Checks abnehmen. In Scala und mit der Optional-Variante von Guava geht das auch sehr schön, da in beiden Fällen Methoden vorhanden sind, um einen vorhandenen Wert unverändert „durchzuschleusen“, aber im „leeren“ Fall stattdessen ein anderes Optional zu verwenden.

Unverständlicherweise fehlt eine solche Funktion in Java 8. Die direkte Übersetzung unseres Beispiels sieht deshalb auch nicht viel hübscher als das Original aus:

public static Optional<Integer> half(int x) {
    return x % 2 == 0 
        ? Optional.of(x / 2) 
        : Optional.empty();
}

...

Optional<Integer> result = half(x);
if (! result.isPresent()) {
    result = half(y);
}
if (! result.isPresent()) {
    result = half(z);
}
String s = result
    .map(n -> "the result is " + n)
    .orElse("all numbers were odd");

Zum Vergleich die elegante Scala-Version:

def half(n : Int) : Option[Int] = 
    if (n % 2 == 0) Some(n / 2) else None

val s = half(x)
    .orElse(half(y))
    .orElse(half(z))
    .map(n => "the result is " + n)
    .getOrElse("all numbers were odd")

Haben wir eine Chance, das wenigstens ungefähr so nachzubauen? Ja, es gibt einen Workaround. Das ist wieder eines jener Probleme, über das man durchaus eine Weile grübeln kann, aber wenn man einmal die Lösung kennt, erscheint sie ganz selbstverständlich:

String s = half(x).map(Optional::of)
    .orElse(half(y)).map(Optional::of)
    .orElse(half(z))
    .map(n -> "the result is " + n)
    .orElse("all numbers were odd");

Der Trick ist, mit einem map aus dem Optional<Integer> jeweils ein Optional<Optional<Integer>> zu machen, bevor wir mit der orElse-Methode wieder eine Optional-Ebene „abbauen“. Insgesamt macht diese map-orElse-Kombination also genau dasselbe, was in Scala ein einzelnes orElse (oder im Optional von Guava ein or) erledigt.

Wir haben sogar die Chance, hier noch etwas besser zu machen. Was wäre, wenn die half-Aufrufe lange dauern würden oder ungewünschte Seiteneffekte hätten? Dann sollten die Aufrufe natürlich lazy erfolgen, und das geht, in dem man das orElse einfach durch orElseGet ersetzt:

String s = half(x).map(Optional::of)
    .orElseGet(() -> half(y)).map(Optional::of)
    .orElseGet(() -> half(z))
    .map(n -> "the result is " + n)
    .orElse("all numbers were odd");

Trotzdem hoffe ich sehr, dass die Verantwortlichen ein Einsehen haben, Optional in Java 9 ein wenig komfortabler gestalten, und uns damit solche Verrenkungen in Zukunft ersparen.

Java-Kontrollstrukturen nachgebaut – if

Wieder so ein seltsamer Beitrag: Wozu sollte man Kontrollstrukturen nachbauen? Nun, selbst als reine Fingerübung lernt man einiges über die Möglichkeiten – und Unmöglichkeiten – der Sprache, aber die eigentliche Idee ist, einen soliden Ausgangspunkt für eigene Erweiterungen zu schaffen.

Beginnen wir mit einer der einfachsten Kontrollstrukturen, nämlich if, und dem verwandten ternären Operator x ? y : z. Das klassische if ist leicht zu modellieren – die einzige Schwierigkeit ist, dass wir schön „lazy“ bleiben, also einen Zweig nur dann ausführen, wenn die Entscheidungsvariable das auch vorsieht:

public static void if1(boolean choice, 
    Runnable ifTrue, 
    Runnable ifFalse) {
    if (choice) {
        ifTrue.run();
    } else {
        ifFalse.run();
    }
}

/Anwendung
if1(System.currentTimeMillis() % 2 == 0,
        () -> System.out.println("ifTrue"),
        () -> System.out.println("ifFalse"));

Allerdings wäre solcher Code in der funktionalen Programmierung verpönt, denn er tut nur eines: Seiteneffekte ausführen. Viel nützlicher wäre ein Verhalten, wie es der ternäre Operator zeigt, der stattdessen einen Wert zurückliefert. Nichts leichter als das:

public static <A> A if2(boolean choice, 
    Supplier<A> ifTrue, 
    Supplier<A> ifFalse) {
    return choice ? ifTrue.get() : ifFalse.get();
}

//Anwendung
String s = if2(System.currentTimeMillis() % 2 == 0,
    () -> "trueValue", 
    () -> "falseValue");

Wir haben jetzt schon einen kleinen Vorteil gegenüber dem ternären Operator: Die beiden Zweige können aus mehreren Operationen bestehen. Trotzdem geht es noch besser. Was ist z.B., wenn man das Konstrukt wiederverwenden will? Nun, mit einer kleine Änderung können wir die Auswertung „auf später“ verschieben, und damit eine Mehrfachnutzung erleichtern:

public static <A> Function<Boolean, A> if2Fun(
    Supplier<A> ifTrue, 
    Supplier<A> ifFalse) {
    return b -> if2(b, ifTrue, ifFalse);
}

//Anwendung
Function<Boolean, String> f = if2Fun(
    () -> "trueValue", 
    () -> "falseValue");
System.out.println(
    f.apply(System.currentTimeMillis() % 2 == 0));
System.out.println(
    f.apply(System.currentTimeMillis() % 2 == 0));

Ein anderer Schwachpunkt ist, dass sich unsere bisherigen Konstrukte schlecht schachteln lassen. Sicher sind ellenlange if-else-Kaskaden nicht die feine englische Art, aber hin und wieder lassen sie sich doch nicht vermeiden. Jetzt brauchen wir schon Fluent Interfaces, und bewegen uns langsam in Richtung DSL:

public class If3<A> {

    private Optional<A> result = Optional.empty();

    public static <A> If3<A> if3(boolean choice, 
        Supplier<A> ifTrue) {
        If3<A> if3 = new If3<>();
        if (choice) {
            if3.result = Optional.of(ifTrue.get());
        }
        return if3;
    }

    public If3<A> elseIf3(boolean choice, 
        Supplier<A> ifTrue) {
        if (! result.isPresent() && choice) {
           result = Optional.of(ifTrue.get());
        }
        return this;
    }

    public A else3(Supplier<A> ifTrue) {
        return result.orElseGet(ifTrue);
    }

}

//Anwendung
int i = 15;
String s = if3 (i < 10, () -> "kleiner 10")
    .elseIf3 (i < 100, () -> "kleiner 100")
    .else3(() -> "größer gleich 100");

Es ist auch möglich, die Variante, die eine Funktion liefert, und die letzte „kaskadierende“ Variante zu kombinieren, unter der Voraussetzung, dass alle Tests auf einen einzigen Wert ausgeführt werden können:

public class If4<T,A> {

    private Map<Predicate<T>, Supplier<A>> cases = 
        new LinkedHashMap<>();

    public static <T,A> If4<T,A> if4(
        Predicate<T> choice, 
        Supplier<A> ifTrue) {
        If4<T,A> if4 = new If4<>();
        if4.cases.put(choice, ifTrue);
        return if4;
    }

    public If4<T,A> elseIf4(Predicate<T> choice, 
        Supplier<A> ifTrue) {
        cases.put(choice, ifTrue);
        return this;
    }

    public Function<T, A> else4(Supplier<A> ifTrue) {
        return t -> {
            for(Map.Entry<Predicate<T>, Supplier<A>> entry : 
                cases.entrySet()) {
                if (entry.getKey().test(t)) {
                    return entry.getValue().get();
                }
            }
            return ifTrue.get();
        };
    }
}

//Anwendung
Function<Integer, String> f = if4(
        (Integer i) -> i < 10, () -> "kleiner 10")
        .elseIf4(i -> i < 100, () -> "kleiner 100")
        .else4(() -> "größer gleich 100");
System.out.println(f.apply(15));

Allerdings sieht man hier, dass damit die Grenzen von Javas Typinferenz-Mechanismus erreicht sind: Das Prädikat in der if4-Methode benötigt die Typangabe (Integer i), um zu kompilieren. Trotzdem ist es interessant, was alles möglich und – fast noch wichtiger – auch praktikabel ist.

Ich hoffe, die Zeit zu finden, diese kleine Serie fortzusetzen. Neben den offensichtlichen Kandidaten wie case und for dürfte auch try mit allen seinen Varianten (inklusive ARM) interessant sein.

Kleiner Optional-Trick in Java

So froh ich über die Einführung von Optional in Java 8 bin, so ärgerlich ist dort das Fehlen von Methoden, die eigentlich selbstverständlich sein sollten. So renne ich öfter in die Situation, dass ich aus dem Optional keinen Wert zurückliefern möchte, sondern abschließend eine Aktion ausführen. Dafür gibt es die Methode ifPresent, die einen Consumer entgegennimmt. Das Problem ist, dass ich im Falle eines leeren Optionals keine Default-Aktion angeben kann.

Zur Veranschaulichung ein Beispiel: Ich möchte aus einem Integer-Optional heraus auf die Konsole schreiben, ob die Zahl gerade ist oder nicht. Ist das Optional leer, will ich auch das auf die Konsole schreiben. Natürlich würde man in diesem einfachen Fall normalerweise den String „durchreichen“, aber nehmen wir an, dass statt der Textausgabe verschiedene Aktionen erforderlich sind, die sich nicht so leicht „integrieren“ lassen. Gewöhnlich sah der Code dann bei mir so aus:

Optional<Integer> op = ...
if (op.isPresent()) {
    op.ifPresent(i -> {
        System.out.println(i % 2 == 0 ? "even" : "odd");
    });
} else {
    System.out.println("empty");
}

Ich finde den expliziten Test recht hässlich – eine zusätzliche Schleife, die unser Gehirn drehen muss. Mein Workaround wird sicher auch keinen Schönheitspreis gewinnen, trotzdem halte ich diese Version für einen (kleinen) Fortschritt:

Optional<Integer> op = ...
op.<Runnable>map(i -> () -> {
    System.out.println(i % 2 == 0 ? "even" : "odd");
}).orElse(() -> System.out.println("empty")
).run();

Der Trick ist, die Aktion nicht sofort auszuführen, sondern in ein Runnable zu verpacken. Damit kann man dieses als Wert „durchschleifen“, und hat damit auch die Chance, über orElse auch einen Defaultwert angeben zu können. Die generische Typangabe bei map ist leider notwendig, und die Schreibweise mit den zwei Pfeilen in map ist auch gewöhnungsbedürftig. Man muss auch aufpassen, dass man das run() am Ende nicht vergisst.

Ich hoffe wirklich, dass hier bei Java 9 noch nachgebessert wird, denn solche Klimmzüge für ein einfaches Problem müssen nun wirklich nicht sein. Oder habe ich eine elegantere Lösung übersehen?

Dependency Injection mit der Reader-Monade

Schon wieder nehme ich das böse M-Wort in den Mund! Dabei ist die Reader-Monade kaum mehr als eine einfache Function. Aber eins nach dem anderen.

Zuerst einmal das Datenmodell mit einem Fake-Service:

public class User {
    public long id;
    public String name;

    public User(String name, long id) {
        this.id = id;
        this.name = name;
    }
}

public interface UserService {
    User getUser(long id);

    List<User> findAll();
}

public class UserServiceImpl implements UserService {
    @Override
    public User getUser(long id) {
        return new User("user" + id,id);
    }

    @Override
    public List<User> findAll() {
        return IntStream.of(1,2,5,42).
               mapToObj(this::getUser).
               collect(Collectors.toList());
    }
}

Nun das Grundgerüst der Komponente, die diesen Service gern benutzen würde:

public class UserComponent {
    public User getUser(long id) { ??? }
    public String greet(User user) { ???  }
    public List<User> getAllUsers() { ??? }
    public String greetAll() { ??? }
}

Ohne den UserService läuft natürlich nichts, und wir wollen ihn auch nicht mit gewöhnlichen DI-Frameworks hineinzaubern. Welche Möglichkeiten haben wir dann?

Am naheliegendsten ist sicher, den Service im Konstruktor mitzugeben und in einer Instanzvariable zu speichern. Das Problem dabei ist, dass dann nur dort Objekte konstruiert werden können, wo der „richtige“ Service bekannt ist. Andere benötigte Klassen, die ebenfalls den Service benötigen, müssen als weitere Parameter übergeben werden (was die Initialisierung verkompliziert), oder im Konstruktor initialisiert werden (was zu unschönen Abhängigkeiten führt).

Weiterhin könnte man einfach jeder Methode den Service als Parameter mitgeben, also UserComponent.getUser(long id, UserService service). Das funktioniert, wird aber schnell ziemlich unschön, da dieser Parameter bei jedem einzelnen Aufruf „mitgeschleift“ werden muss.

Wir haben auch eine weitere Möglichkeit, nämlich keinen Wert, sondern eine Funktion zurückzuliefern, als wenn wir sagen wollten: Wenn du uns einen UserService gibst, können wir dir den Wert berechnen: Function getUser(long id).

Mit etwas „Verfeinerung“ ist das die Idee der Reader-Monade. Als erstes stellt sich die Frage, was ist, wenn wir mehr Services oder andere Daten (etwa aus einer Property-Datei) brauchen. Deshalb bündeln wir das Ganze gleich in ein Config-Interface:

public interface Config {
    public UserService userService();
    //später mehr...
}

Dann fällt uns auf, dass alle Methoden den Typ Function<Config, Irgendwas> zurückgeben würden. Da sollten wir uns Schreibarbeit sparen, und diesem neuen Typ gleichzeitig ein paar nützliche Methoden (von denen zwei, nämlich pure und flatMap, das Ding auch formal zu einer Monade machen) verpassen:

//R wie "Reader"
public interface R<A> extends Function<Config, A> {

    @Override
    A apply(Config c);

    static <A> R<A>; pure(A a) {
        return s -> a;
    }

    default <B> R<B> map(Function<A, B> fn) {
        return s -> fn.apply(apply(s));
    }

    default <B> R<B> flatMap(Function<A, R<B>> fn) {
        return s -> fn.apply(apply(s)).apply(s);
    }
}

Damit würde unsere UserComponent so aussehen:

public class UserComponent {

    public R<User> getUser(long id) {
        return config -> config.userService().getUser(id);
    }

    public R<String> greet(User user) {
        return R.pure("Hello " + user.name + "!");
    }

    public R<List<User>> getAllUsers() {
        return config -> config.userService().findAll();
    }

    public R<String> greetAll() {
        return getAllUsers().map(list ->
                list.stream().map(user ->
                        "Hello " + user.name + "!\n").
                        reduce("", String::concat));
    }

}

OK, das sieht erst einmal ziemlich gewöhnungsbedürftig aus. getUser und getAllUsers sind einfach zu verstehen, sie reichen nur die Aufrufe an den Service weiter. Die Methode greet könnte eigentlich ohne Service auskommen, aber jeder weiß, wie schnell sich das ändern kann, und wer will sich schon merken, welche Methode jetzt eine Config braucht und welche nicht? Deshalb wird mit pure einfach ein R erzeugt, das einen Wert zurückliefert und dabei die Config völlig ignoriert. In greetAll sieht man, wie die Methoden aufeinander aufbauen können, in dem man sie mit map- (oder auch flatMap-) Aufrufen miteinander verknüppert. Interessant ist, dass hier überhaupt keine Spur mehr von einem Service oder einem Config-Objekt zu sehen ist, außer dem R-Rückgabetyp.

Wie wird das Ganze nun benutzt? Zuerst einmal braucht man natürlich eine Implementierung von Config. In unserem Mini-Beispiel reicht eine anonyme Klasse:

Config config = new Config() {
    @Override
    public UserService userService() {
        return new UserServiceImpl();
    }
};
...

Dann kann man Methoden wie gewohnt aufrufen, nur muss man überall ein .apply(config) dranhängen:

...
UserComponent userComp = new UserComponent();
System.out.println(userComp.greetAll().apply(config));
...

Natürlich können auch hier einzelne Methoden miteinander verknüpft werden:

...
System.out.println(userComp.getUser(42).
                   flatMap(userComp::greet).apply(config));
...

Das war das Grundprinzip der Reader-Monade als DI-Ersatz. Ich gebe zu, der entstehende Code sieht erst einmal ziemlich ungewöhnlich aus, und ich bin skeptisch, wie gut das Ganze in größeren Systemen funktionieren würde. Trotzdem ist es interessant zu sehen, wie man sich mit „Bordmitteln“ behelfen kann, wenn man kein DI-Framework einsetzen will.

Und wieder mal die Damen…

Ja, ich weiß, ich habe versprochen, die 8 Damen in Ruhe zu lassen. Aber als das geschrieben hatte, war funktionale Programmierung in Java so unbequem, dass ich nicht gedacht hätte, dass man auch nur ansatzweise einmal eine Übersetzung aus Haskell wagen kann. Zur Erinnerung, das hier was mein Ausgangspunkt:

nqueens :: Int -> [[(Int,Int)]] 
nqueens n = foldr qu [[]] [1..n]
    where qu k qss = [ ((j,k):qs) | qs <- qss, j <- [1..n], all (safe (j,k)) qs ]
          safe (j,k) (l,m) = j /= l && k /= m && abs (j-l) /= abs (k-m)

Und das hier war meine Scala-Version:

object queens {
   def nqueens(n: Int) = {
      import math.abs
      type Pos = (Int, Int)
      def safe(p:Pos, q:Pos) = p._1 != q._1 && p._2 != q._2 && 
                               abs(p._1 - q._1) != abs(p._2 - q._2)
      def qu(k: Int, qss:List[List[Pos]]) =
        for(qs <- qss; j <- (1 to n) if qs.forall(safe(_ ,(j,k)))) yield ((j,k) :: qs)
      (1 to n).foldRight(List(List[Pos]()))(qu)
   }
   def main(args:Array[String]) = println(nqueens(8).mkString("\n"))
}

Die folgende Java 8-Version ist beiliebe nicht allein auf meinem eigenen Mist gewachsen. Ich habe nämlich feststellen müssen, dass meine Kentnisse über die javanischen Lambdas zwar recht gut sind, bei der Stream-API aber doch noch einige Bildungslücken vorhanden sind. Danke an alle „Mitwirkenden“ 🙂

Zuerst einmal brauchen wir ein Äquivalent zu Pos, wie gewohnt etwas länglicher in Java:

public class Pos {
    public final int x;
    public final int y;

    public Pos(int x, int y) {
        this.x = x;
        this.y = y;
    }
    public String toString() {
        return String.format("(%d,%d)",x,y);
    }
}

Nun die eigentliche Berechnung, die strukturell immmer noch recht dicht am Original liegt – nur auf mehrere Methoden verteilt und mit etwas sprechenderen Bezeichnern:

import static java.lang.Math.abs;
 
import java.util.*;
import java.util.stream.*;
 
public class Queens {

    private static boolean safe(Pos p, Pos q) {
        return p.x != q.x && p.y != q.y && 
            abs(p.x - q.x) != abs(p.y - q.y);
    }

    private static <T> List<T> snoc(List<T> ts, T t) {
        List<T> result = new LinkedList<>(ts);
        result.add(t);
        return result;
    }

    private static Stream<Integer> range(int fromInclusive, int toInclusive) {
        return IntStream.rangeClosed(fromInclusive, toInclusive).boxed();
    }

    private static Stream<List<Pos>> solveRow(int row, int boardSize, 
                                              Stream<List<Pos>> solutions) {
        return solutions.flatMap(solution ->
            range(1, boardSize).flatMap(column ->
                solution.stream().allMatch(pos ->
                    safe(pos, new Pos(row, column)))
                    ? Stream.of(snoc(solution, new Pos(row, column)))
                    : Stream.empty()));
    }

    public static Stream<List<Pos>> nqueens(int boardSize) {
        return range(1, boardSize).reduce(
            Stream.of(Collections.emptyList()),
            (solutions, row) -> solveRow(row, boardSize, solutions),
            Stream::concat);
    }

    public static void main(String[] args) {
        nqueens(8).forEach(System.out::println);
    }
}

Was an diesem Code meiner Meinung nach am unschönsten ist, ist der Einsatz von reduce für foldLeft. Sicher, es funktioniert hier, aber nur weil es sich um einen sequentiellen Stream handelt. Genaugenommen ist das Stream::concat also gelogen, und ein paralleler Aufruf würde bestimmt lustige Ergebnisse liefern. Es scheint aber keine wirklich „saubere“ Alternative zu geben, die gleichzeitig praktikabel und funktional ist.

Weniger schön ist auch, dass andauernd Listen kopiert werden müssen, weil es leider immer noch keine „richtigen“ immutablen Collections in Java gibt.

Dann hat sich herausgestellt, dass die Benutzung von IntStream ziemlich unbequem ist – hier hatte wohl Performance Vorrang vor Benutzerfreundlichkeit.

Und natürlich merkt man deutlich, wieviel bequemer und übersichtlicher List-Comprehensions in Haskell oder For-Comprehensions in Scala im Vergleich zu handgedrechselten Trainwrecks aus map, flatMap und filter sind.

Trotz aller Kritikpunkte sollte man aber anerkennen, dass es jetzt zumindest möglich ist, solchen funktionalen Code auch in Java zu schreiben, auch wenn er deutlich länger und etwas schlechter zu lesen ist.

Der Aufwand, um zu diesem Ergebnis zu kommen, war recht hoch, und wie schon gesagt, eine kollektive Anstrengung. Ich denke aber, dass das auch eine Gewohnheitsfrage ist, und sehr viel leichter fällt, wenn man sich erst einmal an die Stream-API gewöhnt hat. Außerdem hoffe ich, dass die nächsten Java-Versionen an der Lambda- und vor allem der Stream-Front noch ein wenig nachbessern, um die Programmierung ein wenig intuitiver zu gestalten.

Eine Builder-Variante mit Initialisierungsblöcken

Eines der weniger oft genutzen Java-Features sind Initialisierungsblöcke. Aber wenn sie dann einmal gebraucht werden, können sie ziemlich nützlich sein. Vielleicht auch, um Builder zu schachteln? Und wie könnte das aussehen?

Nehmen wir an, wir müssten eine einfache hierarchische Struktur aufbauen: Eine Menü-Leiste, darin Menüs, und in diesen wiederum Menüpunkte. Mit Initialisierungsblöcken könnte der Aufruf dann so aussehen:

MenuBarBuilder menuBarBuilder = new MenuBarBuilder() {{
    new Menu("menu1") {{
        new Item("item1.1");
        new Item("item1.2");
    }};
    new Menu("menu2") {{
        new Item("item2.1");
        new Item("item2.2");
        new Item("item2.3");
    }};
}};

System.out.println(menuBarBuilder);

Der Einfachheit halber bauen wir hier das Menü nicht zusammen (was ja nicht schwer ist, wenn man die Builder-Struktur erst einmal hat), sondern geben einfach nur eine String-Repräsentation aus. Hier wäre das Ergebnis:

menubar[
  menu 'menu1'[item 'item1.1', item 'item1.2'], 
  menu 'menu2'[item 'item2.1', item 'item2.2', item 'item2.3']]

Okay, bis auf die geschweiften Doppel-Klammern sieht die Verwendungsseite eigentlich gar nicht so schlimm aus. Aber welche Scheußlichkeiten müssen wir bei der Implementierung begehen, damit das funktioniert? Ich finde, auch die Implementierung ist recht erträglich, denn wir benutzen einen einfachen Trick: Menu ist eine innere Klasse von MenuBarBuilder, und kann sich somit bei der Objekterzeugung bei „seiner“ äußeren Instanz „registrieren“ (in diesem Fall einfach in eine vorgegebene Liste eintragen). Genauso ist Item eine innere Klasse von Menu und registriert sich dort. Dieser Aufbau löst eine Menge Probleme – und es wird nicht einmal ein statischer Import benötigt. Hier ist der Code:

import java.util.ArrayList;
import java.util.List;

public class MenuBarBuilder {

    private List<Menu> menus = new ArrayList<>();

    public String toString() {
        return "menubar" + menus.toString();
    }

    public class Menu {
        private final String menuName;
        private List<Item> items = new ArrayList<>();

        public Menu(String name) {
            this.menuName = name;
            MenuBarBuilder.this.menus.add(this);
        }

        public String toString() {
            return "\n  menu '" + menuName + "'" + items;
        }

        public class Item {
            private final String itemName;

            public Item(String name) {
                this.itemName = name;
                Menu.this.items.add(this);
            }

            public String toString() {
                return "item '" + itemName + "'";
            }

        }
    }

}

Ja, das ist alles was man braucht, damit der Aufruf oben funktioniert. Im Endeffekt ergibt sich die Einfachheit daraus, dass wir die Builder genau so ineinanderschachteln, wie auch unsere Struktur später aussehen soll.

Wie ist diese Builder-Variante nun einzuschätzen? Der größte Nachteil ist wohl, dass sie durch die Verwendung von Initialisierungsblöcken einfach ungewohnt ist. Weiterhin skaliert dieser Ansatz nicht so gut: Bei tiefen Hierarchien wird die Builder-Klasse immer länger, weil immer neue innere Klassen dazukommen, die man nicht auslagern kann. Außerdem wird für jeden verwendeten Initialisierungsblock eine anonyme Klassen erzeugt und eine entsprechende class-Datei angelegt, was bei viel geschachteltem „Inhalt“ ebenfalls problematisch sein kann (allerdings würde in diesem Fall auch das „normale“ Builder-Pattern unbequem werden). Auf der Haben-Seite dieses Konstrukts steht ein recht einfacher Aufbau und eine hohe Flexibilität.

Ehrlich gesagt bin ich mir nicht sicher, ob die vorgestellte Builder-Variante eine gute Idee ist, aber es war auf jeden Fall spannend, damit herumzuspielen, und überraschend, wie gut sie funktioniert.

Popularität Programmiersprachen – 2014-08

Hallo Leute,

hier sind die Statistiken des Monats August.

Popularität der Programmiersprachen für August 2014:
(Zuwachs oder Schrumpfung in Prozent über die 13 vorherigen Monate)

Popularität der Programmiersprachen für August 2014:
(Statistische Zahlen zu den Sprachen)

INFO: Die Statistiken für den September und Oktober erscheinen Anfang November.

Viel Spasz weiterhin
Falk

Popularität Programmiersprachen – 2014-07

Hallo Leute,

hier sind die Statistiken des dritten Monats.

Popularität der Programmiersprachen für Juli 2014:
(Zuwachs oder Schrumpfung in Prozent über die 13 vorherigen Monate)

Popularität der Programmiersprachen für Juli 2014:
(Statistische Zahlen zu den Sprachen)

Viel Spasz weiterhin
Falk