And Now For Something Completely Different—Ropes

Well, I guess you can teach an old dog new tricks. I just got introduced to a new datatype—Ropes. Ropes are a “new” type of string-like data that definitely can have its uses. See the Wikipedia article here for an introduction to Ropes. The article is called Rope (Data Structure) and it says in part:

A rope is a binary tree where each leaf (end node) holds a string and a length (also known as a “weight”), and each node further up the tree holds the sum of the lengths of all the leaves in its left subtree. A node with two children thus divides the whole string into two parts: the left subtree stores the first part of the string, the right subtree stores the second part of the string, and node’s weight is the sum of the left child’s weight along with all of the nodes contained in its subtree.

For rope operations, the strings stored in nodes are assumed to be constant immutable objects in the typical nondestructive case, allowing for some copy-on-write behavior. Leaf nodes are usually implemented as basic fixed-length strings with a reference count attached for deallocation when no longer needed, although other garbage collection methods can be used as well.

It lends itself to uses in a Unicode string, because not all leaves need to be the same width.

In the article is a comparison to monolithic strings, outlining, the advantages and disadvantages of Ropes.

The Wikipedia article complains that the article mainly references  only one article, but Casey Ransberger said on the Cuis-dev mailing list:

Found the link for the paper I read about the “ropes” data type. Figured I’d share it around for interested folks.

ALSO! Grab this next one quickly, as it’s free on the ACM’s digital library for a limited time due to them opening up the library during the COVID-19 crisis. It’s a paper describing an experience implementing Ropes using Traits in Pharo. It seems that much more significant per-capita reductions in code duplication were achieved by using Traits in the Ropes implementation than were accomplished in the older experiment (referenced in the paper) which involved reimplementing the collections hierarchy using Traits. Seemed relevant to the conversation, and given the limited window for people without ACM memberships to download it, I had to bring it up: