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? 😛

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