Cursors, Part 1: Introduction with the List Cursor

This is the first post in a series about cursors. It explores the motivation behind cursors and uses the list cursor as an example.

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.

Motivation: The cursor problem

Suppose you are writing a terminal user interface (TUI), with brick for example. Sooner or later you will run into the problem that you have to represent two pieces of data at the same time:

The entire text that is currently on the screen.
Where the user is looking within this text.

Example state:

My tex|tual example
      ^- User is looking here

In most languages, you would probably choose one of the following options;

Maintain a linked list of characters and a pointer into that linked list.
Maintain a string, and an index of where the user is looking.

Both of these options the fundamental problem that there can exist values of the data structure that are not valid representations.

In the case of the linked list, the pointers could be arranged incorrectly. In the case of the index into a string, the index could be negative or greater than the length of the list.

The concept of a cursor is intended to solve this problem.

Solution: The cursor

A cursor of a certain data structure contains represents both the entire data structure, and where we are looking within that data structure. Note that these data structures need not be limited to simple data structures such as lists of items, but could be more complex structures such as trees or mappings. Stay tuned for future blogposts to see how those would work. Ideally these pieces of information are represented in such a way that every value of the type is a valid cursor.

Let us have a look at some potential implementations of a list cursor. Remember: a list cursor is a data structure that represents both the entire list, and where a user is looking within that list.

A first attempt: The list cursor with an index

The way a list cursor is usually implemented looks a bit like the following:

data ListCursor a = ListCursor
  { list :: [a]
  , index :: Int
  }

The example state from before, can then be represented as the following value:

ListCursor
  { list = "My textual example"
  , index = 6
  }

To construct a list cursor, we can just start at the start of the list:

makeListCursor :: [a] -> ListCursor a
makeListCursor as = ListCursor { list = as, index = 0 }

Deconstructing a list cursor is then very simple:

rebuildListCursor :: ListCursor a -> [a]
rebuildListCursor = list

We can now start writing functions to look one character to the left or one character to the right. These are the functions that we would want to use to manipulate the editor state when a user presses the left and right arrows on their keyboard, respectively.

listCursorPrev :: ListCursor a -> Maybe (ListCursor a)
listCursorPrev lc 
  | index lc <= 0 = Nothing
  | otherwise = Just $ lc { index = index lc - 1}

listCursorNext :: ListCursor a -> Maybe (ListCursor a)
listCursorNext lc 
  | index lc >= length (list lc) = Nothing
  | otherwise = Just $ lc { index = index lc + 1}

The problem with this type is that there exist values that do not represent a valid cursor. The following is an example of such a value:

ListCursor
  { list = "Example"
  , index = 20
  }

This value is nonsensical. It somehow represents the idea that a user could be looking beyond the text in their editor.

A type-safe list cursor

A more type-safe list cursor could be implemented with two stacks as follows:

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

The idea is that the cursor is represented as two stacks of elements, and that these stacks are to be interpreted such that the user is looking between the top elements of the stacks.

The example state would then be represented as follows:

ListCursor
  { previous = "xet yM"
  , next = "tual example"
  }

Using this definition, every possible value of a ListCursor a will be a valid representation of a list cursor.

To construct a list cursor, we still start at the start of the list, but now that means creating an empty stack on the left:

makeListCursor :: [a] -> ListCursor a
makeListCursor as = ListCursor { previous = [], next = as }

Deconstructing a list cursor is then very simple:

rebuildListCursor :: ListCursor a -> [a]
rebuildListCursor lc = reverse (previous lc) ++ next lc

Writing functions to move around in the cursor becomes simpler too, we just pop from one stack and push onto the other:

listCursorPrev :: ListCursor a -> Maybe (ListCursor a)
listCursorPrev lc = case previous lc of
  [] -> Nothing
  (l:ls) -> Just $ lc { previous = ls, next = l : next lc}

listCursorNext :: ListCursor a -> Maybe (ListCursor a)
listCursorNext lc = case next lc of
  [] -> Nothing
  (r:rs) -> Just $ lc { previous = r : previous lc, next = rs}

References

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. Smos is a purely functional semantic editor of a subset of YAML that is intended to replace Emacs' Org-mode for Getting Things Done. The simplest contribution could be to just try out smos and provide feedback on the experience.