Sat 26 Apr 2008

## Dynamorphisms as Chronomorphisms

Posted by Edward Kmett under Category Theory , Comonads , Haskell[2] Comments

In case it wasn't obvious, I thought I should mention that Kabanov and Vene's dynamorphisms which optimize histomorphisms for dynamic programming can be expressed readily as chronomorphisms; they just use an anamorphism instead of a futumorphism.

-- | dynamorphism dyna :: Functor f => (f (Cofree f b) -> b) -> (a -> f a) -> (a -> b) dyna f g = extract . dyna' f g -- | dynamorphism kernel dyna' :: Functor f => (f (Cofree f b) -> b) -> (a -> f a) -> (a -> Cofree f b) --dyna' f g = hylo (Cofree . (f &&& id)) g dyna' f g = chrono' f (fmap return . g) . return -- | generalized dynamorphism g_dyna :: (Functor f, Functor h) => (forall b. f (h b) -> h (f b)) -> (f (Cofree h b) -> b) -> (a -> f a) -> (a -> b) g_dyna k f g = extract . g_dyna' k f g -- | generalized dynamorphism kernel g_dyna' :: (Functor f, Functor h) => (forall b. f (h b) -> h (f b)) -> (f (Cofree h b) -> b) -> (a -> f a) -> (a -> Cofree h b) g_dyna' k f g = g_chrono' k id f (fmap return . g) . return

Moreover, as an interesting aside, since one side is an anamorphism, there is no power to be gained for a dynamorphism by introducing a natural transformation term, even though dynamorphism is a form of chronomorphism, because 'eta' can be folded into the anamorphism side of the chronomorphism, as you do with a normal hylomorphism.

April 27th, 2008 at 3:09 am

Another notion of g_dyna could be to allow the composition of a generalized anamorphism with a histomorphism rather than the one above which has a generalized histomorphism with an anamorphism.

Allowing for them both together yields the near trivial declaration:

g_dyna k = g_hylo (distCofree k)

but at that point its not clear that its a whole lot more specific than g_hylo.

April 27th, 2008 at 4:58 am

Up too late and way too tired, I mis-read “Cofree” for “Coffee” at first glance :) . Hopefully some of the latter, in the morning, will help me digest the former.