haskellrecursionnumberslazy-evaluationcatalan

Lazy Catalan Numbers in Haskell


How might I go about efficiently generating an infinite list of Catalan numbers? What I have now works reasonably quickly, but it seems to me that there should be a better way.

c 1 = 1
c n = sum (zipWith (*) xs (reverse xs)) : xs
    where xs = c (n-1)

catalan = map (head . c) [1..]

I made an attempt at using fix instead, but the lambda isn't lazy enough for the computation to terminate:

catalan = fix (\xs -> xs ++ [zipWith (*) xs (reverse xs)])

I realize (++) isn't ideal

Does such a better way exist? Can that function be made sufficiently lazy? There's an explicit formula for the nth, I know, but I'd rather avoid it.


Solution

  • The Catalan numbers [wiki] can be defined inductively with:

    C0 = 1 and Cn+1=(4n+2)×Cn/(n+2).

    So we can implement this as:

    catalan :: Integral i => [i]
    catalan = xs
        where xs = 1 : zipWith f [0..] xs
              f n cn = div ((4*n+2) * cn) (n+2)

    For example:

    Prelude> take 10 catalan
    [1,1,2,5,14,42,132,429,1430,4862]