The Catalan numbers satisfy the recurrence
Of course Catalan numbers have a closed form expression involving binomial coefficients. Also we can express C_n in terms of C_{n-1} alone. What I am wondering is how one can implement this kind of convolution in functional languages like SML or Haskell.
Of course you can implement the catalan numbers in haskell (and I think as well the ml-family is powerful enough)!
But I guess this is not the answer you were looking for. So I hope you are familiar with the basic haskell syntax think of the catalan numbers as functions catalan :: Int -> Int
any series of natural numbers is such a function (well for small indices). But as catalan numbers grow quite fast I will choose for the codomain of our function the type of Integer
s(= arbitrary big integral numbers).
catalan :: Int -> Integer
catalan 0 = 1
catalan n = sum [ ?catalan magic? | i <- [1..n]]
I know I almost solved the problem but there is still the catalan magic ;-) you have to do on your own.
But before I stop a few caveats