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