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.
