This is the fifth post in a series about cursors. It prepares the first data structure to write a simple forest editor
In the previous posts in the cursors series, we discussed the concept of a cursor, and the implementation of a type-safe (nonempty) list cursor. In this post, we will discuss a cursor for trees.
It originated in the work on
smos, a Purely Functional Semantic Forest Editor.
Trees are nontrivial to model as a cursor. Let's have a look at an example of where a user could be looking:
0 | +- 1 | | | +- 2 <-- Looking here | | | \- 3 | \- 4
The cursor needs to remember the current node, and its children, just like a regular tree. But the cursor also needs to remember all values above and next to the current node. However, if we just store the siblings of the current node, then the result could be a forest and not a tree. This means that the siblings can only exist if there is a parent node. This is captured as follows:
There is a lot to unpack here. The
treeCurrent field is the node that the user is looking at. The
treeBelow field represents the forest of children of the current node. If the
treeAbove field is
Nothing, then the
TreeCursor represents a root node being selected. If the
treeAbove fields contains a
TreeAbove, then the current node is not the root of the tree. In that case, the triple
treeAboveRights work just like a
NonEmptyCursor, and treeAboveAbove` allows the tree cursor to have parents recursively.
There are many movements to define for tree cursors. We will only look at an example.
Moving to the next sibling is a good example of a movement. It is not always possible, and it involves shuffling around the above elements a bit:
Note that this means that moving to the next node is only possible if:
The current node is part of a forest, and not a root.
There is a next node.
Tree cursors are available in the
cursor package on Hackage. Cursors originated in the work on Smos. This post is part of an effort to encourage contributions to Smos. The simplest contribution could be to just try out smos and provide feedback on the experience. Smos is a purely functional semantic forest editor of a subset of YAML that is intended to replace Emacs' Org-mode for Getting Things Done.