Skip to content

Latest commit

 

History

History
208 lines (164 loc) · 11.1 KB

README.md

File metadata and controls

208 lines (164 loc) · 11.1 KB
Raw

Double-Ended Iterator and Destructuring

Stauts: Stage 1

Author: HE Shi-Jun (hax)

Champion: HE Shi-Jun (hax)

Motivation

Python and Ruby support (first, *rest, last) = [1, 2, 3, 4], CoffeeScript supports [first, rest..., last] = [1, 2, 3, 4], and Rust supports [first, rest @ .., last] = [1, 2, 3, 4], all resulting in first be 1, last be 4, and rest be [2, 3]. But surprisingly [first, ...rest, last] = [1, 2, 3, 4] doesn't work in JavaScript.

And in some cases we really want to get the items from the end, for example getting matchIndex from String.prototype.replace when using a function:

string.replace(pattern, (fullMatch, ...submatches, matchIndex, fullString) => {
  // `matchIndex` is always the second to last param (the full string is the last param).
  // There may be many submatch params, depending on the pattern.
})

Solution

A naive solution is making let [first, ...rest, last] = iterable work as

let [first, ...rest] = iterable
let last = rest.pop()

The concern is it requires saving all items in the rest array, although you may only need last. A possible mitigation is supporting [..., last] = iterable which saves the memory of rest, but you still need to consume the entire iterator. In the cases where iterable is a large array or something like Number.range(1, 100000), it's very inefficient. And in case like let [first, ..., last] = repeat(10) which repeat is a generator returns infinite sequence of a same value, theoretically both first and last could be 10, but you just get a dead loop.

Instead of the naive solution, we introduce the double-ended iterator (like Rust std::iter::DoubleEndedIterator). A double-ended iterator could be consumed from both ends, next() consume the first item from the rest items of the sequence, nextLast() consume the last item from the rest items of the sequence.

let a = [1, 2, 3, 4, 5, 6]
let deiter = a.values() // suppose values() would be upgraded to return a double-ended iterator
deiter.next() // {value: 1}
deiter.next() // {value: 2}
deiter.nextLast() // {value: 6}
deiter.next() // {value: 3}
deiter.nextLast() // {value: 5}
deiter.nextLast() // {value: 4}
deiter.nextLast() // {done: true}
deiter.next() // {done: true}

With double-ended iterators, let [a, b, ..., c, d] = iterable would roughly work as

let iter = iterable[Symbol.iterator]()
let a = iter.next().value
let b = iter.next().value
let d = iter.nextLast().value
let c = iter.nextLast().value
iter.return()

Generator

Generator functions provide a concise syntax to create iterators in the userland. For example, you can write values(arrayLike) which returns iterator for all array-likes:

function *values(arrayLike) {
  let i = 0
  while (i < arrayLike.length) {
    yield arrayLike[i]
    i++
  }
}

To implement double-ended version of values(arrayLike) in userland, we could use the doubleEnded helper:

const values = doubleEnded(function *values(arrayLike, context) {
  let i = 0, j = 0
  while (i + j < arrayLike.length) {
    if (context.method == "nextLast") {
      yield arrayLike[arrayLike.length - 1 - j]
      j++
    } else { // context.method == "next"
      yield arrayLike[i]
      i++
    }
  }
})

It could also be used as decorator (stage 3 proposal):

class IntRange {
  constructor(start, end) {
    if (!Number.isSafeInteger(start)) throw new TypeError()
    if (!Number.isSafeInteger(end)) throw new TypeError()
    this.start = start; this.end = end; Object.freeze(this)
  }
  @doubleEnded *[Symbol.iterator](context) {
    let {start, end} = this
    while (start < end) {
      if (context.method == "nextLast") yield --end
      else yield start++
    }
  }
}

Iterator helpers and reverse iterator

Iterator helpers add some useful methods to iterators and async iterators. Most methods are easy to upgrade to support double-ended. For example, map() could be implemented like:

// only for demonstration, the real implementation should use internal slots
Iterator.prototype.map = function (fn) {
  let iter = {
    __proto__: Iterator.prototype,
    return(value) { this.return?.(); return {done: true, value} }
  }
  if (this.next) iter.next = () => fn(this.next())
  if (this.nextLast) iter.nextLast = () => fn(this.nextLast())
  return iter
}
// usage
let [first, ..., last] = [1, 2, 3].values().map(x => x * 2)
first // 2
last // 6

Furthermore, some extra iterator helpers like toReversed, takeLast, dropLast and reduceRight, etc. could be introduced.

For example, toReversed():

// only for demonstration, the real implementation should use internal slots
Iterator.prototype.toReversed = function () {
  let next = this.nextLast?.bind(this)
  let nextLast = this.next?.bind(this)
  let ret = this.return?.bind(this)
  return {
    __proto__: Iterator.prototype,
    next, nextLast, return: ret,
  }
}
// usage
let a = [1, 2, 3, 4]
let [first, ..., last] = a.values().toReversed()
first // 4
last // 1

With double-ended iterators and toReversed() helpers, we may not need reverse iterator. Even we still want reverse iterator as a separate protocol, we could also easily have a default implementation for it.

Iterator.prototype[Symbol.reverseIterator] = function () {
  return this[Symbol.iterator].toReversed()
}

FAQ

I like the idea of allowing ... in the middle of the destructuring pattern, but why introduce "double-ended" iterator?

Because JavaScript [first, ...rest] = sequence destructuring is based on iterable protocol, so we should make [first, ...rest, last] = sequence also based on iterable protocol. And [a, b, ...rest, c, d, e] = sequence could be perfectly interpreted as "take first two elements from the sequence, then take last three, and the rest", aka. allowing take elements from the the other end of a sequence, which conceptually same as what "double-ended" mean in the common data structure deque. Note JavaScript already have some Array APIs behave as double-ended: 'indexOf/lastIndexOf, reduce/reduceRight, find/findLast', etc. So generalizing the concept could increase the consistency of all APIs (include user-land libraries) which may based on similar abstraction. See Optional Mechanisms for Double-ended Destructructing for further analysis about the consideration of performance, mental burden and design cost.

How could a iterator/generator move back to the previous status?

It's not "move back" or "step back", it's "consume the next value from the other end" or "shorten range of values from the other end".

There are two concepts easy to confuse, bidirectional vs. double-ended. Bidirectional means you can invoke next() (move forward) or previous() (move backward). Double-ended means you can invoke next() (consume the first item from the rest items of the sequence) or nextLast() (consume the last item from the rest items of the sequence).

The initial version of this proposal used next("back") which follow Rust nextBack(). The term "back" may come from C++ vector/deque (see https://cplusplus.com/reference/vector/vector/back/), means "last element". This term usage is not popular in JavaScript ecosystem and cause confusion, so we changed the word from "back" to "last".

What is "double-ended", how it differ to "bidirectional"?

To help understand the concepts, you could imagine you use cursors point to positions of a sequence and get value at the position. Normal iteration need only one cursor, and initally the cursor is at the most left side of the sequence. You are only allowed to move the cursor to right direction and get the value of the position via next(). Bidrectional means you could also move the cursor to left direction via previous(), so go back to the previous position of the sequence, and get the value (again) at the position.

Double-ended means you have two cursors and initally one is at the most left side and can only move to right direction, the other is at most right side and can only move to left direction. So you use next() move the first cursor to right and get the value at its position, use nextLast() move the second cursor to left and get the value at its position. If two cursors meet the same postion, the sequence is totally consumed.

You could find these two concept are actually orthogonal, so theorcially we could have both bidirectional and double-ended. So next()/previous() move the first cursor right/left, nextLast()/previousLast() move the second cursor left/right.

Note, even these two things could coexist, bidirectional is not compatible with JavaScript iterator protocol, because JavaScript iterators are one-shot consumption, and produce {done: true} if all values are consumed, and it is required that next() always returns {done: true} after that, but previous() actually require to restore to previous, undone state.

Prior art

Previous discussions

Old discussions