Want a way to iterate through a tree from right to left

[xinxinw1]

Hi @aureooms, I've been using your Finger tree javascript implementation in an online calculator that I'm building and so far it has been really good and easy to use. However today I found that I needed to iterate through the items of a tree from right to left and realized this was gonna be really difficult to do efficiently without changing your fingertree code.

Would it be possible to add something like an Tree#reverseIter() method or something like it to the tree API that'll efficiently iterate through the tree from right to left like Tree[Symbol.iterator]() does from left to right?

I'm guessing part of the implementation will probably look something like

Deep.prototype.reverseIter = function* () {
	yield* this.left.reverseIter();
	for (const node of reversed(this.middle)) yield* node.reverseIter();
	yield* this.right.reverseIter();
};

but I'm not familiar enough with the code to be sure of the details.

[make-github-pseudonymous-again]

Hi @xinxinw1! After a quick glance I think that you would need at least a reverseIter method for each possible implementation of a tree: Deep, Single, Empty, and Lazy. Using reversed on this.middle would be quite bad (with an implementation similar to https://github.com/aureooms/js-itertools/blob/main/src/map/reversed.js). The code for Deep should look like

Deep.prototype.reverseIter = function* () {
	yield* reversed(this.right);
	for (const node of this.middle.reverseIter()) yield* reversed(node); 
	yield* reversed(this.left);
};

Note that we iterate first on the right digit then on the left digit.

To achieve the best performance I guess that digits and nodes could also get an implementation of reverseIter. But for a first implementation the only part where it feels necessary is for this.middle since its size can be arbitrary (digits and nodes have size at most 4).

Just a sanity check, following the definition of a tree:

data Tree x = Empty
            | Single x
            | Deep ( Digit x ) ( Tree ( Node x ) ) ( Digit x )

In the sketched implementation of Deep.prototype.reverseIter above:

• yield* reversed(this.right); yields elements of type x in reverse order.
• for (const node of this.middle.reverseIter()) yields elements of type Node x in reverse order.
  • yield* reversed(node); yields elements of type x in reverse order.
• yield* reversed(this.left); yields elements of type x in reverse order.

Before this gets implemented here, you can try to write a function that achieve the same. You need to branch depending on the tree implementation:

const reverseIter = ( tree ) => {
    switch (tree.constructor) {
        case Empty: return reverseIterEmpty();
        case Single: return reverseIterSingle(tree);
        case Deep: return reverseIterDeep(tree);
        case Lazy: return reverseIterLazy(tree);
        default: throw ...;
    }
};

Then implement each case. You could even add digits and nodes to the switch once it works (One, Two, Three, Four, Node2, Node3).

Can you try this?

[make-github-pseudonymous-again]

Note that it makes sense to implement this reverse iteration since monoid addition is associative.

[make-github-pseudonymous-again]

@xinxinw1 You can now use for (const el of tree.reversed()) .... It currently returns an IterableIterator. I may make it return a tree in the future but even then for ... of ... will still work. If you want a tree with the items in reverse you can use from(measure, tree.reversed()).