Vavr: Consider the Rope data structure as a new data type for javaslang

[nfekete]

An immutable (from the external point of view of the API) Rope would essentially bring structural sharing for strings in the same way a Vector brings structural sharing to immutable lists. Instead of making a copy of the whole String, a Rope would be memory efficient in keeping different versions of a string throughout it's evolution when modifying the content. It might also be more efficient when dealing with mutations on very large strings.

[paplorinc]

Interesting, I didn't know about this data structure.
If I'm mistaken correctly, it's mainly the logarithmic insert/delete that's better than normal String, right?
We've had a similar experiment, i.e. an "immutable StringBuilder" with Vector as a base, but it didn't materialize.
@danieldietrich, what do you think, is this different enough to give it a trie (pun intended)?

[danieldietrich]

@paplorinc I've thought about it the last days. I think it is an interesting data structure but it has the following disadvantages for us:

• It is rarely used because it has a very special use-case. It is optimized for operations on big texts (like in text editors) but generally most collection instances contain only a few elements. With Javaslang we target "Making general purpose Java programming more efficient".
• Adding Rope increases the number of collections, which increases the overall complexity - not only from the viewpoint of the maintainers but also from the user perspective. For "Average Java-Joe" it might be not transparent when to use which data structure (Vector<String> vs CharSeq vs Rope). The less collections, the better.
• We (loosely) align with Scala, which also has not a Rope collection.

I'm still searching an argument that says we urgently need a Rope in Javaslang. But I think it will not make it into the lib.

[paplorinc]

"Making general purpose Java programming more efficient".

Make Java great again!

[danieldietrich]

@nfekete I think a Rope is too special for a general purpose collection library.

For example we expose only one Tree implementation, a general purpose multi-way tree. But internally we have special trees: RedBlackTree for TreeSet/Map, HashArrayMappedTrie for HashSet/Map and BitMappedTrie for Vector.

I hope you understand if we do not implement it.

[nfekete]

@danieldietrich sure, I was rather thinking of contributing an implementation in case I need to implement it for my own purpose. But I'm not yet sure I even need it. A simple Vector<String> might be enough to model something similar, but I haven't given it much thought yet.