= Solution
Represent <Pascal's triangle> by an infinite outer <lazy list>, each of whose elements is one finite row. Pad the preceding row with zero on its left and on its right, then add corresponding entries:
``
pascal :: [[Integer]]
pascal = iterate next [1]
where
-- Padding supplies the two boundary entries as well as the interior sums.
next :: [Integer] -> [Integer]
next row = zipWith (+) (0 : row) (row ++ [0])
``
Here `iterate next [1]` begins `[[1],[1,1],[1,2,1],[1,3,3,1],...]`. Every call to `next` receives a finite row, so its final zero is reachable. <Lazy evaluation> produces any requested finite prefix without trying to finish the infinite outer <list>.
Indexing rows and columns from zero, <Pascal's rule> says
$$
\boxed{\operatorname{pascal}_n=\left[\binom n0,\binom n1,\ldots,\binom nn\right],\qquad \binom{n+1}j=\binom n{j-1}+\binom nj.}
$$
Take out-of-range <binomial coefficients> to be zero. The seed is the zeroth row, and the padded <addition> implements this identity at every position, including the two boundaries. <Mathematical induction> therefore proves every generated row correct. Using unbounded <integers> prevents overflow. Generating rows zero through $r$ takes $\Theta(r^2)$ arithmetic operations, with additional bit costs as the <binomial coefficients> grow.
Back to article page
