-- Pascal triangle row
pascal :: Integer -> [Integer]
pascal 1 = [1]
pascal n = addList (shiftLeft (pascal (n-1)))
                   (shiftRight (pascal (n-1)))
  where
    shiftLeft [] = [0]
    shiftLeft (h:t) = h:shiftLeft t
    shiftRight l = 0:l
    addList [] [] = []
    addList (h1:t1) (h2:t2) = (h1+h2):addList t1 t2

{--To test it:

pascal 5
pascal 24

--}

-- Polynomial-time Pascal triangle row
fastPascal :: Integer -> [Integer]
fastPascal 1 = [1]
fastPascal n = addList (shiftLeft l)
                       (shiftRight l)
  where
    l = fastPascal (n-1)
    shiftLeft [] = [0]
    shiftLeft (h:t) = h:shiftLeft t
    shiftRight l = 0:l
    addList [] [] = []
    addList (h1:t1) (h2:t2) = (h1+h2):addList t1 t2

{-- To test it:

fastPascal 5
fastPascal 24
fastPascal 86

--}

iterate' s isDone transform =
  if isDone s then s
  else let s1 = transform s in
           iterate' s1 isDone transform

ipascal n = iterate' [1] goodEnough improve
  where goodEnough = \r -> (length r) == n
        improve = \r -> addList (shiftLeft r)
                                (shiftRight r)
        shiftLeft [] = [0]
        shiftLeft (h:t) = h:shiftLeft t
        shiftRight l = 0:l
        addList [] [] = []
        addList (h1:t1) (h2:t2) = (h1+h2):addList t1 t2
        

{-- Test it with:
ipascal 5
--}