blog

The "obvious" way to write a monadic zygomorphism is to look at the definition for an ordinary zygomorphism, namely

zygo :: (Recursive t) => (Base t b -> b) -> (Base t (b, a) -> a) -> t -> a
zygo f g = snd . cata (\x -> (f (fmap fst x), g x))

and convert it like so

zygoM :: (Recursive t, Traversable (Base t), Monad m) => (Base t b -> m b) -> (Base t (b, a) -> m a) -> t -> m a
zygoM f g = fmap snd . cataM (\x -> (,) <$> f (fmap fst x) <*> g x)

But, as monads allow ordering effects, this is not always what we want. We may want f to be called after g. With that in mind, we get the second monadic zygomorphism:

zygoM' :: (Recursive t, Traversable (Base t), Monad m) => (Base t b -> m b) -> (Base t (b, a) -> m a) -> t -> m a
zygoM' f g = fmap snd . cataM (\x -> do { a <- g x; b <- f (fmap fst x); pure (b, a) })

Both are now available in my recursion package.