4 ms·
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
by sleepychu 9y 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.
- lomnakkus 9y agoAka a "zipper".
- icen 9y agoSuch a structure is called a Zipper, for anyone wanting to look into it further.
- eru 9y agoIn 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).
- IncRnd 9y agoThey were trying to get you to learn ZipLists, I imagine.
- eru 9y agoIn 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.
- PhineasRex 9y agoThis is conceptually the same as a Gap Buffer, it just uses a different memory layout.