Laziness helps implementing a tabulated version of the naive algorithm to compute binomial coefficients.

`binomial :: Int -> Int -> Integer`

binomial n k = binomialTab!!n!!k

Here is an infinite table of binomial coefficients:

`binomialTab :: [[Integer]]`

binomialTab = [[ binomialCalc n k | k <- [0..n]] | n <- [0..]]

It is defined by mutual recursion with a function that computes new values using old ones.

`binomialCalc :: Int -> Int -> Integer`

binomialCalc n k

| k == 0 || k == n = 1

| k == 1 = toInteger n

| otherwise = binomial (n-1) (k-1) + binomial (n-1) k

That's it! The constant `binomialTab`

is evaluated exactly as much as necessary to compute the demanded coefficients. If values have been computed previously, they are memoized and never recomputed even for completely unrelated calls to `binomial`

.