3 ms·
Well, self-correction: not a binary tree in the traditional sense, since only the leaf nodes contain the elements. It's that each of the two tree pointers eithe
by trealira 2y ago
Well, self-correction: not a binary tree in the traditional sense, since only the leaf nodes contain the elements. It's that each of the two tree pointers either points to another subtree, or to the start of a list, but not both.
- trealira 2y agoI've just realized that what I'm describing is called a rope data structure: https://en.wikipedia.org/wiki/Rope_(data_structure) https://en.wikipedia.org/wiki/Rope_(data_structure) So, a difference list is a rope, but encoded with closures instead of explicit trees.