PascalsTriangle.hs

module PascalsTriangle (pascalsTriangle) where

import Control.Applicative
import Test.QuickCheck

pascalsTriangle :: [[Int]]
pascalsTriangle = [1] : map row pascalsTriangle
  where row prev = zipWith (+) (0 : prev) (prev ++ [0])

-- quickcheck stuff

data ChoosePair = ChoosePair Int Int deriving Show

instance Arbitrary ChoosePair where
  arbitrary = flip suchThat (\(ChoosePair x y) ->  y <= x) $
                (\[x, y] -> ChoosePair x y ) <$> (vectorOf 2 (choose (0, 50)))

checkPascalsTriangle (ChoosePair n k) = choose n k == pascalsTriangle !! n !! k
  where
    choose n 0 = 1
    choose 0 k = 0
    choose n k = choose (n-1) (k-1) * n `div` k