Zipper (data Structure) - Example: Bidirectional List Traversal

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
• Insert(x, L): Constructs a list by inserting value x in front of list L

The list is then constructed as Insert(1, Insert(2, Insert(3, Empty))). It is possible to describe the location of a value in a list as the number of steps from the front of the list to that value. More formally, a location is the number of additional Insert operations used to construct the whole list, after a particular value was inserted.

A context for a location in the list is constructed by recording not just the number of Insert operations, but all of the other information about them—namely, the values that were inserted. These are represented in a separate list that is reversed from the order of the original data structure. Specifically, the context of "3" in the list is represented as . A list with a zipper represents the entire structure, and a location within the structure. This is a pair consisting of the location's context, and the part of the structure that begins at the location. The list with a reference to the "3" is represented as (, ).

With the list represented this way, it is easy to define efficient operations that move the location forward or backward and manipulate the list at that location, for example by inserting or removing items. Similarly, applying the zipper transformation to a tree makes it easy to insert or remove values at a particular location in the tree.