Monadic cata, ana, and hylo

MonadicFolds.hs

newtype Fix f = In { out :: f (Fix f) }

cata :: Functor f => (f a -> a) -> (Fix f -> a)
cata alg = go where go = alg . fmap go . out

ana :: Functor f => (a -> f a) -> (a -> Fix f)
ana coalg = go where go = In . fmap go . coalg


hylo1 :: Functor f => (f b -> b) -> (a -> f a) -> (a -> b)
hylo1 alg coalg = cata alg . ana coalg

hylo2 :: Functor f => (f b -> b) -> (a -> f a) -> (a -> b)
hylo2 alg coalg = go where go = alg . fmap go . coalg


cataM :: (Traversable f, Monad m) => (f a -> m a) -> (Fix f -> m a)
cataM algM = go where go = algM <=< traverse go . out

anaM :: (Traversable f, Monad m) => (a -> m (f a)) -> (a -> m (Fix f))
anaM coalgM = go where go = fmap In . traverse go <=< coalgM


hyloM1 :: (Traversable f, Monad m) => (f b -> m b) -> (a -> m (f a)) -> (a -> m b)
hyloM1 algM coalgM = cataM algM <=< anaM coalgM

hyloM2 :: (Traversable f, Monad m) => (f b -> m b) -> (a -> m (f a)) -> (a -> m b)
hyloM2 algM coalgM = go where go = algM <=< traverse go <=< coalgM