One of the exercises in Structure and Implementation of Computer Programs deals with generating elements of the Pascal’s Triangle. The following pattern of numbers is called Pascal’s Triangle
1 2 3 4 5 6 7 

The numbers at the edge of the triangle are 1, and each number inside is the sum of two numbers above it. The exercise asks us to find the elements of Pascal’s triangle by means of a recursive process.
I find it helpful to deskew the triangle so that the rows and columns line up visually. Here’s the modified triangle:
1 2 3 4 5 6 7 

I decided to write the solution in Haskell, and here it is:
1 2 3 4 5 6 7 8 

This code is great for generating the element at a given row and column (e.g. pascal 3 2
produces 3
), but not so great if we wanted to generate the entire triangle up to n
rows, as we would recursively generate the elements at row n1
multiple times.
In order to generate the entire triangle, it is better to do it via an iterative process as follows: generate the first row, and from that generate the second row, and so on. I other words, we are generating the next row of the triangle, by adding each pair in the current row. My solution is as follows:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 

Here are a couple of examples of generating the triangle:
1 2 3 4 5 6 7 8 9 10 11 12 13 

The function pascalTriangle
can be made more concise by using the builtin iterate
instead of my pascalHelper
:
1 2 

By this point, I was reasonably satisfied with the code. However, being relatively new to Haskell, I decided to explore and see if there were other (and possibly better and more idiomatic) ways to solve this problem. My favorite was by Neil Mitchell, who solved the problem in two lines! I encourage you to go read Neil’s entire post. Here’s the twoline version of Haskell’s triangle:
1 2 3 4 5 

In my view, this code is very elegant and beautiful and does a great job of highlighting the power of Haskell.