Zipper Contexts and Differentiation
It has been shown that the type of the items in the context list produced by the zipper transformation is the "derivative" of the original type in a sense that is loosely related to differentiation in calculus. Intuitively, each item represents the "difference" between an internal substructure and its next containing structure. When the types are described in a particular way, the representation of the original type looks like a polynomial, and the representation of the type of context items looks like the derivative of that polynomial.
For instance, a binary tree with nodes of type A can be represented by the inductive definition: 1+A×T2 → T, that is: a tree is either empty, or a tuple consisting of a value of type A and two subtrees. The derivative of 1+A×T2 is 2×A×T, that is: a tuple consisting of a binary flag, a value of type A and a sibling tree. This is precisely the information needed, given a particular subtree, to construct its parent tree. The boolean flag is an indicator of whether the subtree was on the left or right, the value of type A is the value at the parent, and the value of type T is the sibling subtree. Then, one can reconstruct a tree given one of its subtrees and a list of such derivatives, called a path. The subtree has been effectively separated out (or pointed out) and each item in the list contains the information to reconstruct a node along the path from subtree to the top of the tree.
Read more about this topic: Zipper (data Structure)
Famous quotes containing the word contexts:
“The “text” is merely one of the contexts of a piece of literature, its lexical or verbal one, no more or less important than the sociological, psychological, historical, anthropological or generic.”
—Leslie Fiedler (b. 1917)