Implement a rope for Tendrils

[kmcallister]

VecDeque<Tendril<F>> should perform well up to moderate chunk counts, since Tendril is a small structure. But we might consider switching to a 2-3 finger tree at some size. Do we need persistent append (i.e. Rope + Rope -> Rope) or only in-place?

[andresilva]

I've started implementing a finger tree in rust (https://github.com/andrebeat/fingers). The data types are slightly different from the original Haskell definition since Rust lacks polymorphic recursion. The current implementation is persistent and uses Rc for subtree sharing. Also, in order for the complexity bounds to hold it is necessary for the middle subtree to be lazily evaluated which it currently isn't.
Do you think this is something that could be useful for the purposes of tendril?

[SimonSapin]

This sounds interesting, but I don’t think anyone is pursuing this kind of thing actively at the moment. Or maybe @asajeffrey?

[asajeffrey]

I'm currently doing experiments with string representations. This could be pretty cool, especially if it's parametric over the representation of flat strings.

[andresilva]

@asajeffrey I'm not sure I understood what you meant to say. Did you mean that it should be possible to do this FingerTree<StrTendril>?

Also my current understanding is that the finger tree would be used to represent very large strings (> 4GB) that wouldn't exist contiguously in memory. The finger tree would basically replace the usage of a VecDeque<Tendril>.

Anyway, the current implementation of the finger tree is lacking, I've only implemented the deque methods so far, push_front and push_back. But I'm definitely up for working through the rest of the paper and implementing the remaining methods, especially if this is something that could be potentially useful.

[asajeffrey]

I mean implement FingerTree and then show (for example) FingerTree
impl ToIter where T impl ToIter, and ditto the other traits for
strings.

Ropes are used for more than just huge strings, they're used for O(1) edit
operations, for example expanding entities.

A.
On Nov 16, 2015 12:37, "Andre Silva" notifications@github.com wrote:

@asajeffrey https://github.com/asajeffrey I'm not sure I understood
what you meant to say. Did you mean that it should be possible to do this
FingerTree?

Also my current understanding is that the finger tree would be used to
represent very large strings (> 4GB) that wouldn't exist contiguously in
memory. The finger tree would basically replace the usage of a
VecDeque.

Anyway, the current implementation of the finger tree is lacking, I've
only implemented the deque methods so far, push_front and push_back. But
I'm definitely up for working through the rest of the paper and
implementing the remaining methods, especially if this is something that
could be potentially useful.

—
Reply to this email directly or view it on GitHub
#5 (comment).

[andresilva]

Ah, I think I understand what you mean and it makes perfect sense! Taking your example, if I can interpret a Tendril as being a sequence of u8 or char, I should also be able to achieve the same representation when using a FingerTree<Tendril>, hiding away the fact that we're using a non-contiguous representation for the data.