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. 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 file system with operations to go to parent (often cd ..), and to go downwards (cd subdirectory). The zipper is the pointer to the current path. Behind the scenes, 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.
… excerpt ends here. Continue reading the full article.
