# 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 |

## 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>>=defpascalStream(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>>=defshiftRight(row:List[Int]):List[Int]=0::rowdefshiftLeft(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>>=defaddList(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:

defaddList(l1:List[Int], l2:List[Int]):List[Int]=(l1, l2)match{case(_, Nil)=>Nilcase(Nil,_)=>Nilcase(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:

defprintTriangle(triangle:Stream[List[Int]], nrows:Int){valrows=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>>=defprintTriangle(triangle:Stream[List[Int]], nrows:Int){valrows=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>>=valmaxWidth=rows.last.lengthdefpad(row:String){valpadSize=(maxWidth - row.length)/ 2for(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>>=objectPascalsTriangle{shift operations element-wise addition pascal stream print triangledefmain(args:Array[String]){valnrows=if(args.length > 0)args(0).toIntelse5vallazyTriangle=pascalStream(List(1))printTriangle(lazyTriangle, nrows)}}

Download code |