Game of Life mit Scala - das Tutorial - JAXenter
Teil 2: Funktionale Programmierung

Game of Life mit Scala – das Tutorial

Heiko Seeberger

Collections mappen

Nun wollen wir die nächste Generation bestimmen. Diese setzt sich aus den Zellen zusammen, die am Leben bleiben, und denjenigen, die von den Toten auferstehen:

def next: Generation = {
  val stayingAlive = ...
  val wakingFromDead = ...
  new Generation(stayingAlive ++ wakingFromDead)
}

Hier sehen wir wieder, dass wir kein return benötigen, weil in Scala einfach das Ergebnis der letzten Zeile als Rückgabewert verwendet wird. Die beiden Variablen stayingAlive und wakingFromDead sollen Sets sein, sodass wir mit der Methode ++ ein neues Set von lebendigen Zellen für die nächste Generation erzeugen können.

stayingAlive können wir mit dem bisher besprochenen implementieren, indem wir die aktuellen lebendigen Zellen filtern, sodass nur solche überleben, die zwei oder drei Nachbarzellen haben:

val stayingAlive =
  aliveCells filter { 2 to 3 contains aliveNeighbours(_).size }

Hier verwenden wir eine weitere Kurzform für die Notation von Funktionsliteralen: Wir verzichten auf Parameterliste und Pfeilsymbol und schreiben gleich den Rumpf der Funktion, wobei wir den Unterstrich als Platzhalter für Parameter verwenden. Hätten wir mehrere Parameter, dann bräuchten wir auch mehrere Unterstriche, aber hier haben wir ohnehin nur einen. Natürlich könnten wir auch die „ausführliche“ Notation anwenden: aliveCells filter { cell => 2 to 3 contains aliveNeighbours(cell).size }.

Nun müssen wir noch wakingFromDead ermitteln. Dazu müssen wir zum Glück nicht alle toten Zellen auf dem Spielfeld betrachten, sondern nur diejenigen in der Nachbarschaft von lebendigen, denn es können ja nur solche zum Leben erwachen, die genau drei Nachbarn haben. Deshalb müssen wir nun von den lebendigen Zellen zu deren toten Nachbarzellen kommen. Für eine einzelne Zelle haben wir schon die Methode deadNeighbours, aber wie erhalten wir die toten Nachbarzellen aller lebendigen Zellen? Im imperativen Programmierstil, der in Java oft zum Einsatz kommt, würden wir vermutlich eine Schleife programmieren und im Detail ausprogrammieren, wie wir zum gewünschten Ergebnis kommen. In der funktionalen Programmierung können wir uns das Leben einfacher machen, indem wir einfach sagen, was wir erreichen wollen und das Wie den bereitgestellten Bibliotheken überlassen.

Nochmals die Aufgabenstellung, etwas anders und in zwei Schritten formuliert: Wir gehen von der Menge der lebendigen Zellen (aliveCells) aus und wollen diese in die Menge der toten Nachbarzellen transformieren. Anschließend müssen wir noch filtern, ob diese toten Nachbarzellen wiederum genau drei lebendige Nachbarn haben.

Für den ersten Schritt versuchen wir es als Erstes mit der Collection-Methode map, mit der wir aus einer Collection mittels Transformation eine neue erzeugen können. Ein Beispiel in der REPL:

scala> List(1, 2, 3) map { x => x + 1 }
res0: List[Int] = List(2, 3, 4)

Wenn wir das auf unser Beispiel übertragen, dann könnte das folgendermaßen aussehen: aliveCells map deadNeighbours. Wieder macht der Scala Compiler für uns die Methode deadNeighbours zur Funktion, sodass dieser Code kompiliert. Allerdings ist das Resultat nicht das erwünschte, denn wir transformieren ein Set[Cell] in ein Set[Traversable[Cell]], weil deadNeighbours ja für jede Cell ein Traversable[Cell] zurückgibt. Für solche Fälle gibt es die Collection-Methode flatMap, die quasi verschachtelte Collections flachklopft. Ebenfalls ein Beispiel in der REPL:

scala> List(1, 2, 3) map { x => List(x - 1, x, x + 1) }
res0: List[List[Int]] = List(List(0, 1, 2), List(1, 2, 3), List(2, 3, 4))
scala> List(1, 2, 3) flatMap { x => List(x - 1, x, x + 1) }
res1: List[Int] = List(0, 1, 2, 1, 2, 3, 2, 3, 4)

Damit können wir den wakingFromDead folgendermaßen implementieren:

val wakingFromDead =
  aliveCells flatMap deadNeighbours filter { aliveNeighbours(_).size == 3 }

Hier verketten wir zwei Funktionsaufrufe. Zuerst rufen wir flatMap auf aliveCells auf und übergeben dabei deadNeighbours als Argument. Das Resultat bis dorthin ist ein Set[Cell], das alle toten Nachbarn von lebendigen Zellen enthält. Darauf rufen wir filter mit einem Funktionsliteral auf, das nur diejenigen toten Zellen übrig lässt, die drei lebendige Nachbarn haben.

Listing 2 zeigt den kompletten Code für die Klasse Generation und Listing 3 ein paar Tests, die auch zwei interessante Ausgangsgenerationen zeigen. Da wäre zum einen der so genannte Blinker in Form von drei horizontal angeordneten Zellen, die zu drei vertikal angeordneten werden und umgekehrt. Und zum anderen der so genannte Block als Beispiel für eine Generation, die konstant bleibt.

Listing 2: Generation.scala
package com.weiglewilczek.gameoflife
class Generation(val aliveCells: Set[Cell] = Set.empty) {
  require(aliveCells != null, "aliveCells must not be null!")
  def next: Generation = {
    val stayingAlive =
      aliveCells filter { 2 to 3 contains aliveNeighbours(_).size }
    val wakingFromDead =
      aliveCells flatMap deadNeighbours filter { aliveNeighbours(_).size == 3 }
    new Generation(stayingAlive ++ wakingFromDead)
  }
  private def aliveNeighbours(cell: Cell) =
    cell.neighbours filter aliveCells.contains
  private def deadNeighbours(cell: Cell) =
    cell.neighbours filter { neighbour => !(aliveCells contains neighbour) }
}
Listing 3: GenerationSpec.scala
package com.weiglewilczek.gameoflife
import org.specs.Specification
class GenerationSpec extends Specification {
  "Generation.next" should {
    "return an empty Generation for the empty Generation" in {
      new Generation(Set.empty).next.aliveCells mustBe Set.empty
    }
    "yield three horizontal cells for three vertical cells" in {
      val vertical3 = Set(Cell(0, -1), Cell(0, 0), Cell(0, 1))
      val horizontal3 = Set(Cell(-1, 0), Cell(0, 0), Cell(1, 0))
      new Generation(vertical3).next.aliveCells mustEqual horizontal3
    }
    "stay constant for a 2x2 block of cells" in {
      val block = Set(Cell(0, 0), Cell(0, 1), Cell(1, 0), Cell(1, 1))
      new Generation(block).next.aliveCells mustEqual block
    }
  }
}
Geschrieben von
Heiko Seeberger
Kommentare

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht.