Skip to content

Instantly share code, notes, and snippets.

@robrix
Created April 2, 2022 20:05
Show Gist options
  • Save robrix/c4d470b165230c0c7491e54bcf473ff4 to your computer and use it in GitHub Desktop.
Save robrix/c4d470b165230c0c7491e54bcf473ff4 to your computer and use it in GitHub Desktop.
Monadic cata, ana, and hylo
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment