Skip to content

Instantly share code, notes, and snippets.

@oisdk oisdk/catalan.hs
Created Jan 28, 2020

Embed
What would you like to do?
{-# 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.