Search code examples
haskellrecursion-schemes

Exhibiting the relationship between hylo and hyloM

I'm told the following functions are equivalent in power

hylo :: Functor f => (f b -> b) -> (a -> f a) -> a -> b
hylo f g = h where h = f . fmap h . g

hyloM :: (Traversable g, Monad m) => (g b -> m b) -> (a -> m (g a)) -> a -> m b
hyloM f g = h where h = f <=< traverse h <=< g

For the life of me, though, I can't figure out how to demonstrate this. Setting Monad to Identity in hyloM gets pretty much the right thing, but g is Traversable not Functor, and I have tried a number of approaches to go from hylo to hyloM with no success.

Are these isomorphic, or at least similar in power? If so, how do I evidence that?

Solution

  • You can define hyloM using hylo by instantiating f = Compose m g. 

    hyloM' :: (Traversable g, Monad m) => (g b -> m b) -> (a -> m (g a)) -> a -> m b
hyloM' f g = hylo (\(Compose mg) -> mg >>= sequence >>= f) (\a -> Compose (g a))

    I'm not sure about the converse.