[Haskell-cafe] Re: Looking for practical examples of Zippers
cristiano.paris at gmail.com
Tue Mar 31 16:24:23 EDT 2009
On Tue, Mar 31, 2009 at 10:13 PM, Dan Weston <westondan at imageworks.com> wrote:
>> What I've learned: Zippers are "structured collections 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).
More information about the Haskell-Cafe