[Haskell-cafe] Re: Looking for practical examples of Zippers

wren ng thornton wren at freegeek.org
Tue Mar 31 23:44:12 EDT 2009

Gü?nther Schmidt wrote:
> Thanks Don,
> I followed some examples but have not yet seen anything that would show 
> me how, for instance, turn a nested Map like
> Map Int (Map Int (Map String Double)
> into a "zipped" version.

You can't. Or rather, you can't unless you have access to the 
implementation of the datastructure itself; and Data.Map doesn't provide 
enough details to do it.

One of the problems with trying to make a zipper for Data.Map is that it 
maintains a number of invariants on structure which would be tricky to 
fix up if someone changes things at the focused point. (Not impossible, 
but certainly tricky.)

Another tricky thing for this particular example is answering the 
question of what you want to call the "focus". Usually zippered 
datastructures are functors, so given F X we can pick one X to be the 
focus and then unzip the F around it. You can treat Map X Y as a functor 
(Map X) applied to Y. Here we'd get a zipper of (Map X) with amortized 
access time to the other Ys at neighboring Xs, which is nice but maybe 
not worth the overhead since we already have O(log n) access from the root.

But (Map X) Y misses half the point of Map: we can't change the Xs. We'd 
prefer something like Map as a functor on (X,Y), but if we took (X,Y) as 
the focus, then what should happen if someone changes the X? Changing X 
changes our position in the unzipped Map X Y, so we'd have to do some 
tricky things in order to refocus and maintain the balancing invariants 
of Map. Which is to say that Map isn't really a functor on (X,Y) so we 
can't rely on the structural properties of functors like we're used to 
when making zippers.

Live well,

More information about the Haskell-Cafe mailing list