Pascal's triangle (Scala)

From LiteratePrograms

Other implementations: Scala | Scala, v2.8

This is a Scala program illustrating Pascal's triangle. Here's an example of what you'll see if you run this program:

$ scala PascalsTriangle 10
             1
            1 1
           1 2 1
          1 3 3 1
         1 4 6 4 1
       1 5 10 10 5 1
     1 6 15 20 15 6 1
    1 7 21 35 35 21 7 1
  1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1

Contents 1 Approach 2 Implementation 3 Printing the triangle 4 Completing the program

Approach

The basic method used here to compute the triangle is to generate each new row as the sum of two "shifted" versions of the previous row, where the shifting is accomplished by appending a zero to the end of the row. So, for example, the row

1 2 1

will be "shifted" both left and right to produce

1 2 1 0
0 1 2 1

Summing these two shifted rows yields

1 3 3 1

which is the next row of the triangle.

Our implementation will use this approach to lazily compute the triangle as a Stream of rows:

<<pascal stream>>=
def pascalStream(row: List[Int]): Stream[List[Int]] =
  Stream.cons(row, pascalStream(addList(shiftLeft(row), shiftRight(row))))

Implementation

We use lists of integers to represent each row. Thus the two shifting operations are implemented as operations on a list. The shift right is easily accomplished by adding a 0 to the head of the list. The shift to the left is a little more involved, since it requires inserting a value at the end of the list. In this case, we've opted to concatenate the row with a new list containing just the value 0.

<<shift operations>>=
def shiftRight(row: List[Int]): List[Int] = 0::row
def shiftLeft(row: List[Int]): List[Int] = row:::List(0)  

Combining the two shifted versions of a row is also an operation on lists. A straightforward way to perform an element-wise sum on the two lists is to zip the two lists together -- which produces a single list of 2-tuples containing pairs of elements from each list -- and then map a sum across that single list.

<<element-wise addition>>=
def addList(l1: List[Int], l2: List[Int]): List[Int] = {
  (l1 zip l2) map { case (x, y) => x + y }
} 

A slightly more efficient way to achieve the same end would be to perform the summing operation at the same time as the two lists are combined, instead of making two passes through the lists. Here's a version of addList that performs summing in this way:

def addList(l1: List[Int], l2: List[Int]): List[Int] = (l1, l2) match { 
  case (_, Nil) => Nil
  case (Nil, _) => Nil
  case (h1::t1, h2::t2) => (h1 + h2)::addList(t1, t2)
}

Printing the triangle

Of course, generating lots of nifty Pascal's triangles isn't all that helpful if we can't see them. We could just directly print the elements of the triangle by converting rows to strings and printing them:

def printTriangle(triangle: Stream[List[Int]], nrows: Int) {
  val rows = triangle.take(nrows).map(_.mkString(" "))
  rows foreach { println _ }
}

But taking this approach produces an output that isn't much like the classical presentation of Pascal's triangle because everything is left-justified:

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1 

We can make a more nicely formatted triangle by adding a little padding to the start of each row:

<<print triangle>>=
def printTriangle(triangle: Stream[List[Int]], nrows: Int) {
  val rows = triangle.take(nrows).map(_.mkString(" "))
  row padding
  rows foreach { row => pad(row); println(row) }
}

That way, the rows are center-justified, like this:

    1
   1 1
  1 2 1
 1 3 3 1
1 4 6 4 1

How much padding do we need to add? Well, we won't bother padding the widest row -- that way it'll be flush against the left side of the screen -- and then print enough spaces before each row that the distance from the left edge of the screen to the center of that row is (roughly) the same as the distance to the center of the widest row.

<<row padding>>=
val maxWidth = rows.last.length
def pad(row: String) {
  val padSize = (maxWidth - row.length) / 2
  for(i <- 1 to padSize) { print(" ") }
}

Completing the program

To round out our Pascal's triangle program, we'll wrap everything in a singleton object, and add a main method that reads a number of rows to print from the command-line arguments. In this case we want to print triangles starting from the smallest row, so we seed pascalStream with List(1).

<<PascalsTriangle.scala>>=
object PascalsTriangle {
  shift operations
  element-wise addition
  pascal stream
  print triangle
  def main(args: Array[String]) {
    val nrows = if (args.length > 0) args(0).toInt else 5
    val lazyTriangle = pascalStream(List(1))
    printTriangle(lazyTriangle, nrows)
  }
}

Download code