Показывая отношения между Hylo и HyloM

Question

Мне сказали, что следующие функции эквивалентны по силе

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

Однако, ради жизни я не могу понять, как это продемонстрировать.Установка Monad в Identity в hyloM становится почти правильным, но g Traversable not Functor, и я попробовал несколько подходов, чтобы перейти от hylo к hyloM безуспешно.

Являются ли ониизоморфный или хотя бы похожий по мощности?Если да, то как мне это доказать?

Answer 1

Вы можете определить hyloM, используя hylo, создав 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))

Я не уверен в обратном.