Cursors, Part 3: The Nonempty List Cursor

This is the third post in a series about cursors. In this post we will discuss cursors for nonempty lists.

Disclaimer: cursor is a library based off the concepts outlined in this blog post. It originated in the work on smos, a Purely Functional Semantic Editor.

Looking at an element.

If a list is guaranteed to not be empty, then we can take advantage of this invariant to make a cursor that looks at an element, instead of between two elements.

An example of such a cursor could look something like the following. This cursor is for a list of names:

- Joey
- Frank
- Gerard <-- User is looking here
- Louis

We can go through the same mental exercise of the lists cursors again, but now we already now that we do not want to just keep a list of names and an index of where the user is looking.

The nonempty list cursor

A nonempty list cursor looks very similar to the regular list cursor, but now we also store the exact element that the user is looking at:

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

As in the list cursor, the elements before and the elements after the selected element are both stored as a stack. This allows for constant-time movements.

The example above would then be stored as follows:

NonEmptyCursor
  { previous = ["Frank", "Joey"]
  , current = "Gerard"
  , next = ["Louis"]
  }

Making and rebuilding a nonempty list cursor is relatively simple now too:

makeNonEmptyCursor :: NonEmpty a -> NonEmptyCursor a
makeNonEmptyCursor (a :| as) = NonEmptyCursor
  { previous = []
  , current = a
  , next = as
  }

rebuildNonEmptyCursor :: NonEmptyCursor a -> [a]
rebuildNonEmptyCursor lc = reverse (previous lc) ++ [current lc] ++ next lc

There are plenty more functions available in the nonempty list cursor API and they are fairly straight-forward. Note that the type there is defined slightly differently: with an extra type parameter. More about that in the next post.

References

Nonempty list 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.