How well do zippers perform in practice, and when should they be used?

Posted by Rob on Stack Overflow See other posts from Stack Overflow or by Rob
Published on 2010-03-28T03:05:09Z Indexed on 2010/03/28 3:13 UTC
Read the original article Hit count: 386

Filed under:

functional-programming

|

zipper

|

Performance

|

memory-allocation

|

data-structures

I think that the zipper is a beautiful idea; it elegantly provides a way to walk a list or tree and make what appear to be local updates in a functional way.

Asymptotically, the costs appear to be reasonable. But traversing the data structure requires memory allocation at each iteration, where a normal list or tree traversal is just pointer chasing. This seems expensive (please correct me if I am wrong).

Are the costs prohibitive? And what under what circumstances would it be reasonable to use a zipper?

© Stack Overflow or respective owner

Related posts about functional-programming

Introducing functional programming constructs in non-functional programming languages

as seen on Programmers - Search for 'Programmers'
This question has been going through my mind quite a lot lately and since I haven't found a convincing answer to it I would like to know if other users of this site have thought about it as well. In the recent years, even though OOP is still the most popular programming paradigm, functional programming… >>> More
Functional programming constructs in non-functional programming languages

as seen on Programmers - Search for 'Programmers'
This question has been going through my mind quite a lot lately and since I haven't found a convincing answer to it I would like to know if other users of this site have thought about it as well. In the recent years, even though OOP is still the most popular programming paradigm, functional programming… >>> More
Does functional programming mandate new naming conventions?

as seen on Stack Overflow - Search for 'Stack Overflow'
I recently started studying functional programming using Haskell and came upon this article on the official Haskell wiki: How to read Haskell. The article claims that short variable names such as x, xs, and f are fitting for Haskell code, because of conciseness and abstraction. In essence, it claims… >>> More
pitfalls/disadvantages of functional programming

as seen on Stack Overflow - Search for 'Stack Overflow'
When would you NOT want to use functional programming? What is it not so good at? I am more looking for disadvantages of the paradigm as a whole, not things like "not widely used", or "no good debugger available". Those answers may be correct as of now, but they deal with FP being a new concept (an… >>> More
Should functional programming be taught before imperative programming?

as seen on Stack Overflow - Search for 'Stack Overflow'
It seems to me that functional programming is a great thing. It eliminates state and makes it much easier to automatically make code run in parallel. Many programmers who were first taught imperative programming styles find it very difficult to learn functional programming, because it is so different… >>> More

Related posts about zipper

Page Zipper Unpacks Multi-Page Articles for Single-Page Display

as seen on How to geek - Search for 'How to geek'
It’s annoying when you find an article worth reading but it’s diced up into little segments. Skip clicking next-next-next to read; use Page Zipper to unpack multi-page articles and read them all on one page. Page Zipper is available as both a bookmarklet and a Firefox extension. You… >>> More
LamedropXPd-like very simple zipper?

as seen on Super User - Search for 'Super User'
Hello A friend of mine needs to zip a bunch of MP3's on her locked-down XP or Vista PC at work. There are two requirements: Since she doesn't have admin rights, the application should either not require an installer, or the installer doesn't require admin rights (don't know if it's possible) Ideally… >>> More
Insertions into Zipper trees on XML files in Clojure

as seen on Stack Overflow - Search for 'Stack Overflow'
I'm confused as how to idiomatically change a xml tree accessed through clojure.contrib's zip-filter.xml. Should be trying to do this at all, or is there a better way? Say that I have some dummy xml file "itemdb.xml" like this: <itemlist> <item id="1"> <name>John</name> … >>> More
Idiomatic way to build a custom structure from XML zipper in Clojure

as seen on Stack Overflow - Search for 'Stack Overflow'
Say, I'm parsing an RSS feed and want to extract a subset of information from it. (def feed (-> "http://..." clojure.zip/xml-zip clojure.xml/parse)) I can get links and titles separately: (xml-> feed :channel :item :link text) (xml-> feed :channel :item :title text) However I can't… >>> More
How well do zippers perform in practice, and when should they be used?

as seen on Stack Overflow - Search for 'Stack Overflow'
I think that the zipper is a beautiful idea; it elegantly provides a way to walk a list or tree and make what appear to be local updates in a functional way. Asymptotically, the costs appear to be reasonable. But traversing the data structure requires memory allocation at each iteration, where a… >>> More