Comment by sleepychu

9 years ago

Had an assignment in functional programming which was to implement a text editor, an interesting data structure was provided.

Buffer of X is a BackwardsList of X, Cursor X, ForwardsList of X

So if you make Line a Buffer of char and your document a Buffer of Line you can easily insert and remove characters on a line or lines in the document.

If you wanted to move the cursor forwards you could just place the cursor onto the head of the backwards list behind you and take the head off the forwards list in front of you to be your cursor.

Such a structure is called a Zipper, for anyone wanting to look into it further.

  • In this case it's a Zipper for a list. You can write zippers for other data structures as well (and in fact you can mechanically derive them, even).

They were trying to get you to learn ZipLists, I imagine.

  • In Haskell a ZipList has not much to do with a zipper, if memory serves right. It's just a newtype wrapper around a normal list to get a different Applicative instance.