Scala n00b: Critique my code

Question

G'day everyone,

I'm a Scala n00b (but am experienced with other languages) and am learning the language as I find time - very much enjoying it so far!

Usually when learning a new language the first thing I do is implement Conway's Game of Life, since it's just complex enough to give a good sense of the language, but small enough in scope to be able to whip up in a couple of hours (most of which is spent wrestling with syntax).

Anyhoo, having gone through this exercise with Scala I was hoping the Scala gurus out there might take a look at the code I've ended up with and provide feedback on it. I'm after anything - algorithmic improvements (particularly concurrent solutions!), stylistic improvements, alternative APIs or language constructs, disgust at the length of my function names - whatever feedback you've got, I'm keen to hear it!

You should be able to run the following script via "scala GameOfLife.scala" - by default it will run a 20x20 board with a single glider on it - please feel free to experiment.

// CONWAY'S GAME OF LIFE (SCALA)
abstract class GameOfLifeBoard(val aliveCells : Set[Tuple2[Int, Int]])
{
  // Executes a "time tick" - returns a new board containing the next generation
  def tick : GameOfLifeBoard

  // Is the board empty?
  def empty : Boolean = aliveCells.size == 0

  // Is the given cell alive?
  protected def alive(cell : Tuple2[Int, Int]) : Boolean = aliveCells contains cell

  // Is the given cell dead?
  protected def dead(cell : Tuple2[Int, Int]) : Boolean = !alive(cell)

}


class InfiniteGameOfLifeBoard(aliveCells : Set[Tuple2[Int, Int]])
  extends GameOfLifeBoard(aliveCells)
{
  // Executes a "time tick" - returns a new board containing the next generation
  override def tick : GameOfLifeBoard = new InfiniteGameOfLifeBoard(nextGeneration)

  // The next generation of this board
  protected def nextGeneration : Set[Tuple2[Int, Int]] = aliveCells flatMap neighbours filter shouldCellLiveInNextGeneration

  // Should the given cell should live in the next generation?
  protected def shouldCellLiveInNextGeneration(cell : Tuple2[Int, Int]) : Boolean = (alive(cell) && (numberOfAliveNeighbours(cell) == 2 || numberOfAliveNeighbours(cell) == 3)) ||
                                                                                    (dead(cell)  && numberOfAliveNeighbours(cell) == 3)

  // The number of alive neighbours for the given cell
  protected def numberOfAliveNeighbours(cell : Tuple2[Int, Int]) : Int = aliveNeighbours(cell) size

  // Returns the alive neighbours for the given cell
  protected def aliveNeighbours(cell : Tuple2[Int, Int]) : Set[Tuple2[Int, Int]] = aliveCells intersect neighbours(cell)

  // Returns the coordinates of all of the neighbouring cells of the given cell
  protected def neighbours(cell : Tuple2[Int, Int]) : Set[Tuple2[Int, Int]] = Set((cell._1-1, cell._2-1), (cell._1, cell._2-1), (cell._1+1, cell._2-1),
                                                                                  (cell._1-1, cell._2),                         (cell._1+1, cell._2),
                                                                                  (cell._1-1, cell._2+1), (cell._1, cell._2+1), (cell._1+1, cell._2+1))

  // Information on where the currently live cells are
  protected def xVals  = aliveCells map { cell => cell._1 }
  protected def xMin   = (xVals reduceLeft (_ min _)) - 1
  protected def xMax   = (xVals reduceLeft (_ max _)) + 1
  protected def xRange = xMin until xMax + 1

  protected def yVals  = aliveCells map { cell => cell._2 }
  protected def yMin   = (yVals reduceLeft (_ min _)) - 1
  protected def yMax   = (yVals reduceLeft (_ max _)) + 1
  protected def yRange = yMin until yMax + 1


  // Returns a simple graphical representation of this board
  override def toString : String =
  {
    var result = ""

    for (y <- yRange)
    {
      for (x <- xRange)
      {
        if (alive (x,y)) result += "# "
        else result += ". "
      }

      result += "\n"
    }

    result
  }

  // Equality stuff
  override def equals(other : Any) : Boolean =
  {
    other match
    {
      case that : InfiniteGameOfLifeBoard => (that canEqual this) &&
                                             that.aliveCells == this.aliveCells
      case _ => false
    }
  }

  def canEqual(other : Any) : Boolean = other.isInstanceOf[InfiniteGameOfLifeBoard]

  override def hashCode = aliveCells.hashCode

}


class FiniteGameOfLifeBoard(val boardWidth : Int, val boardHeight : Int, aliveCells : Set[Tuple2[Int, Int]])
  extends InfiniteGameOfLifeBoard(aliveCells)
{
  override def tick : GameOfLifeBoard = new FiniteGameOfLifeBoard(boardWidth, boardHeight, nextGeneration)

  // Returns the coordinates of all of the neighbouring cells of the given cell
  override protected def neighbours(cell : Tuple2[Int, Int]) : Set[Tuple2[Int, Int]] = super.neighbours(cell) filter { cell => cell._1 >= 0 && cell._1 < boardWidth &&
                                                                                                                               cell._2 >= 0 && cell._2 < boardHeight }

  // Information on where the currently live cells are
  override protected def xRange = 0 until boardWidth
  override protected def yRange = 0 until boardHeight

  // Equality stuff
  override def equals(other : Any) : Boolean =
  {
    other match
    {
      case that : FiniteGameOfLifeBoard => (that canEqual this) &&
                                           that.boardWidth  == this.boardWidth &&
                                           that.boardHeight == this.boardHeight &&
                                           that.aliveCells  == this.aliveCells
      case _ => false
    }
  }

  override def canEqual(other : Any) : Boolean = other.isInstanceOf[FiniteGameOfLifeBoard]

  override def hashCode : Int =
  {
    41 * (
      41 * (
        41 + super.hashCode 
      ) + boardHeight.hashCode
    ) + boardWidth.hashCode
  }

}


class GameOfLife(initialBoard: GameOfLifeBoard)
{
  // Run the game of life until the board is empty or the exact same board is seen twice
  // Important note: this method does NOT necessarily terminate!!
  def go : Unit =
  {
    var currentBoard   = initialBoard
    var previousBoards = List[GameOfLifeBoard]()

    while (!currentBoard.empty && !(previousBoards contains currentBoard))
    {
      print(27.toChar + "[2J")  // ANSI: clear screen
      print(27.toChar + "[;H")  // ANSI: move cursor to top left corner of screen
      println(currentBoard.toString)
      Thread.sleep(75)

      // Warning: unbounded list concatenation can result in OutOfMemoryExceptions  ####TODO: replace with LRU bounded list
      previousBoards = List(currentBoard) ::: previousBoards
      currentBoard   = currentBoard tick
    }

    // Print the final board
    print(27.toChar + "[2J")  // ANSI: clear screen
    print(27.toChar + "[;H")  // ANSI: move cursor to top left corner of screen
    println(currentBoard.toString)
  }
}



// Script starts here
val simple = Set((1,1))
val square = Set((4,4), (4,5), (5,4), (5,5))
val glider = Set((2,1), (3,2), (1,3), (2,3), (3,3))

val initialBoard = glider

(new GameOfLife(new FiniteGameOfLifeBoard(20, 20, initialBoard))).go
//(new GameOfLife(new InfiniteGameOfLifeBoard(initialBoard))).go

// COPYRIGHT PETER MONKS 2010

One specific question: I removed the return types from all of the functions at one point (Scala type inference ftw!), but found the code actually got harder to read. Are there any conventions about when to leave return types in vs letting Scala figure them out (beyond those cases where they're necessary)?

Thanks!
Peter

Answer 1

Tuple2 (and all TupleN) types and values can be written with parens:

type cell = (Int, Int)
// same as:
type cell = Tuple2[Int, Int]

val cell00 = (0, 0)
// same as:
val cell00 = Tuple2(0, 0)

Answer 2

The for loop for creating the toString result is a lot less compact than it could be.

You want

yRange.map(y => {
  xRange.map(x => if (alive(x,y)) "#" else ".").mkString(" ")
}).mkString("\n")

Also a until b+1 is better written as a to b.

P.S. The (i => { thing is the main reason I switched from the separate-line brace style to the end-of-line style.

Answer 3

Tuples are great, but things might read easier if you created and used a "Cell" class.

Answer 4

I had a nice idea for adding concurrency, but never got to it. Anyway, here's one of my own implementations of it. I planned to blog about it -- and many variations on the theme -- but life got in the way. :-)

As for your question, I prefer to always declare the return type of my methods, unless it's really a very simple one liner.

Answer 5

You can replace

protected def neighbours(cell : Tuple2[Int, Int]) : Set[Tuple2[Int, Int]] = 
   Set((cell._1-1, cell._2-1), (cell._1, cell._2-1), (cell._1+1, cell._2-1),
   (cell._1-1, cell._2),                         (cell._1+1, cell._2),
   (cell._1-1, cell._2+1), (cell._1, cell._2+1), (cell._1+1, cell._2+1))

with:

protected def neighbours(cell : Tuple2[Int, Int]) : Set[Tuple2[Int, Int]] = { 
  val direction = Set(-1,0,1)
  for(x <- direction; y<-direction; if(x !=0 || y != 0)) 
    yield (cell._1+x,cell._2+y)
}

var previousBoards, var currentBoard: If you define the go method recursively you can define these as vals.

while (!currentBoard.empty && !(previousBoards contains currentBoard)): If you implement Iterable with InfiniteGameOfLifeBoard you can use a for expression here.

The obvious: Why's the documentation in a format that cannot be processed by scaladoc?