Not What You Meant? There are 46 definitions for Zip.

Zipper (data structure)

About 3 pages (857 words)

Questions on this topic? Just ask!

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 has a book on the topic of

Haskell/Zippers

Zipper is a data structure used in programming (particularly 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.

1 An analogy, using only sets
- 1.1 Parametric constructs
- 1.2 Derivative
2 Uses
3 References
4 Further reading
5 External links

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:

The empty set (analogous to zero)

<math>\empty</math>

The cartesian product of the sets <math>A</math> and <math>B</math> (analogous to multiplication)

<math>A \times B</math>

the set of <math>n</math>-tuples of elements of the set <math>A</math> (analogous to n-power)

<math>A^n\;\forall n\in\mathbb N</math>

the set of functions from <math>A</math> to <math>B</math> (analogous to exponentiation)

<math>B^A\,</math> (sometimes written as <math>A \to B</math> or <math>\mathrm{Hom}(A,B)\,</math>)

Also

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.

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.

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

<math>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</math>

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:

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

becomes

<math>f^\prime(x)=n a_n x^{n-1} + (n-1) a_{n-1} x^{n-2} + \cdots + a_1</math>

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

becomes

<math>F^\prime(X) = X^2 + X^2 + X^2</math>

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).

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]

References

^ More precisely, it is a two-arguments case of the more general construct

<math>\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\}</math> where <math>\vec A : \Lambda \to \mathcal A</math>
^ "Functional Pearl: Weaving a web".