Pascal's triangle (Scala, v2.8)

From LiteratePrograms

Other implementations: Scala | Scala, v2.8

This is a Scala version 2.8 program illustrating Pascal's triangle. The program takes a number n as command line argument and prints n rows of the triangle to console output. Machine limitations apply.

Output

Sample output for n=6:

      1
     1 1
    1 2 1
   1 3 3 1
  1 4 6 4 1
1 5 10 10 5 1

Approach

The program uses a Stream, i.e. a lazily evaluated collection, to store the values in the triangle row by row. The element type of the stream is the class Row. The rule to build the tail of the stream is that every element in the tail is created by calling the next method of the preceding element.

<<Store the rows of the triangle lazily>>=
private val triangle: Stream[Row] =
  Stream.cons(new Row, triangle map (_ next))

The Row class

To create a Row, an array of integers for the values of the row must be provided. A convenience constructor is provided for default initialization of the very first row:

<<Define no-arguments constructor>>=
def this () = this(Array(1))

The next method will create new rows by calculating a list of values. Another auxiliary constructor makes this easier by automatically adding the preceding and following values:

<<Define list-argument constructor>>=
def this (xs: List[Int]) = this((1 :: xs ::: List(1)) toArray)

In the general case, the next method uses a sliding iterator that yields successive pairs from its base collection. E.g. if elts is List(1, 4, 6, 4, 1), then elts.iterator.sliding(2).toList yields List(List(1, 4), List(4, 6), List(6, 4), List(4, 1)). This structure is mapped over the sum method and the result is used to initialize an instance of Row:

<<Next row general case>>=
new Row(elts.iterator.sliding(2).toList map (_ sum))

In the base case, the next method simply creates a Row with the values 1, 1.

<<Define next method>>=
def next = elts match {
  case Array(1) => new Row(Array(1, 1))
  case _        => 
    Next row general case
}

The Row class also has a basic method to convert its elements to String.

<<Define inner class Row>>=
class Row (elts: Array[Int]) {
  Define no-arguments constructor
  Define list-argument constructor
  Define next method
  override def toString = elts mkString " "
}

The print method

The main method will send a Stream[String] that represents the top n rows of the triangle to the print method. To improve appearance, the print will attempt to print the rows such that the rows are centered over the last row. maxWidth is the width of the last row, and row.size is the width of this row.

<<Create padding for row>>=
" " * ((maxWidth - row.size) / 2)

The method calculates maxWidth and then simply prints the rows together with padding.

<<Define print method>>=
def print (rows: Stream[String]) {
  val maxWidth = rows.last.size
  rows foreach { row =>
    val padding = Create padding for row
    println(padding + row)
  }
}

The complete program

When run, the program gets n from its command line arguments (or uses a default value of 5). Then it takes n elements (rows) from the triangle stream, converts them to strings and passes them to the print method.

<<pascalstriangle.scala>>=
object PascalsTriangle {
  Store the rows of the triangle lazily
  Define inner class Row
  Define print method    
  def main (args: Array[String]) {
    val n = if (args.length > 0) args(0).toInt else 5
    print(triangle take n map (_ toString))
  }
}