Cursors, Part 6: The Forest Cursor

This is the sixth post in a series about cursors. It prepares the final 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 tree cursor. In this post, we will discuss a cursor for forests.

It originated in the work on smos, a Purely Functional Semantic Forest Editor.

The ForestCursor type

A forest, in the containers library, is defined as a list of trees.

type Forest a = [Tree a]

We could start off by modeling a ForestCursor as a list cursor for tree cursors. However, there are a few things wrong with that model.

First, a regular list cursor is not the appropriate cursor to use here. Indeed, a list cursor is used to point in between elements. Instead, we want to use a nonempty list cursor. Note that that means that it becomes impossible to represent a forest cursor with no trees in it. We can wrap the forest cursor in a Maybe if that is a practical problem.

newtype ForestCursor a b
  = ForestCursor
    { forestCursorNonemptyCursor ::
        NonEmptyCursor (TreeCursor a)
    }

The next problem is that there is potentially problematic redundancy in this structure. Indeed, if we use a simple nonempty cursor as defined in the blog post about nonempty list cursors then every element of the nonempty list is a tree cursor. Instead, we only want the selected tree to be represented as a tree cursor. The other trees can remain regular trees. We need to use a slightly modified version of a NonEmptyCursor for that:

data NonEmptyCursor a b = NonEmptyCursor
  { previous :: [b] -- In reverse order
  , current :: a
  , next :: [b]
  }

Here, the selected element of the nonempty cursor can be of a different type. That requires some modifications of its API, but that's already done in the cursor package. (Note that we could make a similar modification to the TreeCursor type.)

The ForestCursor can now be modeled as follows:

newtype ForestCursor a b
  = ForestCursor
    { forestCursorListCursor ::
        NonEmptyCursor (TreeCursor a) (Tree b)
    }

Operations on forest cursors

Once we have a ForestCursor defined as such, the operations on forest cursor can trivially be delegated to either the NonEmptyCursor or the selected TreeCursor. Indeed, operations like moving from tree to tree can be delegated to the NonEmptyCursor while operations like moving deeper can be delegated to the selected TreeCursor.

For this reason, the only important functions to note here are two lenses to the values below.

forestCursorListCursorL ::
       Lens' (ForestCursor a b)
             (NonEmptyCursor (TreeCursor a b) (CTree b))
forestCursorListCursorL =
    lens forestCursorListCursor $ \fc lc -> fc {forestCursorListCursor = lc}

forestCursorSelectedTreeL :: Lens' (ForestCursor a b) (TreeCursor a b)
forestCursorSelectedTreeL = forestCursorListCursorL . nonEmptyCursorElemL

Generalising the type of forestCursorListCursorL is left as an exercise to the reader. (See the solution on Hackage).

There are also some more complex operations that require some interaction between the nonempty cursor and the trees. Feel free to browse through them on Hackage.

Collapsing trees

A final interesting note about forest cursors is that often when using trees or forests in an editor, the user will want to be able to collapse trees and forests. To allow for such a feature, we will need a new datatype to represent collapsable trees and forest.

We can choose to model this concept such that collapsed tree still shows its element, but not the elements below.

data CTtee a =
  CNode a (CForest a)

We can then make the distinction between an open forest and a closed forest. It is not clear whether an empty forest should be considered opened or closed, so we can just use a third constructor to represent empty forests in order to avoid redundancy in the type:

data CForest a
    = EmptyCForest
    | ClosedForest !(NonEmpty (Tree a))
    | OpenForest !(NonEmpty (CTree a))

Next we need to replace the trees and forests in the tree- and forest cursor types by collapsable trees and forests.

newtype ForestCursor a b
  = ForestCursor
    { forestCursorListCursor ::
        NonEmptyCursor (TreeCursor a) (CTree b) -- <- here
    }

data TreeCursor a = TreeCursor
    { treeAbove :: Maybe (TreeAbove a)
    , treeCurrent :: a
    , treeBelow :: CForest a -- <- here
    } deriving (Show, Eq, Generic)

data TreeAbove a = TreeAbove
    { treeAboveLefts :: [CTree a] -- <- here
    , treeAboveAbove :: Maybe (TreeAbove a)
    , treeAboveNode :: a
    , treeAboveRights :: [CTree a] -- <- and here
    }

Now we can implement functions to collapse and un-collapse trees and forest cursors. See the corresponding code on Hackage.

References

Forest 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.