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.

Nochmal die Damen

Die berühmten 8 Damen hatte ich schon mal abgehandelt, aber das folgende Stückchen Haskell hat es mir angetan:

--http://www.reddit.com/r/programming/comments/62j4m/nqueens_in_haskell/

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)

Das sieht ein ganzes Stück besser aus als mein eigener Versuch, und die Logik dahinter ist bestechend einfach: safe testet, ob zwei Positionen „sicher“ sind (sich also nicht in der gleichen Reihe, Spalte oder Diagonale befinden). qu nimmt eine Liste mit allen Teillösungen für die Reihen kleiner als k, und prüft dann für jede Liste qs, welche Spalten j in der Reihe k „sicher“ sind, und sammelt alle entsprechenden Listen mit den neuen Positionen. Nun wird qu für 1 bis n aufgerufen, und dabei jeweils die Teillösung des letzten Aufrufs übergeben, was man mit foldr realisieren kann.

Und hier meine Scala-Übersetzung, die sich wieder möglichst nah ans Original halten soll:

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"))
}

Zuerst importiere ich die abs-Methode und definiere den Typ (Int,Int) als Pos, weil ich ihn häufiger benötige. Lokale Hilfsfunktionen schreibt man in Scala besser zuerst, so dass man im Beispiel die umgekehrte Reihenfolge wie in Haskell hat. Bei safe gibt es kaum eine Änderung, wenn man davon absieht, dass in Scala leider kein Pattern Matching in der Argumentliste funktioniert. Die Methode qu wird im Prinzip unverändert übernommen, auch wenn die Syntax deutlich abweicht. Ich denke man sieht hier gut, wie stark Haskell den Entwurf von Scala beeinflusst hat, auch wenn man das Scala nicht unbedingt auf den ersten Blick ansieht. Zu guter Letzt kommt der Aufruf von qu über foldRight. In Scala ist foldLeft üblicher und auch performanter (da Haskell „lazy“ ist, scheint es dort umgekehrt zu sein), aber ich will ja dicht am Original bleiben. Da die Argumente für qu in der richtigen Reihenfolge geliefert werden, läßt sich das (k,l) => qu(k,l) wahlweise mit qu(_,_) oder schlicht mit qu abkürzen. Die main-Methode testet den klassischen 8×8-Fall.

Wie ich schon im oben genannten Artikel erwähnt habe, kann man mit Scala normalerweise sehr dicht an einer Vorlage in einer funktionalen Sprache wie Haskell, Clean oder ML bleiben. Natürlich wird durch die unvollständige Typinferenz und ausführlichere „Zeichensetzung“ in Scala alles ein wenig länglicher, aber strukturell ähneln sich die beiden Programme sehr stark. Auch die „Werkzeugkisten“ der beiden Sprachen haben viel gemeinsam, während Dinge wie Tupel, foldRight, Pattern Matching und List Comprehensions in Java fehlen.

So, in Zukunft werde ich die Damen in Ruhe lassen, zumindest hier im Blog… Hatte ich eigentlich schon erwähnt, dass ich Single bin? 😛

Wie funktional ist Scala?

Nachdem ich ein wenig über die funktionale Sprache Clean gelesen hatte, wollte ich auch mal ein Beispiel selber programmieren. Das fiel mir erstaunlich leicht, denn Clean ähnelt der Sprache Haskell, mit dem ich auch schon ein wenig herumgespielt habe. Das Ergebnis ist sicher kein Meilenstein funktionaler Programmierung, aber das Programm läuft. Hier sind also meine acht Damen in Clean:

//Clean 2.2
module Queens
import StdEnv

Start = queens []

queens list 
    | length list == 8 = [list]
    | otherwise = flatten (map (\x = queens [x:list]) (filter (valid list) [1..8]))
    where 
    valid t h = not (isMember h t || diagonal (+) (h+1) t || diagonal (-) (h-1) t)
        where
        diagonal _ _ [] = False
        diagonal op n [h:t] = n == h || diagonal op (op n 1) t

So sieht Code aus, mit dem man OO-Programmierer erschrecken kann. Aber mit ein paar zusätzlichen Informationen klärt sich das Bild: Ergebnis der Berechnung soll eine Liste von Int-Listen sein. Dabei hat jede Int-Liste acht Stellen und gibt eine Brettposition wieder (die n-te Zahl gibt dabei an, in welcher Spalte die Dame in der n-ten Reihe steht). Hat unsere Liste die gewünschte Länge 8, sind wir fertig. Andernfalls (otherwise) nehmen wir die Spaltenpositionen von 1 bis 8, behalten nur die, die nicht von den vorangegeangenen bedroht werden (filter(valid list)), fügen die jeweilige Position an die vorhandene Liste, rufen damit Queens rekursiv auf und liefern die Ergebnisse der einzelnen Aufrufe zusammengefügt (flatten) zurück. Die Unterfunktion valid hat drei Bedrohungsarten zu berücksichtigen: gleiche Spalte und gleiche Diagonale aufsteigend oder absteigend. Für die Diagonalen gibt es eine Unter-Unterfunktion diagonal, bei der auch der Operator mitgeliefert wird, der die Richtung der Diagonale bestimmt (also, ob zur vorhandenen Position +1 oder -1 in der nächsten Zeile gerechnet wird). Eigentlich ganz logisch, wenn man sich nicht von der Syntax erschrecken lässt.

Nun wird Scala oft als objektorientierte Sprache mit etwas funktionalem Flair beschrieben. Das ist auch wenig verwunderlich, schließlich läuft Scala auf der JVM, und die Kompatibilität zu Java wird (zu recht) immer wieder betont. Codeschnipsel, die Scala als „besseres Java“ propagieren sollen, tun ein übriges, um dieses Bild zu festigen. Dabei wird übersehen, dass Scala viel, viel weiter in Richtung funktionaler Programmierung geht als andere gebräuchliche OO-Sprachen, und damit meiner Meinung nach ziemlich genau in der Mitte zwischen den Paradigmen steht. Wie sieht nun mein Beispiel in Scala aus, wenn ich versuche, mich möglichst dicht ans Original zu halten?

object Queens {
  def main(args: Array[String]) { println(queens(Nil)) }
   
  def queens(list: List[Int]):List[List[Int]] = list match {
    case full if full.size == 8 => List(full)
    case _ => def valid(t:List[Int])(h:Int) = {
        def diagonal(op: (Int,Int)=>Int, n:Int, li:List[Int]): Boolean = li match {
          case Nil => false
          case h :: t => n == h || diagonal(op, op(n,1), t)
        }
        ! (t.contains(h) || diagonal(_+_, h+1, t) || diagonal(_-_, h-1, t))
      }
      (1 to 8 toList).filter(valid(list)).map(n => queens(n :: list)).flatten
  }
}

Ich finde, das sieht ziemlich ähnlich aus. Scala hat im Gegensatz zu Haskell und Clean nur eine partielle Typinferenz (der übliche Hindley-Milner-Algorithmus verträgt sich mit OO und vor allem Methodenüberladung nicht), so dass die Aufruftypen und bei rekursiven Funktionen auch die Rückgabetypen angegeben werden müssen. Lokale Funktionsdefinitionen funktionieren ähnlich wie das originale where, wobei man die lokale Funktion besser vor der Benutzung definiert. Der rekursive Aufruf von queens verwendet die gleichen Funktionen wie das Original. In diesem Fall finde ich, dass die objektorientierte Schreibweise vorteilhafter ist: Nimm die Positionsliste, filtere sie nach gültigen Positionen, rufe queens mit der um die jeweilige neue Position ergänzte Liste rekursiv auf, und füge die Ergebnisse zusammen. Man erhält also eine Abarbeitungsreihenfolge in Leserichtung, und nicht umgekehrt.

Der vorgestellte Code zeigt, wie weit man sich in Scala von Java wegbewegen kann, denn dort könnte man nicht einmal annähernd etwas ähnliches schreiben. Wenn man es will, ist mit Scala ein sehr funktionaler Stil möglich, nicht ganz wie in Haskell oder Clean, aber doch sehr dicht dran. Aber das Schöne ist, dass man dazu nicht gezwungen wird. Es ist immer gut, wenn man sich entscheiden kann. Funktionale Programmierung ist keine „Silver Bullet“, aber es lohnt, sich damit zu beschäftigen.

Nachtrag:
Martin Odersky hat gerade einen Artikel veröffentlicht, in dem er Scala als „postfunktionale Sprache“ bezeichnet, und auch auf andere Diskussionen um Scalas „Funktionalität“ verweist. Die neue Bezeichnung gefällt mir. Und Java könnte man dann unter den „dysfunktionalen Sprachen“ einordnen 😀