catalan.hs

{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE DeriveFoldable, DeriveTraversable, DeriveFunctor #-}

import Data.List (mapAccumL)

data Stream a = a :< Stream a deriving (Functor, Foldable, Traversable)
infixr 5 :<

instance Show a => Show (Stream a) where
  showsPrec n = showsPrec n . foldr (:) []

catalan :: Stream Integer
catalan = 1 :< snd (mapAccumL f const catalan)
  where
    f k x = (xs, xs 0 catalan)
      where
        xs !r (y :< ys) = k (r + x * y) ys