[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.
More information about the Haskell-Cafe