Zipper, the functional cursor into a data structure, is itself
a data structure, derived from the original one. The derived data type
D' for the recursive data type D is D with exactly one hole.
Filling-in the hole -- integrating over all
positions of the hole -- gives the data type D back. Zipper
is the derivative, pretty much in the calculus sense, of a
data type. The zipper-as-datatype view was the original presentation,
described by Huet (JFP, 1997) and Hinze and Jeuring (JFP 2001);
the data structure derivative was expounded by McBride.
We advocate a different view, emphasizing not the result of navigating through a data structure to a desired item and extracting it, but the process of navigation. Each data structure comes with a method to enumerate its components, representing the data structure as a stream of the nodes visited during the enumeration. To let the user focus on a item and submit an update, the enumeration process should yield control to the user once it reached an item. Co-routines provide exactly the right yielding mechanism. As Chung-chieh Shan aptly put it, ``zipper is a suspended walk.''
Whereas datatype-derivative zipper necessarily depends on the data
type (different data types have different derivatives), the
suspended-walk zipper is datatype-invariant. We only need a traversal
procedure that applies a given function to each item of the data
structure. The zipper is obtained by supplying the mapping function
that yields. Since the traversal procedure can generically handle
many data types (think of map), so can the zipper.
Our zipper type depends only on the interface of the traversal function.
The two views of zipper are dual: they both regard zipper as the context of a data structure traversal. That context can be rendered in the functional form (the suspension, the delimited continuation of a traversal) or in the defunctionalized form, as a data structure.
Ralf Hinze and Johan Jeuring: Weaving a Web
Journal of Functional Programming 11(6), pages 681 - 689, 2001. Technical report ICS Utrecht University, UU-CS-2001-33.
Data.Traversible
interface -- at the very least, providing something like mapM.
We demonstrate that zipper is the suspended traversal by deriving
zipper for Data.Map. The latter is the Haskell standard, abstract
data type for finite maps. The example is a bit contrived since
Data.Map has a very rich interface, with many ways to access and
update map's elements. On the other hand, Data.Map is the only non-trivial
instance of Traversable defined in the standard library. We refer
to Zipper1.lhs for a more interesting zipper, walking up and down
a lambda-calculus term. Zipping into nested maps (which is a model of
a file system) is described in ZipperFS below.
data Zipper t a = ZDone (t a)
| Z a (Maybe a -> Zipper t a)
make_zipper :: T.Traversable t => t a -> Zipper t a
make_zipper t = reset $ T.mapM f t >>= return . ZDone
where
f a = shift (\k -> return $ Z a (k . maybe a id))
The few lines above is all it takes to implement the zipper. The active
`pointer' Z a k contains the current, focused on, element of the map
and the function k to move forward. Evaluating k Nothing returns
the cursor to the next element; evaluating k v replaces the current
element with v and moves the cursor forward. The complete code below
defines the function tmod to interactively traverse the map,
displaying the elements one by one and offering to modify the current
element, or quit the traversal. Here is a sample interaction: Current element: 1
Enter Return, q or the replacement value:
Current element: 2
Enter Return, q or the replacement value:
Current element: 6
Enter Return, q or the replacement value:
42
Current element: 24
Enter Return, q or the replacement value:
q
Done:
fromList [(1,1),(2,2),(3,42),(4,24),(5,120),(6,720),(7,5040),(8,40320),(9,362880),(10,3628800)]
Indeed, the third element of the map has been replaced with 42.Zipper1.lhs [12K]
Introduction to generic zippers as delimited continuations
The code was originally posted as Zipper as a delimited continuation on the Haskell mailing list on Wed, 27 Apr 2005 16:17:04 -0700 (PDT)
The new version of the code demonstrates deriving zipper
from a different traversal function, with a more intuitive interface,
suggested by Ron de Bruijn. The zipper declaration and
the navigation functions remain the same: the delimited-control--based
zipper is generic indeed. The new version of the code
relies on the delimcc library of delimited control in Haskell.
Chung-chieh Shan: From walking to zipping, Part 3: Caught in a zipper
< http://conway.rutgers.edu/~ccshan/wiki/blog/posts/WalkZip3/ >
Our Data.Map zipper moves only forward. Chung-chieh Shan
has explained in detail how to turn any
one-directional zipper into bi-directional. Again generically.
Zipper in Scheme
An old derivation, using call/cc to implement delimited control to model suspension.
We can easily change our file server to support NFS or 9P or
other distributed file system protocol. We can traverse richer terms than
mere finite maps with string keys. In particular, we can use
lambda-terms as our file system: one could cd into a lambda-term in
bash.
The implementation of ZipperFS has no unsafe operations, no GHC let alone Unix threads, and no concurrency problems. Our threads cannot even do IO and cannot mutate any global state --- and the type system sees to it. We thus demonstrate how delimited continuations let us statically isolate effects even if the whole program eventually runs in the IO monad.
ZFS.hs [18K]
The commented source code of the interrupt handler, scheduling loop, and the shell.
The code has tested with GHC 6.4-6.10 on FreeBSD and Linux.
ZipperM.hs [8K]
Zipper over the nested Map with path accumulation and sharing preservation
LowLevelIO.hs [4K]
Low-level IO operations, specifically, select
(also used by the Iteratee library)
Joint work with Chung-chieh Shan.
Olivier Danvy has very kindly pointed out that continuations in operating systems delimited at process, job, etc. boundaries were first mentioned back in 1974 in the seminal work by Christopher Strachey and Christopher P. Wadsworth `Continuations: A mathematical semantics for handling full jumps.' Technical Monograph PRG-11, Programming Research Group, Oxford University Computing Laboratory, 1974. Reprinted in Higher-Order and Symbolic Computation, 2000, 13(1-2):135-152. Here is footnote 1 from their paper:
Poster presented at CONTEXT 2007, Roskilde U., Denmark, August 22, 2007.
< http://www.cs.rutgers.edu/~ccshan/zipper/poster.ps >
delimcc library.oleg-at-okmij.org
Your comments, problem reports, questions are very welcome!
Converted from HSXML by HSXML->HTML