Cursors, Part 5: The Tree Cursor

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:

data TreeCursor a = TreeCursor
    { treeAbove :: Maybe (TreeAbove a)
    , treeCurrent :: a
    , treeBelow :: Forest a
    } deriving (Show, Eq, Generic)

data TreeAbove a = TreeAbove
    { treeAboveLefts :: [Tree a] -- In reverse order
    , treeAboveAbove :: Maybe (TreeAbove a)
    , treeAboveNode :: a
    , treeAboveRights :: [Tree a]
    } deriving (Show, Eq, Generic, Functor)

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 treeAboveLefts, treeAboveNode and treeAboveRights work just like a NonEmptyCursor, and treeAboveAbove` allows the tree cursor to have parents recursively.

Movements

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:

treeCursorSelectNextOnSameLevel :: TreeCursor a -> Maybe (TreeCursor a)
treeCursorSelectNextOnSameLevel tc@TreeCursor {..} = do
    ta <- treeAbove
    case treeAboveRights ta of
        [] -> Nothing
        Node c f:xs ->
            Just $ TreeCursor
              { treeAbove =  Just $
                ta
                  { treeAboveLefts =
                      Node (treeCurrent tc) (treeBelow tc)
                      : treeAboveLefts ta
                  , treeAboveRights = xs
                  }
              , treeCurrent = n
              , treeBelow = f
              }

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.

References

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.