2010-06-19

Zipper for faster tree modifications

Novelang uses immutable trees to represent a document and transform it. While immutable data structure have well-known advantages, Novelang's tree library requires to update every parent node on each change on any child node. Clever guys found how to save those changes when performing multiple local modifications. This relies on a tree structure called Zipper. Here is a very clear explaination, the original paper (site currently down), the Scala implementation and the Clojure one.

No comments: