Pascal's Triangle

Pascal's triangle can be defined directly

> pascal1 0 _ = 1
> pascal1 _ 0 = 1
> pascal1 n m = pascal1 (n-1) m + pascal1 n (m-1)

This direct implementation is very inefficient, much as the direct computation of the Fibonacci sequence

> fib 0 = 0
> fib 1 = 1
> fib n = fib (n-1) + fib (n-2)

is inefficient. An elegant way to compute this sequence exploits sharing and laziness.

> fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

So, for example, fib 6 == fibs!!6. (You can see the above defintion and others on the Haskell wiki.) A nice exercise is to pull the same stunt with Pascal's triangle. Instead of a list we need a tree and some obvious operations on it.

> data T a = T a (T a) (T a)
> 
> left :: T a -> T a
> left (T _ l _) = l
> 
> right :: T a -> T a
> right (T _ _ r) = r
> 
> value :: T a -> a
> value (T x _ _) = x
> 
> zipTreeWith :: (a -> b -> c) -> T a -> T b -> T c
> zipTreeWith op (T x1 l1 r1) (T x2 l2 r2) =
>       T (op x1 x2) (zipTreeWith op l1 l2) (zipTreeWith op r1 r2)

We can now define a generic (replacing addition with an arbitrary operation op) Pascal's triangle.

> pascals' :: a -> (a -> a -> a) -> T a
> pascals' i op = T i l r
>    where m = zipTreeWith op l r
>          l = leftone m
>          r = rightone m
>          leftone t = T i (leftone (left t)) t
>          rightone t = T i t (rightone (right t))

(The above version is due to JS and I prefer it to the version I came up with.) We get what we want by specialising.

> pascals :: T Integer
> pascals = pascals' 1 (+)

We make it easy to get values out of the tree with this helper:

> pascalsHelper n m = value $ (iterate right ((iterate left pascals)!!n))!!m

Finally we can test it.

> main = print $ and [pascalsHelper x y == pascal1 x y| x <- [1..5], y <- [1..5]]