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

[Dan Weston]

 > What I've learned: Zippers are "structured collections[1] with a
 > focus". Through a Zipper you can O(1) change the value of the focused
 > element: that's the fundamental property. In addition, you can change
 > the focus through a series of "moving" functions.

To clarify: there is no magic that turns a data structure into O(1) 
access, just as a CPS transformation is not a magic bullet for speeding 
up programs. Only the move functions (changing focus to some subset of 
"adjacent" substructures) are O(1). Update functions need not be O(1). 
And amortized random access time via a zipper is never less than 
amortized random access of the optimal equivalent un-zippered data 
structure.

Zippers are most effective when a structure is accessed by some 
quasicontinuous path through it. Fortunately, this happens quite a lot, 
although laziness does obviate the need for a zipper in many of these cases.

Dan

Cristiano Paris wrote:
> On Mon, Mar 30, 2009 at 9:46 PM, Gü?nther Schmidt <gue.schmidt at web.de> 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.
>>
>> That is presuming of course that this use is feasible at all.
> 
> Hi Günther,
> 
> a couple of weeks ago I was looking into Zippers my self as well.
> After reading all the documents mentioned in the other messages, I
> decided to go for my implementation as the proposed ones seemed to me
> unnecessarily complicated. You can see the discussion here:
> 
> http://www.haskell.org/pipermail/haskell-cafe/2009-March/056942.html
> 
> I have to thank Heinrich Apfelmus and Ryan Ingram because they pointed
> out a major flaw in my implementation and so I got Zippers and why
> they are implemented as such.
> 
> What I've learned: Zippers are "structured collections[1] with a
> focus". Through a Zipper you can O(1) change the value of the focused
> element: that's the fundamental property. In addition, you can change
> the focus through a series of "moving" functions. Regarding their
> implementation, it's important to understand that the moving functions
> must be "aware" of the changes you made to the focused element. This
> is carried out by having the moving functions rebuild the context of
> the new focused element starting from the current focus' context.
> 
> On the contrary, my implementation relied on laziness and partial
> application but lacked the "awareness" of the changes. If you can
> catch this difference, it's easy to grasp the Zipper/Delimited
> Continuation link and the statement "a zipper is a delimited
> continuation reified to data".
> 
> Sorry for my explanation using elementary terms: I'm no computer
> science theorist ;)
> 
> Hope this helped.
> 
> Cristiano
> 
> [1] By structured collection I mean lists, trees, graphs and so on.
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
> 
>