Zipper (data structure)

From Wikipedia, the free encyclopedia

 The introduction to this article provides insufficient context for those unfamiliar with the subject.
Please help improve the article with a good introductory style.
Wikibooks
Wikibooks' Haskell has more about this subject:

Zipper is a purely functional data structure used in functional programming to solve some problems in a way using notions like “context” and “hole”. It is related to the generalization of notion “derivative” (for types). The zipper was described by Gerard Huet in 1997.

Zippers are multidimensional in the sense that they can be used as lists or trees by placing additional restrictions upon them. Such derived data structures are usually referred to by saying a tree with zipper or a list with zipper to give the image that the structure is a tree or a list, with a zip slider attach to it as an after thought.

Contents

[edit] Minimal Example

While zipper is a functional structure and is often used from within a functional language equipped with extensive type checking, there is no reason why it would not be suitable for use with many procedural languages as well. Many procedural languages even support functional programming to some degree. A minimal list with zipper example is described below in Python. Python's duck typing makes the example readable without prior understanding about a proper type system. The example is only used to present the core idea and is not provided as a guide for actually implementing a zipper.

cursor = [ [0,1,2], 3, [4,5,6,7,8,9] ]

The structure is named cursor because its value is a list with focus set on value 3. Technically it is (at top level) a list with exactly three values([0,1,2], 3 and [4,5,6,7,8,9]). This list starts with a list of elements ([0,1,2]) that precede the element with current focus, then as the second element it contains the element with focus (3) and finally it contains another list ([4,5,6,7,8,9]) with the elements that follow the element with current focus.

[edit] An analogy, using only sets

The ideas of zero, addition, multiplication and exponentiation known from the area of arithmetic have analogies in set theory, category theory and type theory. For example, there follows a small list of set theoretical ones:

\empty
A \times B
  • the set of n-tuples of elements of the set A (analogous to n-power)
A^n\;\forall n\in\mathbb N
  • the set of functions from A to B (analogous to exponentiation)
B^A\, (sometimes written as A \to B or \mathrm{Hom}(A,B)\,)

Also

A + B\,

can be defined for sets as a fruitful concept (analogous to addition). It is something similar to the disjoint union of sets, but it uses labels to achieve a partition-like construct [1]. There are analogous constructs for types, too (see also typeful functional programming languages), used for case analysis.

[edit] Parametric constructs

Several programming languages have parametric type constructs. They are used in a natural way in functional programming and have firm theoretical foundations, see type theory.

If we continue using the set theoretical analogies: we have a notion of constructing from a set another set. In many specific cases, these can be grasped as polynomial constructs of sets, where multiplication, addition, power correspond to the appropriate set-theoretic operations.

F(X) = X3

“makes” an appropriate set of triples from the set given in the argument:

F\left(\left\lbrace\,0, 1, \dots, 9\,\right\rbrace\right) = \left\lbrace\,\left\langle0,0,0\right\rangle, \left\langle0,0,1\right\rangle, \dots, \left\langle9,9,9\right\rangle \,\right\rbrace

[edit] Derivative

Thus, we can write “polynomials” for sets. We know polynomials from many numerical branches of mathematics. A notion of "derivative" has sense in them:

f(x)=a_n x^n + a_{n-1} x^{n-1} + \cdots + a_1 x + a_0

becomes

f'(x)=n a_n x^{n-1} + (n-1) a_{n-1} x^{n-2} + \cdots + a_1

Let us define the derivative here as we define it for polynomials over a ring! In our triple-building example,

F(X) = X3

becomes

F'(X) = X2 + X2 + X2

and let us examine whether this step — that we have done in a mechanical way — has any sense for sets.

Maybe astonishingly, this mechanical application of a concept borrowed from a distant field of mathematics will yield a fruitful result: the resulting construct is a polynomial that builds from any set the corresponding set of triples “with a hole”. An informal explanation: if we store a pair, and at the same time make a distinction among three cases, then we have exactly the right amount of information to distinguish among cases

  • first thing, second thing, hole
  • first thing, hole, third thing
  • hole, second thing, third thing

thus we can interpret it as storing a triple with a hole.

In summary, such a notion is meaningful and even fruitful, and several analogous constructs are used in functional programming.

Supported by this achievement, we can examine whether mechanical use of some differentiation rules will produce a meaningful notion also for sets. We can build an analogous calculus with polynomials, for sets.

There are also more interesting constructs, than such polynomial ones. This notion of “derivative” can be extended also to them. This concept has practical applications (in functional programming).

[edit] Uses

The zipper is often used where there is some concept of 'focus' or of moving around in some set of data, since its semantics reflect that of moving around but in a functional non-destructive manner.

The zipper has been used in

  • Xmonad, to manage focus and placement of windows
  • Huet's papers cover a structural editor[2] based on zippers and a theorem prover
  • A filesystem (ZipperFS) written in Haskell offering "...transactional semantics; undo of any file and directory operation; snapshots; statically guaranteed the strongest, repeatable read, isolation mode for clients; pervasive copy-on-write for files and directories; built-in traversal facility; and just the right behavior for cyclic directory references."[1]

[edit] References

  1. ^ More precisely, it is a two-arguments case of the more general construct
    \sum_\Lambda \vec A = \left\{\left\langle\lambda, a\right\rangle \in \Lambda \times \bigcup\mathcal A \mid \lambda\in\Lambda \land a \in \vec A_\lambda\right\} where \vec A : \Lambda \to \mathcal A
  2. ^ "Functional Pearl: Weaving a web".

[edit] Further reading

[edit] External links