Lazy Catalan Numbers in Haskell

Question

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 n^th, I know, but I'd rather avoid it.

Answer 1

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

C₀ = 1 and C_n+1=(4n+2)×C_n/(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]