(My answer to this Stack Overflow question.)

Start out with the triangle itself:

``````     1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
...
``````

You should notice that to write down the next row, you must apply this rule: sum the previous rows’ adjacent elements, using a `0` for the lonely edge elements. Visually:

``````    0   1   0
\+/ \+/
0   1   1   0
\+/ \+/ \+/
0   1   2   1   0
\+/ \+/ \+/ \+/
1   3   3   1
...
``````

Operationally, that looks like this:

``````For row 0:
  (it's a given; i.e. base case)

For row 1:
[0, 1]   <- row 0 with a zero prepended ( ++ row 0)
+  +
[1, 0]   <- row 0 with a zero appended  (row 0 ++ )
=  =

For row 2:
[0, 1, 1]
+  +  +
[1, 1, 0]
=  =  =
[1, 2, 1]

Generally, for row N:

 ++ row(N-1)
row(N-1) ++ 
``````

Remember that element-wise addition of lists in Haskell is `zipWith (+)`.

Thus we arrive at the following Haskell definition:

``````pascal 0 = 
pascal n = zipWith (+) ( ++ pascal (n-1)) (pascal (n-1) ++ )
``````

Or in a fashion similar to the famous “lazy fibs”:

``````pascals =  : map (\xs -> zipWith (+) ( ++ xs) (xs ++ )) pascals
``````