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

Heinrich Apfelmus apfelmus at quantentunnel.de
Tue Mar 31 22:10:06 EDT 2009


Cristiano Paris wrote:
> On Tue, Mar 31, 2009 at 10:13 PM, Dan Weston <westondan at imageworks.com> wrote:
>>> 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.
> 
> That's true. But, correct me if I'm wrong, updates on the focus site are O(1).

Yes. It's just that shifting the focus to the site from scratch does not
 take constant time, obviously.


Regards,
apfelmus

--
http://apfelmus.nfshost.com



More information about the Haskell-Cafe mailing list