Andrew J Bromage ajb@spamcop.net
Fri, 22 Aug 2003 16:00:45 +1000

```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

```