[Haskell-cafe] Zipper and Comonad
Mathijs Kwik
mathijs at bluescreen303.nl
Tue May 22 08:42:46 CEST 2012
Hi all,
After using zippers for a while, I wanted to dig a bit deeper into them.
I found there is some relation between Zipper and Comonad, but this
confuses me somewhat.
After reading a bit more about Comonads [1] and [2], I think I
understand them somewhat, and I see how they too are useful for
navigating a data structures and giving functions the ability to "look
around".
What confuses me though, is the relation between these 2.
This source [3] mentions all zippers can be made instances of Comonad,
and demonstrates how to do this for simple, 1-dimensional (list)
zippers.
But a comment on [4] says a Zipper by itself is already an application
of Comonad.
I want to find out which is the case. Looking at the types does not
yield me a solution yet.
This is Zipper from LYAH:
data Tree a = Empty | Node a (Tree a) (Tree a)
data Crumb a = LeftCrumb a (Tree a) | RightCrumb a (Tree a)
type Breadcrumbs a = [Crumb a]
type Zipper a = (Tree a, Breadcrumbs a)
This is Comonad from the comonad package (flattened to 1 class):
class Functor w => Comonad w where
duplicate :: w a -> w (w a)
extend :: (w a -> b) -> w a -> w b
extract :: w a -> a
Now, if [3] is correct, I can write "instance Comonad Zipper".
If I understood all this correctly, "extend" becomes "(Zipper a -> b)
-> Zipper a -> Zipper b".
This gives me something like a "look-around fmap" which sounds useful.
If the comment on [4] is correct though, Zipper somehow has a Comonad
"built-in", (probably hidden the interaction between Tree and
[Crumb]).
So in that case, a Zipper would be a (somewhat customized) "instance
Comonad Tree" with some extensions.
"(Tree a -> b) -> Tree a -> Tree b" seems reasonable. It will build up
a new tree with the same shape as the input tree, and allows the
mapping function to examine every node _and_ its child nodes. It does
not allow "looking up" though.
So what do I make of this?
It's clear that every Zipper can be a Comonad, and it's probably
useful in some cases, but on the other hand, a Zipper already gives
the ability to look around and modify (a -> a) things, so the
comonadic instance only allows you to do this in a somewhat
structure-preserving way.
It's still not clear to me whether there is some truth in "a Zipper
itself is an application of Comonad". What I looked at above is just a
Tree instance, which obviously lost power compared to a full Zipper.
But I somehow feel there indeed is a somewhat deeper relation between
these 2 compared to just "can be made instance of".
Please share your thoughts.
Thanks,
Mathijs
[1] http://blog.sigfpe.com/2006/12/evaluating-cellular-automata-is.html
[2] http://blog.sigfpe.com/2008/03/comonadic-arrays.html
[3] http://blog.sigfpe.com/2007/01/monads-hidden-behind-every-zipper.html
[4] http://gelisam.blogspot.com/2007/04/i-understand-comonads.html
More information about the Haskell-Cafe
mailing list