词条 | 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 layman's explanation for a tree with zipper would be an ordinary computer filesystem with operations to go to parent (often Example: Bidirectional list traversalMany 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:
A list such as To be clear, a location in the list is not just the number of 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 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 is easy to insert or remove values at any particular location in the tree. UsesThe 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
Zipper contexts and differentiationIt 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 related to differentiation in calculus by decategorification. Most datatypes are constructed from products and sums of datatypes; any given datatype looks like a polynomial or a Taylor series, and the representation of the type of context items looks like the derivative of that polynomial or series.[5][6] In a recursive datatype like a list or a tree, the derivative is taken with respect to the recursion variable. Consider a recursive data structure like a binary tree labeled by data of type A. The derivative is computed by introducing a recursion variable and we recover the original data structure by finding the fixed point . The datatype of the context is By taking the fixed point we find that a zipper for a tree consists of a "path" and a downward subtree, where a path is a context list of triples consisting of
In general, then, a zipper for a datatype parameterized by some other type and a recursion variable consists of two parts: a context list with items of type and a copy of the downward substructure Alternatives and extensionsDirect modificationIn a non-purely-functional programming language, it may be more convenient to simply traverse the original data structure and modify it directly (perhaps after deep cloning it, to avoid affecting other code that might hold a reference to it). Generic zipperThe Generic Zipper[7][8][9] 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. References1. ^{{harvnb|Huet|1997}} 2. ^{{cite journal|title=Functional Pearl: Weaving a web|url=http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=90859&fileId=S0956796801004129|doi=10.1017/S0956796801004129|issn=0956-7968|last1=Hinze|first1=Ralf|last2=Jeuring|first2=Johan|journal=Journal of Functional Programming|volume=11|issue=6|pp=681-689|year=2001}} 3. ^Generic Zipper: the context of a traversal 4. ^{{cite web|author=jafingerhut |url=http://clojuredocs.org/clojure_core/clojure.zip/zipper |title=clojure.zip/zipper |publisher=ClojureDocs |date=2010-10-22 |accessdate=2013-06-15}} 5. ^Joyal, André (1981), "Une théorie combinatoire des séries formelles", Advances in Mathematics 42:1-82. 6. ^McBride, Conor (2001), "The Derivative of a Regular Type is its Type of One-Hole Contexts" 7. ^{{cite web|url=http://conway.rutgers.edu/~ccshan/wiki/blog/posts/WalkZip1/|title=From walking to zipping, part 1|author=Chung-chieh Shan, Oleg Kiselyov|date=17 August 2008|accessdate=29 August 2011}} 8. ^{{cite web|url=http://conway.rutgers.edu/~ccshan/wiki/blog/posts/WalkZip2/|title=From walking to zipping, part 2|author=Chung-chieh Shan, Oleg Kiselyov|date=17 August 2008|accessdate=29 August 2011}} 9. ^{{cite web|url=http://conway.rutgers.edu/~ccshan/wiki/blog/posts/WalkZip3/|title=From walking to zipping, part 3|author=Chung-chieh Shan, Oleg Kiselyov|date=17 August 2008|accessdate=29 August 2011}} Further reading
External links
2 : Functional programming|Data structures |
随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识,基本涵盖了大多数领域的百科知识,是一部内容自由、开放的电子版国际百科全书。