Thu 24 Apr 2008

## Generalized Hylomorphisms

Posted by Edward Kmett under Category Theory , Comonads , Haskell , Monads1 Comment

I haven't seen written up anywhere the following operator (g_hylo), defined in the spirit of generalized catamorphisms and generalized anamorphisms, which seems to follow rather naturally from the definition of both -- I'm using liftW & liftM rather than fmap to make it clear what is being lifted over what.

class Functor w => Comonad w where -- minimal definition: extend & extract or duplicate & extract duplicate :: w a -> w (w a) extend :: (w a -> b) -> w a -> w b extract :: w a -> a extend f = fmap f . duplicate duplicate = extend id liftW :: Comonad w => (a -> b) -> w a -> w b liftW f = extend (f . extract) g_hylo :: (Comonad w, Functor f, Monad m) => (forall a. f (w a) -> w (f a)) -> (forall a. m (f a) -> f (m a)) -> (f (w b) -> b) -> (a -> f (m a)) -> a -> b g_hylo w m f g = extract . hylo (liftW f . w . fmap duplicate) (fmap join . m . liftM g) . return where hylo f g = f . fmap (hylo f g) . g

In the above, w and m are the distributive laws for the comonad and monad respectively, and hylo is a standard hylomorphism. In the style of Dave Menendez's Control.Recursion code it would be a 'refoldWith' and it can rederive a whole lot of recursion and corecursion patterns if not all of them.

Anyone?

April 26th, 2008 at 2:43 am

[...] First, we can make the generalized hylomorphism from the other day more efficient by noting that once you inline the hylomorphism, you can see that you do 3 fmaps over the same structure, so we can fuse those together yielding: [...]