Wednesday, August 09, 2006

Sigfpe explains comonads

I just discovered this very cool discussion of comonads, which starts with a really lovely review of monads. The basic idea: monads allow you to compose two functions that inject their inputs into some "fancy structure." If we have functions f : a → m b and g : b → m c (i.e., Kleisli arrows), we can lift g to a function m b → m (m c) by the law that m is a functor, and then use the "flattening" monad law to unwrap the extra layer of structure on the result. As sigfpe (what is his/her real name?) puts it: "twice as fancy is still just fancy." I like that this provides an intuition for monads using the map/flatten formulation, as opposed to the usual unit/bind formulation, while still preserving the notion of "plumbing."

As for comonads, I'm starting to see the duality: comonads allow us to take some things already inside some fancy structure and map them down to something outside of that structure. For functions (co-Kleisli arrows) f : m a → b and g : m b → c, we can map f to a function m (m a) → m b, compose this with g on one end and the comonad operation m a → m (m a) on the other to get a function m a → c.

I'm still working on understanding some of the applications.

4 comments:

Anonymous said...

sigpfe -> dan piponi (http://homepage.mac.com/sigfpe/)

sigfpe said...

Combine this and this and we should have a nice way of looking at expressions through comonads.

David Van Horn said...

One application of comonads is optimal evaluation. If you look at the rules for boxes (which just mark structure that can be shared) you'll see that it forms a comonad.

David Van Horn said...

Another application is zippers. A nice discussion is found here:

http://cs.ioc.ee/~tarmo/tsem05/uustalu0812-slides.pdf

(I realize what I wrote about optimal evaluation makes no sense, but I can explain it in five minutes and you don't need to know anything about optimal evaluation to get it.)