StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>A classic general-purpose solution to this problem is what's called a <a href="http://en.wikipedia.org/wiki/Zipper_(data_structure)" rel="noreferrer">"zipper" data structure</a>. There are a number of variations, but the basic idea is simple: Given a nested data structure, take it apart as you traverse it, so that at each step you have a "current" element and a list of fragments representing how to reconstruct the rest of the data structure "above" the current element. A zipper can perhaps be thought of as a "cursor" that can move through an immutable data structure, replacing pieces as it goes, recreating only the parts it has to.</p> <p>In the trivial case of a list, the fragments are just the previous elements of the list, stored in reverse order, and traversal is just moving the first element of one list to the other.</p> <p>In the nontrivial but still simple case of a binary tree, the fragments each consist of a value and a subtree, identified as either right or left. Moving the zipper "down-left" involves adding to the fragment list the current element's value and right child, making the left child the new current element. Moving "down-right" works similarly, and moving "up" is done by combining the current element with the first value and subtree on the fragment list.</p> <p>While the basic idea of the zipper is very general, constructing a zipper for a specific data structure usually requires some specialized bits, such as custom traversal or construction operations, to be used by a generic zipper implementation.</p> <p>The <a href="http://www.st.cs.uni-saarland.de/edu/seminare/2005/advanced-fp/docs/huet-zipper.pdf" rel="noreferrer">original paper describing zippers</a> (warning, PDF) gives example code in OCaml for an implementation storing fragments with an explicit path through a tree. Unsurprisingly, plenty of material can also be found on zippers in <a href="http://www.haskell.org/haskellwiki/Zipper" rel="noreferrer">Haskell</a>. As an alternative to constructing an explicit path and fragment list, zippers can be implemented <a href="http://okmij.org/ftp/Scheme/misc.html#zipper" rel="noreferrer">in Scheme using continuations</a>. And finally, there seems to even be a <a href="http://clojure.org/other_libraries#toc2" rel="noreferrer">tree-oriented zipper provided by Clojure</a>.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload