Tuesday, May 03, 2011

[hvubwlpt] Tree of tree of tree of tree

Start with Haskell's Data.Sequence, which is internally represented by a finger tree.   Next, implement rose trees with the children of a node stored in a Sequence instead of a list in order to have rapid access to both the first and the last child.  Let the rose tree represent the data structure for an editor for trees.  (Use zippers to navigate the internal data structure.) Next, implement a sophisticated undo "stack", where the stack is actually a tree, because new edits after some undos actually create a new branch of a the undo tree.  (Navigation of this tree is a UI challenge.)  Let the undo tree also be implemented by a rose tree of finger trees.  We now have a tree of a tree of a tree of a tree.

No comments :