Zipper comonad

Here’s something cool I realized while thinking about Haskell lenses (getters and setters) being coalgebras of the costate comonad. Another example of a comonad is the zipper.

data Zipper a = Zipper [a] a [a]

(List) zippers are a way of looking at lists with a focus at a particular element. It should be obvious that we might want to get or set that focus, so that zippers come naturally adorned with lenses.

get :: Zipper a -> a
set :: Zipper a -> a -> Zipper a
lens :: Zipper a -> (a , a -> Zipper a)
get Zipper ls x rs = x
set (Zipper ls x rs) y = Zipper ls y rs
lens z = (get z , set z)

The other natural operations on zippers is list traversal. The zipper had three parts, the part of list to the left, the focus, and the part of the list to the right. (Clowns to the left of me, jokers to the right.) The left part is assumed to be in reverse order, so that its head is next to the focus.

toList :: Zipper a -> [a]
goLeft :: Zipper a -> Zipper a
goRight :: Zipper a -> Zipper a
toList Zipper ls x rs = (reverse ls) ++ (x:rs)
goLeft Zipper ls x rs = Zipper (tail ls) (head ls) (x:rs)
goRight Zipper ls x rs = Zipper (x:ls) (head rs) (tail rs)

So, how are zippers an example of a comonad? Define extract (coreturn) and duplicate (cojoin) like so.

extract :: Zipper a -> a
duplicate :: Zipper a -> Zipper Zipper a
extract = get
duplicate z = Zipper (tail $ iterate goLeft z) z (tail $ iterate goRight z)

What is duplicate of a zipper? Its focus is the zipper itself, but its other parts are all the other possible zippers for the underlying list, with their foci shifted according to their distance from the focus zipper. Maybe a better word for “duplicate” would be “diagonal”, since you can visualize it by putting copies of the list next to each other, then drawing a diagonal line through their foci. Indeed, this is closely related to various morphisms in topology and algebra that all go by the name “diagonal map”.

Nota bene: Zippers only really make sense for infinite lists, because in a finite list you can’t go left or right indefinitely, so for finite lists you have to work around with Maybes or special cases. I’m sure this has something to do with the distinction between data and codata. Finite lists are data and form a monad (the familiar one) while infinite lists (streams) are codata and form a comonad.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: