Re: Pascal Line in Haskell

22 Aug 2003

      G'day all.

On Fri, Aug 22, 2003 at 09:40:12AM +1000, Job L. Napitupulu wrote:
...
Can anyone help me how to make a function which takes an integer n > 0 and
returns the list of integers in Line of Pascal's Triangle. For examples,
pascalLine 4 -> [1,4,6,4,1]
pascalLine 7 -> [1,7,21,35,35,21,7,1]
This should do the trick.

Cheers,
Andrew Bromage

--------8<---CUT HERE---8<--------

type InfTable a = [(Integer, BinTree a)]
data BinTree a = Leaf a | Node Integer (BinTree a) (BinTree a)

swing :: Integer -> Integer
swing n = rec n (\_ _ r -> r)
  where
     rec :: Integer -> (Integer -> Integer -> Integer -> Integer) -> Integer
     rec n k
       | n < 2
         = k 1 1 1
       | otherwise
         = rec (n `div` 2) (\nn ff r -> swing' n nn ff
                     (\nn' ff' -> k nn' ff' $! (r*r*ff')))

     swing' :: Integer -> Integer -> Integer ->
             (Integer -> Integer -> Integer) -> Integer
     swing' n nn ff k
       | nn `mod` 2 == 1 = swing_odd k nn ff
       | otherwise       = swing_even k nn ff
         where
             swing_odd k nn ff
               | nn <= n   = swing_even k (nn+1) $! (ff*nn)
               | otherwise = k nn ff

             swing_even k nn ff
               | nn <= n   = swing_odd k (nn+1) $! (ff*4 `div` nn)
               | otherwise = k nn ff

recProd :: Integer -> Integer -> Integer
recProd b n
  | n < 5
    = case n of
         0 -> 1
         1 -> b
         2 -> b*(b+1)
         3 -> b*(b+1)*(b+2)
         4 -> (b*(b+1))*((b+2)*(b+3))
  | otherwise
    = let n2 = n `div` 2
      in recProd b n2 * recProd (b+n2) (n-n2)

pascalLine :: Integer -> [Integer]
pascalLine n
  | n >= 0 = searchTable n table
  where
     table :: InfTable [Integer]
     table = buildInfTable 1 5

     buildInfTable n i
        = (nextn, buildInfTable' n i) : buildInfTable nextn (i+1)
         where
             nextn = n + 2^i

             buildInfTable' base 0
                 = Leaf [ c base k | k <- [0..base] ]
                 where
                     c m n
                        | m < 0          = 0
                        | n < 0 || n > m = 0
                        | n > m `div` 2  = c' n (m-n)
                        | otherwise      = c' (m-n) n
                     c' i j = recProd (i+1) j `div` swing j
             buildInfTable' base i
                 = Node (base + midSize)
                        (buildInfTable' base (i-1))
                        (buildInfTable' (base + midSize) (i-1))
                 where
                     midSize = 2 ^ (i-1)

     searchTable x ((x',tree):ms)
         | x < x'    = searchTree x tree
         | otherwise = searchTable x ms

     searchTree x (Leaf y) = y
     searchTree x (Node mid l r)
         | x < mid   = searchTree x l
         | otherwise = searchTree x r

Re: Pascal Line in Haskell

Andrew J Bromage