Note how I didn't write "Immutable Strings" in the subject.

Boehm describes in [1] a data structure, called a _rope_, that can be
used to represent very long strings efficiently.  The way they are
implemented, where operations that modify the rope return a new rope
that shares as much data as possible with the old one (i.e., a
functional interface), also leads to the nice property that ropes may be
heavily altered without wasting a lot of memory.  Another nice property
is that as one abstracts away the pointer-to-char, ropes can be created
lazily from IO or other generators of data.  As an example, say that we
want a String of one million a's

s = "a" * 1000000

With a Rope, we could have written this as:

r = Rope.new("a", 1000000)

and that could be represented very efficiently.  A better example is if
we would like to search the concatenation of two strings for a regular
expression.  Using only Strings, we would have to write this as:

s1 + s2 =~ /.../

where the whole concatenation of s1 and s2 has to be created before the
matching can take place, taking both O(max(s1.length, s2.length)) time
and space, whereas with ropes this could be written as:

r1 + r2 =~ /.../

and the concatenation would simply be a O(1) time and space operation of
creating a new concatenation node, representing the concatenation of the
two ropes.

The implementation of ropes is rather straight-forward and fits well
with the garbage-collection model of memory allocation, so I was
wondering if there was any interest in seeing a Rope object in Ruby 2.0.
It would give us that immutable string representation that everyone is
always talking about as a plus for choosing Python.  Ropes are also a
lot more memory-friendly than Strings for cases where the text sequence
is long, or is to be heavily modified.

Comments?,
	nikolai

[1] Hans-J Boehm, "Ropes: an Alternative to Strings", Software--Practice
and Experience, vol. 25(12), 1315--1330, Dec. 1995.

-- 
::: name: Nikolai Weibull    :: aliases: pcp / lone-star / aka :::
::: born: Chicago, IL USA    :: loc atm: Gothenburg, Sweden    :::
::: page: www.pcppopper.org  :: fun atm: gf,lps,ruby,lisp,war3 :::
main(){printf(&linux["\021%six\012\0"],(linux)["have"]+"fun"-97);}