binomial.hs

import Data.List (unfoldr)

-- Recursive definition of binomial coefficient
-- Can take exponential time in n + k
-- Try binom_r 25 10 -- already takes several seconds

binom_r :: Int -> Int -> Integer
binom_r n 0 = 1
binom_r n k | n == k = 1
            | otherwise = binom_r (n-1) (k-1) + binom_r (n-1) k

-- List-unfolding definition of binomial coefficient
-- Roughly quadratic time and space in (n + k)

binom_l :: Int -> Int -> Integer
binom_l n k =
    let binoms = unfoldr nextRow [1]
        nextRow row =
            let row' = 1 : zipWith (+) row (tail row) ++ [1]
            in Just (row', row')
    in binoms !! n !! k

-- Factorial version - uses definition of coefficients based
-- on division of factorials.
-- Worst-case linear in n

binom_f :: Int -> Int -> Integer
binom_f n k = product [nI,nI-1..(kh+1)] `div` product [2..kl]
    where
        nI = fromIntegral n
        kI = fromIntegral k
        nk = fromIntegral $ n - k
        kl = fromIntegral $ min k nk
        kh = fromIntegral $ max k nk