Post #1082444

2026-04-09 19:30 UTC

Doing some deep dives on structured text editing. Is anyone aware of any work on *data structures* for editing tree-like data? I’m specifically interested in stuff like multiple cursors, efficient undo/redo, etc. This is directly relevant to my research re: Telecode (which is a tree, or hedge rather), but I’ve not been able to find any papers covering data structures. Sort of unclear to me whether ropes and other usual suspects generalize well to a structured domain

Replies (11)

@clayrat@types.pl 2026-04-09 19:47

@kevin Saw this thing a while ago, might be relevant: https://github.com/hazelgrove/tylr

Open ##2069352
@mnl@hachyderm.io 2026-04-09 19:50

@kevin I know this one from the functional pearls: https://www.st.cs.uni-saarland.de/edu/seminare/2005/advanced-fp/docs/huet-zipper.pdf Maybe there's something to be found in the CRDT/JSON/XML editing territory? https://arxiv.org/pdf/1608.03960

Open ##2069354
@cdrichards@mathstodon.xyz 2026-04-09 19:57

@kevin maybe @raph has pointers?

Open ##2069357
@bjoreman@toot.cafe 2026-04-09 20:01

@kevin I have no knowledge to contribute, but I want to know more about this.

Open ##2069358
@brettm@swarm.coiloptic.org 2026-04-09 20:02

@kevin@kbg.sh vis text editor (vi clone) has multiple cursors and uses structured regular expressions (copied from plan9 sam editor) idk if its suitable for you

Open ##2069359
@pimotte@mathstodon.xyz 2026-04-09 20:04

@kevin I'm not sure if it matches what you're looking for, but prosemirror might have some interesting aspects? https://prosemirror.net/docs/guide/

Open ##2069360
@Susan_calvin@mastodon.social 2026-04-09 20:08

@kevin i'm going to say the OCCAM people must have written papers on this? David May?

Open ##2069362
@ireneista@adhd.irenes.space 2026-04-09 20:10

@kevin oh, super neat question. we are not aware of anything on this topic, we're very interested in hearing what you find.

Open ##2069363
@BoydStephenSmithJr@hachyderm.io 2026-04-09 22:46

@kevin Best I can give you if that for any type you use to represent the tree, it's derivative (https://en.wikipedia.org/wiki/Generalizations_of_the_derivative#Derivative_of_a_type) is a tree plus one cursor (hole). (This generalizes zippers) If that's useful you might check out http://strictlypositive.org/CJ.pdf from @pigworker Your "jokers" are everything before/above your hole; the "clowns" are everything after/below your hole. (This captures a traversal-in-progress, "stuck in the middle" with you.)

Open ##2069364
@SWwind@kazv.moe 2026-04-10 00:38

@kevin take a look at immer, it uses relaxed radix-balanced trees (rrbt)

Open ##2069366
@synlogic4242@social.vivaldi.net 2026-04-11 18:57

@kevin CRDT? also any abstraction which lets you model capability to Undo and Redo. also recommend spelunking through vim's public C source cuz its guaranteed to have faced similar challenges

Open ##2069368