Zipper (data structure)

A zipper is a technique of representing an aggregate data structure so that it is convenient for writing programs that traverse the structure arbitrarily and update its contents, especially in purely functional programming languages. The zipper was described by Gérard Huet in 1997.[1] It includes and generalizes the gap buffer technique sometimes used with arrays.

The zipper technique is general in the sense that it can be adapted to lists, trees, and other recursively defined data structures. Such modified data structures are usually referred to as "a tree with zipper" or "a list with zipper" to emphasize that the structure is conceptually a tree or list, while the zipper is a detail of the implementation.

A layperson's explanation for a tree with zipper would be an ordinary computer filesystem with operations to go to parent (often cd ..), and the possibility to go downwards (cd subdirectory). The zipper is the pointer to the current path. Behind the scenes the zippers are efficient when making (functional) changes to a data structure, where a new, slightly changed, data structure is returned from an edit operation (instead of making a change in the current data structure).

Example: Bidirectional list traversal

Many common data structures in computer science can be expressed as the structure generated by a few primitive constructor operations or observer operations. These include the structure of finite lists, which can be generated by two operations:

• Empty constructs an empty list,
• Cons(x, L) constructs a list by prepending or concatenating value x in front of list L.

A list such as [1, 2, 3] is therefore the declaration Cons(1, Cons(2, Cons(3, Empty))). It is possible to describe the location in such a list as the number of steps from the front of the list to the target location. More formally, a location in the list is the number of Cons operations required to reconstruct the whole list from that particular location. For example, in Cons(1, Cons(2, Cons( X, Cons(4, Empty)))) a Cons(2, L) and a Cons(1, L) operation would be required to reconstruct the list relative to position X otherwise known as Cons( X, Cons(4, Empty)). This recording together with the location is called a zipped representation of the list or a list-zipper.

To be clear, a location in the list is not just the number of Cons operations, but also all of the other information about those Cons; in this case, the values that must be reconnected. Here, these values may be conveniently represented in a separate list in the order of application from the target location. Specifically, from the context of "3" in the list [1, 2, 3, 4], a recording (commonly referred to as a 'path') could be represented as [2, 1] where Cons(2, L) is applied followed by (Cons 1, L) to reconstitute the original list starting from [3, 4].

A list-zipper always represents the entire data structure. However, this information is from the perspective of a specific location within that data structure. Consequently, a list-zipper is a pair consisting of both the location as a context or starting point, and a recording or path that permits reconstruction from that starting location. In particular, the list-zipper of [1, 2, 3, 4] at the location of "3" may be represented as ([2, 1], [3, 4]). Now, if "3" is changed to "10", then the list-zipper becomes ([2, 1], [10, 4]). The list may then be efficiently reconstructed: [1, 2, 10, 4] or other locations traversed to.

With the list represented this way, it is easy to define relatively efficient operations on immutable data structures such as Lists and Trees at arbitrary locations. In particular, applying the zipper transform to a tree makes it easy to insert or remove values at any particular location in the tree.

Contexts and differentiation

The type of a zipper's contexts can be constructed via an operation on the original type that is closely related to the derivative of calculus through decategorification. The recursive types that zippers are formed from can be viewed as the least fixed point of a unary type constructor of kind ${\displaystyle *\rightarrow *}$. For example, with a higher-order type constructor ${\displaystyle {\text{lfp}}:(*\rightarrow *)\rightarrow *}$ that constructs the least fixed point of its argument, an unlabeled binary tree can be represented as ${\displaystyle {\text{lfp}}(T\mapsto T^{2}+1)}$ and an unlabeled list may take the form ${\displaystyle {\text{lfp}}(T\mapsto T+1)}$. Here, the notation of exponentiation, multiplication, and addition correspond to function types, product types, and sum types respectively, whilst the natural numbers label the finite types; in this way, the type constructors resemble polynomial functions.[2]

The derivative of a type constructor can therefore be formed through this syntactic analogy, and the zipper of the type constructor is the derivative paired with its element type. In this way, the derivative can be viewed as a zipper with a hole in it, where a value could be placed.

Consider the type of singly-linked lists. The list data structure can be defined as ${\displaystyle L(X)=1+X\times L(X)}$. That is, ${\displaystyle L}$ is a type constructor which takes an element type ${\displaystyle X}$ and produces the type of lists of that element type. The two addends correspond to the two data constructors for a list. The Nil data constructor, a sentinel node that holds no data, is represented by the unit type ${\displaystyle 1}$, and the Cons constructor is represented as a product of the head element ${\displaystyle X}$ and the tail ${\displaystyle L}$ of the list.

Under this representation, the derivative ${\displaystyle L'}$ of ${\displaystyle L}$ in terms of ${\displaystyle X}$ is ${\displaystyle L'(X)=L(X)+X\times L'(X)}$. That is, if we have a zipper-with-a-hole for a list, then either (I) the hole is the very first element, and the rest of the list is an ordinary (non-zipper) list ${\displaystyle L(X)}$, or (II) the first element is present (${\displaystyle X}$) and the hole is somewhere else further down the tail of the list (${\displaystyle L'(X)}$). Then the formal type of a zipper for a linked list is ${\displaystyle X\times L'(X)}$, or ${\displaystyle X\times (L(X)+X\times L'(X))}$. Put another way, a zipper for a linked list consists of an element in that list and instructions on where to put it in a partially-built list.

For another example, consider the recursive data structure of a binary tree with nodes that are either sentinel nodes of type ${\displaystyle 1}$ or which are leaves containing a value of some type ${\displaystyle X}$. We can represent this type algebraically as ${\displaystyle T(X)=1+X\times T^{2}(X)}$. The derivative in terms of ${\displaystyle X}$ is ${\displaystyle T'(X)=T^{2}(X)+2\times X\times T(X)\times T'(X)}$. We can read this algebraic notation as a zipper with a hole: A zipper for a tree either has the "missing value" at the very root of the tree, leaving the two branches as ordinary trees (the ${\displaystyle T^{2}(X)}$ case), or it has the missing value on one of the two branches (${\displaystyle 2\times X\times T(X)\times T'(X)}$). In the latter case, the Boolean type ${\displaystyle 2}$ indicates which branch (left or right) contains the hole, and the zipper contains a value for the root, a ${\displaystyle T(X)}$ for the complete branch, and a ${\displaystyle T'(X)}$ for the branch that's missing a value of type ${\displaystyle X}$. The complete type of a zipper for this binary tree structure, then, is ${\displaystyle X\times T'(X)}$, or ${\displaystyle X\times (T^{2}(X)+2\times X\times T(X)\times T'(X))}$.

In general, a zipper consists of two parts: a collection of contexts for the current node and each of its ancestors up until the root node, and the value that the current node contains.

Uses

The zipper is often used where there is some concept of focus or a cursor used to navigate 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[3] 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."[4]
• Clojure has extensive support for zippers.[5]

Alternatives and extensions

Direct modification

In a non-purely-functional programming language, it may be more convenient to simply traverse the original data structure and modify it in place (perhaps after deep cloning it, to avoid affecting other code that might hold a reference to it).

Generic zipper

The generic zipper[6][7][8] is a technique to achieve the same goal as the conventional zipper by capturing the state of the traversal in a continuation while visiting each node. (The Haskell code given in the reference uses generic programming to generate a traversal function for any data structure, but this is optional – any suitable traversal function can be used.)

However, the generic zipper involves inversion of control, so some uses of it require a state machine (or equivalent) to keep track of what to do next.

References

1. Huet 1997
2. Joyal, André (October 1981). "Une théorie combinatoire des séries formelles". Advances in Mathematics. 42 (1): 1–82. doi:10.1016/0001-8708(81)90052-9.
3. Hinze, Ralf; Jeuring, Johan (2001). "Functional Pearl: Weaving a web". Journal of Functional Programming. 11 (6): 681–689. doi:10.1017/S0956796801004129. ISSN 0956-7968. S2CID 35791452.
4. Generic Zipper: the context of a traversal
5. jafingerhut (22 October 2010). "clojure.zip/zipper". ClojureDocs. Retrieved 15 June 2013.
6. Chung-chieh Shan, Oleg Kiselyov (17 August 2008). "From walking to zipping, part 1". Retrieved 29 August 2011.
7. Chung-chieh Shan, Oleg Kiselyov (17 August 2008). "From walking to zipping, part 2". Retrieved 29 August 2011.
8. Chung-chieh Shan, Oleg Kiselyov (17 August 2008). "From walking to zipping, part 3". Retrieved 29 August 2011.

Further reading

• Huet, Gerard (September 1997). "The Zipper" (PDF). Journal of Functional Programming. 7 (5): 549–554. doi:10.1017/s0956796897002864. S2CID 31179878.
• Hinze, Ralf; Jeuring, Johan; Löh, Andres (May 2004). "Type-indexed data types". Science of Computer Programming. 51 (1–2): 117–151. doi:10.1016/j.scico.2003.07.001.

External links

• Zipper
• Theseus and the Zipper
• "Roll Your Own Window Manager: Tracking Focus with a Zipper"
• Definition
• "An Applicative Control-Flow Graph Based on Huet's Zipper"
• Infinitesimal Types