next/prev for non-async iterators?

💡 Ideas
1

It would be convenient to be able to go next() or prev() on an iterator (or some similar construct, if not an iterator).

For example, to do this with a Set, we currently have to convert it into an Array, then use index math.

It would be nice to be able to (somehow?) be able to go forward or backward on a Set. This could avoid alternatives like linked lists (including circular). For example,

const set = new Set([1, 2, 3, 4])

set.prev() // go to last item so first next() call hits first item (or maybe this is default, or something)

console.log(set.next()) // 1
console.log(set.next()) // 2
console.log(set.next()) // 3
console.log(set.prev()) // 2
console.log(set.next()) // 3
console.log(set.next()) // 4
console.log(set.next()) // 1

That illustrates the idea, but maybe its not a good API, because it is not inherently iterable by our standards. Would it be plausible to add this to iterators somehow? For example:

const iter = set.values()

console.log(iter.nextItem()) // 1
console.log(iter.prevItem()) // 4

and a way to control the order of automatic iteration, f.e.

set.forward = false // or something
for (const val of set) console.log(val) // 4, 3, 2, 1

set.forward = true
for (const val of set) console.log(val) // 1, 2, 3, 4

or (just to throw in alternative ideas):

for (const val of set.reverse()) console.log(val) // 4, 3, 2, 1

for (const val of set) console.log(val) // 1, 2, 3, 4

for (const val of set.startAt(1)) console.log(val) // 2, 3, 4, 1

Or something.

Basically just wondering if this is possible to add, because it may be convenient to use a Set for certain reasons compared to a linked list, namely when order doesn't matter.

2

Neither all that active, but those are places you could start.

1 Like
3

I opened a topic in proposal-deiter.

proposal-reverseIterator seems to be empty, a clone of the template repo and nothing more.

Here's a use case that becomes simplified, and this example is obviously not very well thought out (next() actually returns {value: ___, ...}), but it shows what the end-user desire is:

const set = new Set(...) // maybe this comes from somewhere else (imported, component prop, etc)

const vals = set.values()
let selected = vals.next()

// ... some reactive framework template ...
return <div>
  <p>name: {selected.name}</p>
  <button onclick={() => selected = vals.next()}>next</button>
  <button onclick={() => selected = vals.prev()}>prev</button>
</div>
4

Indeed, the reverse iterator proposal is a replacement of https://github.com/leebyron/ecmascript-reverse-iterator, initially just based off of a gist, but we haven't populated the proposal repo yet: https://github.com/tc39/notes/blob/4c253a989e8da200bc8c351f1e0a557e2a5d73e4/meetings/2019-07/july-23.md?plain=1#L648-L711

5

I think i have more of the context than anyone else at this point. I would be one of the people still eager to participate in this work, but I'm not in favor of an iter.prev proposal because I'm not in favor of a both-direction cursor. While a cursor can be great way of navigating a concrete (memory-allocated) data structure, an iterator cursor introduces some major fuzziness, e.g. can you really trust that calling next followed by prev will get you back to where you started? If your cursor was truly an index into an array this property of the system would be beyond dispute, but with iterators you can only hope that the illusion of cursoring is preserved.

On the other hand if iter.next() remains the only API for getting the next element, it would in no way prevent the iteration of items in a reverse order.

6

I think the solution to that fuzziness is to treat it like a linked list. If items are removed ahead, or behind, then when you go in either direction you do not encounter those items, and you also don't encounter holes.

This is already how iter.next() works, right? If you delete something ahead, it will not come up when you proceed in that direction.

So a cursor-like feature would similarly not see any previous items if they were removed. And it would see any new items if they were inserted (Sets don't allow insertion though).

And if the current item is deleted, then it would either go forward by one, or next just calls goes to the next one that's available after any that were deleted.

Can this solve the fuzziness? Basically just imagine a linked list.

Maybe iterator is not the best place. Could there be a Link class for link lists, and these would have iterators like Set and Map do?

7

The way iteration and next works is that there’s nothing ahead until you ask for it, and the previous item is gone once you’re given it.

That a subset of iterables are backed by finite complete collections isn’t relevant to the protocol itself.

2 Likes
8

Hmm, I'm starting to think a linked list primitive would be better, if anything: it could have Symbol.iterator (with future new features like iterator.reverse() or similar) to make it iterable for the standard iterator cases (for-of loops, etc), but it would also provide a separate API for navigating the linked list in either direction.

9

How would your linked list be different than an Array? It seems like a normal index loop over an array would get you everything you want to have.

The big problem here is that Iterators are conceptually an abstraction over allocated data and computed data. If I had to pick a name for the kind of API you want, it's a cursoring API, which is only really algorithmically efficient when you have some kind index which allows you to quickly start a traversal in the middle of a list.

10

Possibly to keep an index with an array, but with a linked list you can just have the reference, and go arbitrarily prev/next without having to keep the index.

With an array, if things are inserted, the index needs to be updated. With a linked list, insertion doesn't affect the reference so you can simply go prev/next after that. The only thing that can affect the link reference is if that reference itself is removed, so it needs to emit an event (or something) to tell the holder what the new item in its place is.

Plus, with the linked list, when adding/removing things from the list, it doesn't have to shift all the values to new keys, it only modifies three objects (prev, current (removed/added), and next).

Basically I'm thinking that for certain use cases with large lists, and large sets of large lists, it can be more efficient than arrays, as most of the time an add/remove won't affect anything (O(n)).

Set operations are supposed to be constant too, but it has no indexing.

11

Nothing you're describing requires language support though does it? Do you have a library-space implementation of this that you're already using?