Sat 26 Apr 2008

## Time for Chronomorphisms

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

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:

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 . g_hylo' w m f g . return -- | the kernel of the generalized hylomorphism 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)) -> (m a -> w b) g_hylo' w m f g = liftW f . w . fmap (duplicate . g_hylo' w m f g . join) . m . liftM g

Also, the above made me realize that most of the generalized cata/ana, etc morphisms give you a little more interesting stuff to do if you separate out the recursive part. Then you can pass it a monad built with something other than return to perform substitution on, or inspect the comonadic wrapper on the result.

Oh, and to support my earlier claim that g_hylo generalizes g_cata and g_ana here are derivations of each in terms of g_hylo.

g_cata :: (Functor f, Comonad w) => (forall a. f (w a) -> w (f a)) -> (f (w a) -> a) -> Mu f -> a g_cata k f = g_hylo k (fmap Id . runId) f (fmap Id . outF) g_ana :: (Functor f, Monad m) => (forall a. m (f a) -> f (m a)) -> (a -> f (m a)) -> a -> Nu f g_ana k g = g_hylo (Id . fmap runId) k (InF . fmap runId) g

As an aside, histomorphisms have a dual that seems to be elided from most lists of recursion schemes: Uustalu and Vene call it a futumorphism. It basically lets you return a structure with seeds multiple levels deep rather than have to plumb 'one level at a time' through the anamorphism. While a histomorphism is a generalized catamorphism parameterized by the cofree comonad of your functor, a futumorphism is a generalized anamorphism parameterized by the free monad of your functor.

futu :: Functor f => (a -> f (Free f a)) -> a -> Nu f futu f = ana ((f ||| id) . runFree) . return

Now, g_hylo is painfully general, so lets look at a particularly interesting choice of comonad and monad for a given functor that always have a distributive law: the cofree comonad, and the free monad of that very same functor!

This gives rise to a particular form of morphism that I haven't seem talked about in literature, which after kicking a few names around on the haskell channel we chose to call a **chronomorphism** because it subsumes histo- and futu- morphisms.

chrono :: Functor f => (f (Cofree f b) -> b) -> (a -> f (Free f a)) -> a -> b

Unlike most of the types of these generalized recursion schemes, chrono's type is quite readable!

A chronomorphism's fold operation can 'look back' at the results it has given, and its unfold operation can 'jump forward' by returning seeds nested multiple levels deep. It relies on the fact that you always have a distributive law for the cofree comonad of your functor over the functor itself and also one for the functor over its free monad and so it works for any Functor.

You can generalize it like you generalize histomorphisms and futumorphisms, and derive ana and catamorphisms from it by noting the fact that you can fmap extract or fmap return to deal with the cofree comonad or free monad parts of the term.

Alternately, since the 'identity comonad' can be viewed as the cofree comonad of the Functor that maps everything to , you can also choose to rederive generalized futumorphisms from generalized chronomorphism using the distributive law of the identity comonad.

Below you'll find source code for generalized hylo- cata- ana- histo- futu- chrono- etc... morphisms and their separated kernels.

As an aside, Dan Doel (dolio) has started packaging these up for addition to category-extras in Hackage.

April 26th, 2008 at 7:43 pm

[...] Not quite. Unfortunately the same trick doesn’t work for the generalized chronomorphism defined last night. [...]

April 26th, 2008 at 8:54 pm

[...] 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. [...]

June 5th, 2016 at 7:10 pm

Did the chronomorphism ever get on hackage? I don’t really need the whole thing, but I am needing a dynamorphism, and understanding the chronomorphism by experimentation would be nice.

September 23rd, 2022 at 5:28 am

Viagra levitra https://500px.com/p/skulogovid/?view=groups...Kudos! I like this!…

September 23rd, 2022 at 9:28 am

Buy viagra online https://500px.com/p/bersavahi/?view=groups...Really a lot of beneficial data….

September 26th, 2022 at 10:18 am

Canadian Pharmacies Shipping to USA https://melaninterest.com/user/canadian-pharmaceuticals-online/?view=likes...Excellent information. Thanks a lot….

September 26th, 2022 at 2:18 pm

Viagra kaufen https://haikudeck.com/canadian-pharmaceuticals-online-personal-presentation-827506e003...You mentioned it superbly!…

September 26th, 2022 at 6:26 pm

Generic for viagra https://buyersguide.americanbar.org/profile/420642/0...You expressed it very well!…

September 27th, 2022 at 2:07 am

Canadian Pharmacy USA https://experiment.com/users/canadianpharmacy...Wonderful content. With thanks….

September 27th, 2022 at 8:05 am

Canadian viagra https://slides.com/canadianpharmaceuticalsonline...Whoa many of superb tips!…

September 27th, 2022 at 11:46 am

Viagra vs viagra https://challonge.com/esapenti...Awesome information. Cheers….

September 28th, 2022 at 5:54 am

Viagra uk https://challonge.com/citlitigolf...Many thanks! Numerous advice!

…

September 28th, 2022 at 9:27 am

stromectol lice https://order-stromectol-over-the-counter.estranky.cz/clanky/order-stromectol-over-the-counter.html...Seriously loads of terrific information….

September 28th, 2022 at 3:54 pm

Viagra 5mg https://soncheebarxu.estranky.cz/clanky/stromectol-for-head-lice.html...You actually explained it wonderfully….

September 29th, 2022 at 5:24 am

Viagra cost https://lehyriwor.estranky.sk/clanky/stromectol-cream.html...Kudos, I like it!…

September 29th, 2022 at 3:40 pm

Viagra vs viagra https://inflavnena.zombeek.cz/...You made the point!…

September 30th, 2022 at 9:54 am

online pharmacies https://www.myscrsdirectory.com/profile/421708/0...Seriously tons of valuable info!…

September 30th, 2022 at 5:08 pm

Viagra 5 mg funziona https://supplier.ihrsa.org/profile/421717/0...Terrific data. Cheers….

October 1st, 2022 at 7:28 am

canadian pharmacies online prescriptions https://wefbuyersguide.wef.org/profile/421914/0...Kudos, I appreciate this….

October 1st, 2022 at 11:31 am

canada pharmacies https://legalmarketplace.alanet.org/profile/421920/0...Reliable info. With thanks!…

October 2nd, 2022 at 5:06 am

Viagra coupon https://moaamein.nacda.com/profile/422018/0...Thank you, I appreciate it!…

October 2nd, 2022 at 9:31 am

Viagra purchasing https://www.audiologysolutionsnetwork.org/profile/422019/0...You’ve made your point….

October 2nd, 2022 at 12:49 pm

Viagra online https://network.myscrs.org/profile/422020/0...Appreciate it, Numerous advice!

…

October 3rd, 2022 at 6:34 am

Interactions for viagra https://sanangelolive.com/members/canadianpharmaceuticalsonlineusa...Good forum posts. Many thanks….

October 3rd, 2022 at 10:02 am

Viagra vs viagra vs levitra https://sanangelolive.com/members/girsagerea...Whoa a good deal of useful facts!…

October 4th, 2022 at 8:52 am

Viagra generico https://www.ecosia.org/search?q=“My Canadian Pharmacy – Extensive Assortment of Medications – 2022″…Information well used!!…

October 4th, 2022 at 1:01 pm

Viagra bula https://www.mojomarketplace.com/user/Canadianpharmaceuticalsonline-EkugcJDMYH...Seriously plenty of very good material….

October 4th, 2022 at 5:02 pm

Cheap viagra https://seedandspark.com/user/canadian-pharmaceuticals-online...Regards, A good amount of write ups!

…

October 5th, 2022 at 10:04 am

Buy generic viagra https://www.giantbomb.com/profile/canadapharmacy/blog/canadian-pharmaceuticals-online/265652/...You made your stand very nicely!!…

October 5th, 2022 at 1:56 pm

Viagra for sale https://feeds.feedburner.com/bing/Canadian-pharmaceuticals-online...Amazing lots of awesome tips!…

October 5th, 2022 at 6:40 pm

How does viagra work https://search.gmx.com/web/result?q=“My Canadian Pharmacy – Extensive Assortment of Medications – 2022″…Awesome facts. Cheers!…

October 6th, 2022 at 3:45 am

Viagra generique https://search.seznam.cz/?q=“My Canadian Pharmacy – Extensive Assortment of Medications – 2022″…You’ve made the point….

October 6th, 2022 at 7:27 am

Viagra pills https://sanangelolive.com/members/unsafiri...Cheers. I enjoy it!…

October 6th, 2022 at 11:42 am

Interactions for viagra …Thanks! Great information….

October 6th, 2022 at 5:38 pm

legitimate canadian mail order pharmacies https://swisscows.com/en/web?query=“My Canadian Pharmacy – Extensive Assortment of Medications – 2022″…Good information. Thank you….

October 7th, 2022 at 5:09 am

canadian pharmacy viagra https://www.dogpile.com/serp?q=“My Canadian Pharmacy – Extensive Assortment of Medications – 2022″…Many thanks! Excellent stuff….

October 7th, 2022 at 12:19 pm

most reliable canadian pharmacies …Really lots of helpful info!…

October 8th, 2022 at 1:41 pm

Viagra canada https://www.bakespace.com/members/profile/Сanadian pharmaceuticals for usa sales/1541108/…Wonderful postings. Kudos….

October 9th, 2022 at 4:29 pm

canadian rx https://www.infospace.com/serp?q=“My Canadian Pharmacy – Extensive Assortment of Medications – 2022″…Thanks a lot! I like it!…

October 10th, 2022 at 8:44 am

Viagra for sale https://headwayapp.co/canadianppharmacy-changelog...Thank you, I value it….

October 11th, 2022 at 6:45 am

Viagra generico https://results.excite.com/serp?q=“My Canadian Pharmacy – Extensive Assortment of Medications – 2022″…You actually reported that exceptionally well….

October 14th, 2022 at 6:25 am

ivermectin dosage https://reallygoodemails.com/orderstromectoloverthecounterusa...Amazing stuff. Thanks….