CODEWITHSUNDEEP
typescriptiterable
kaba
kaba

Reputation: 735

Multiple traversals over iterable in Typescript

What is a good way of dealing with multiple traversals over an Iterable in Typescript?

In general, an Iterable can be traversed only once, after which it yields no new elements. For example, IterableIterator is an Iterable with this property. Therefore, one solution to traverse a sequence multiple times is to first copy it to an array (say).

When the Iterable can already be traversed multiple times, such as with Array, this copying is redundant. Therefore, as an optimization it would seem worthwhile to create a possiblyCopyForMultipleTraversals() function which returns a copy only when necessary. A conservative implementation of this function would detect standard collections such as Arrays and Sets and avoid a copy for them. Can such a function be implemented generically?

Upvotes: 0

Views: 1030

Answers (2)

Richard Stiller
Richard Stiller

Reputation: 173

Maybe this is the way to go:

type FIterable<T> = (() => Iterable<T>) | Iterable<T>;
export function* run<T = any>(...its: FIterable<T>[]) {
    while (true) {
        for (const it of its) {
            if (typeof it === 'function') {
                yield* it(); // this throw a type error but compile :)
            } else {
                yield* it;
            }
        }
    }
}

// Example:
export const map: Map<number, number> = new Map([[1, 2], [3, 4]]);
const a = run(() => map.keys(), [5, 6, 7], new Set([8, 9]));
for (const _ of Array(10)) {
    console.log(a.next());
};

JS/TS generators can iterate generators by using yield*. The problem with the single way iterable should solve with functions, why not create a iterable again?

In this example only the map can not repeated.

my tsconfig.json

{
    "compilerOptions": {
        "module": "UMD",
        "target": "es5",
        "lib": [
            "es2015",
            "es2015.iterable",
            "dom"
        ]
    },
    "files": [
        "app.ts"
    ]
}

Upvotes: 0

jcalz
jcalz

Reputation: 327624

This isn't necessarily perfect, but along the lines of "create one yourself":

You can make a MultipleIterable interface which exposes nothing more than a property whose value is true if the object represents an Iterable whose iterator method produces a "fresh" iterator each time it is called:

export interface MultipleIterable<T> extends Iterable<T> {
  multipleIterable: true;
}

As well as a function you can call on an Iterable to check if it is also MultipleIterable:

function isMultableIterable<T>(iterable: Iterable<T>): iterable is MultipleIterable<T> {
  return (iterable) && ((iterable as any).multipleIterable === true);
}

Then you can, if you want, augment Array's prototype to signal that arrays are MultipleIterable:

declare global {
  interface Array<T> {
    multipleIterable: true;
  }
}
Array.prototype.multipleIterable = true;

Similarly you could modify the prototype of any built-in iterable that behaves this way.

Then, you can create a ReplayableIterable<T> class whose constructor takes any Iterable<T> and wraps it in such a way that its iterators are always fresh:

class ReplayableIterable<T> implements MultipleIterable<T> {

  multipleIterable = true as true;

  [Symbol.iterator](): Iterator<T> {
    let cur = 0;
    let iterable = this;
    return {
      next(): IteratorResult<T> {
        while (cur >= iterable.iteratorResults.length) {
          iterable.iteratorResults.push(iterable.iterator.next());
        }
        const ret: IteratorResult<T> = iterable.iteratorResults[cur];
        cur++;
        return ret;
      }
    }
  }

  private iterator: Iterator<T>;
  private iteratorResults: Array<IteratorResult<T>>;

  constructor(iterable: Iterable<T>) {
    this.iterator = iterable[Symbol.iterator]();
    this.iteratorResults = [];
  }

}

The idea is that the passed-in iterable is used to get just one iterator, and the results from processing that iterator are stored in an array. Iterators handed out by the ReplayableIterable only consult the actual iterator if it exhausts the array contents. This is lazily copying the iterator: if the passed-in iterable has a billion elements (or worse, infinite) but you only plan to traverse a few of them, you don't have to take the memory and time hit of copying the elements you'll never use (the time hit for generators that never terminate would be quite substantial indeed).

And finally, export a function that converts any Iterable to a MultipleIterable either by handing back the parameter unchanged (if you give it a MultipleIterable to begin with) or by constructing a ReplayableIterable based on it.

export function toMultipleIterable<T>(iterable: Iterable<T>): MultipleIterable<T> {
  return isMultableIterable(iterable) ? iterable : new ReplayableIterable(iterable);
}

Hope that helps; good luck!

Upvotes: 1

Related Questions