I spent some time the other day thinking about zippers and structural editors and I wanted to share some of the ideas, because they were interesting, so this is going to be a thread about that
Post
Replies:
15
Boosts:
1
historically, the underline/box cursor and the vertical line cursor had different meanings/usages
the vertical line cursor was an insertion cursor that indicated you were going to insert a character at the cursor position BETWEEN existing characters in the string
thats why it was a vertical line -- to fit between two characters. sometimes a subscripted ^ was used for a similar purpose
the underline and box cursors were whole character width because they would be overlaid on top of an existing character to indicate that the character would be _replaced_ and _overwritten_
if you've ever wondered what the "Insert" key on a keyboard is for, it's for toggling between insertion and overwrite ("overtype") mode
overwrite was the default for decades, because terminals were _typewriters_ and you literally couldn't insert at all
so early electronic terminals kept the overwriting as a default, and also offered an insertion mode with a key to toggle. this is also why backspacing sometimes seems to do nothing in terminal emulators except move the cursor to the left -- teletypes couldn't backspace either
the distinction between the Insert line cursor and the Overtype box cursor lines up rather neatly with the kind of zippers I mentioned earlier
text editing zippers are INSERT zippers, while tree zippers are OVERTYPE zippers
interesting!
in the case of a text editing zipper for overtype mode, that's pretty easy too:
it's not a pair of strings, but rather a string for the reversed stuff before the overwritable character, the character that would be overwritten with an edit, and the string after the character
but strings/lists are just a kind of single-branching tree, so strings should ALSO have an overtype-style zipper when viewed as trees, and they do: it plucks out an entire sub-list from the string
at this point its useful to emphasize that in tree zippers, there are two parts -- the node in focus, and the context of the rest of the tree around the node
similar to how overtype for strings is a character in focus and the rest of the string around it (qua pair of strings)
for a string-as-tree, the overtype zipper is still a node plus the tree around it
in this case, the node is an entire sub-string, ie a sublist, i.e. the tail of some portion of a non-empty list
the context is the rest of the tree around it, ie the not-tail part of the list
this is basically an insertion zipper for a text editing string, which is a neat fact
perhaps we can make some larger unification of these ideas to understand how to get insertion editing operations for trees!
the observation to make is that if we view a text insertion zipper as a normal tree overtype zipper on a string, rather than a true insertion zipper, we can analyze insertion and overtype as follows:
a string-with-insertion-cursor, such as
fo|o
corresponds to the tree zipper
"o" @ "fo_"
where the LHS of @ is the thing in focus, the RHS is the one-hold context (with an _ representing the hole)
the act of typing a character, such as 't' should produce the string-with-insertion-cursor
fot|o
which is
"o" @ "fot_"
which is equivalent to updating the zipper to
"to" @ "fo_"
and then navigating to the next recursive tree position
but when we view these tree contexts through McBride's tube view, where a one hole context is a stack of frames of local subtrees, we get this:
fo|o
is the tube-y zipper
"o" @ [ 'o':_, 'f':_ ]
and
fot|o
is
"o" @ [ 't':_, 'o':_, 'f':_ ]
