import Data.Vector (Vector, (!))
import Data.Vector qualified as V

import qualified Data.Map
main :: IO ()
main = do
    print $ fibv 10 -- first 10 fibonacci numbers
    print $ fibv 100 ! 99 --100th fibonacci number
    print $ catv 10 -- first 10 catalan numbers
    print $ catv 50 ! 49 -- 50th catalan number
    let pas = pascalv 40 40
    print $ pas ! 5 ! 5 -- 10 choose 5
    print $ pas ! 39 ! 39 -- 78 choose 39

-- fibonacci numbers
fibv :: Int -> Vector Integer
fibv m = v where
    v = V.fromList fibgen
    fibgen = [if n < 2 
                then 1 
                else v ! (n-1) + v ! (n-2)
              | n <- [0..m-1]]

-- catalan numbers http://wikipedia.org/wiki/Catalan_number
catv :: Int -> Vector Integer
catv m = v where
    v = V.fromList catgen
    catgen = [if n == 0 
                then 1 
                else sum [v!a * v!b | a <- [0..n-1], let b = n-1-a] 
              | n <- [0..m-1]]
          
-- pascal's triangle. An example of "2D" DP
pascalv :: Int -> Int -> Vector (Vector Integer)
pascalv m n = v where
    v = V.fromList . map V.fromList $ pascalgen
    pascalgen = [[ if x == 0 || y == 0
                    then 1
                    else v!(x-1)!y + v!x!(y-1)
                  | y <- [0..n-1]]
                  | x <- [0..m-1]]