How to clone ES6 generator?

Question

I'm trying to create a List monad in ES6 using generators. To make it work I need to create a copy of an iterator that has already consumed several states. How do I clone an iterator in ES6?

function* test() {
    yield 1;
    yield 2;
    yield 3;
}

var x = test();
console.log(x.next().value); // 1
var y = clone(x);
console.log(x.next().value); // 2
console.log(y.next().value); // 2 (sic)

I've tried clone and cloneDeep from lodash, but they were of no use. Iterators that are returned in this way are native functions and keep their state internally, so it seems there's no way to do it with own JS code.

Oeillade

Answer 1

Iterators […] keep their state internally, so it seems there's no way

Yes, and that for a good reason. You cannot clone the state, or otherwise you could tamper too much with the generator.

It might be possible however to create a second iterator that runs alongside of the first one, by memorizing its sequence and yielding it later again. However, there should be only one iterator that really drives the generator - otherwise, which of your clones would be allowed to send next() arguments?

Cleptomania

Memoizing the previous values would help if I wanted to get previous results one more time, but that's not the point of question. I had an option of memoizing arguments to next, so that I could create another iterator from the same generator and rerun it until the same point. The problem with that approach was that functions in ES are not pure, and it's possible that on the second run of the same generator I'd get other results. I think, that I'd better get into a maillist of harmony and ask the question there if nobody gets with a better idea of cloning an iterator. – Oeillade

Maybe I don't understand your usecase well enough. Is you generator actually pure? Do you ever pass arguments to .next()? How (by what) are the two iterators (original and cloned one) actually consumed? – Cleptomania

I'm trying to run the following code that resembles Haskell's nondeterminism monad (ideone.com/kGF9KY). For each element x of the array iter.next(prev).value I need to pass it as an argument to the next called next, recursively. This way the code after yield is being run several times with different "return values", hence nondeterminism. – Oeillade

I don't think generators support such at all, maybe you'll need to back up and use explicit continuations. I'll investigate though, that nondeterminism monad sounds very interesting. – Cleptomania

In case generators supported that, it would steal the main feature of Haskell: ability to run the same code in different environments. It seems to me that the best way to enable it is to hack into sources of regenerator and show it to ES6 community. That won't be easy :/ – Oeillade

I've made a preliminary implementation of this concept (github.com/polkovnikov-ph/es7-effect). Semantics are currently unsound, and it should take a while to fix that. Most likely it will require immutable data structures to handle scopes, because proper implementation needs to copy the whole scopes. It's clear to me that this is never going to make its way to the language. – Oeillade

Answer 2

I wrote a do-notation library for JavaScript, burrido. To get around the mutable generator problem I made immutagen, which emulates an immutable generator by maintaining a history of input values and replaying them to clone the generator at any particular state.

Circulate

Sweet! I was working on the same thing and came here :D – Harelip

Answer 3

You can't clone a generator--it's just a function with no state. What could have state, and therefore what could be cloned, is the iterator resulting from invoking the generator function.

This approach caches intermediate results, so that cloned iterators can access them if necessary until they "catch up". It returns an object which is both an iterator and an iterable, so you can either call next on it or for...of over it. Any iterator may be passed in, so you could in theory have cloned iterators over an array by passing in array.values(). Whichever clone calls next first at a given point in the iteration will have the argument passed to next, if any, reflected in the value of the yield in the underlying generator.

function clonableIterator(it) {
  var vals = [];

  return function make(n) {
    return {
      next(arg) {
        const len = vals.length;
        if (n >= len) vals[len] = it.next(arg);
        return vals[n++];
      },
      clone()   { return make(n); },
      throw(e)  { if (it.throw) it.throw(e); },
      return(v) { if (it.return) it.return(v); },
      [Symbol.iterator]() { return this; }
    };
  }(0);
}

function *gen() {
  yield 1;
  yield 2;
  yield 3;
}

var it = clonableIterator(gen());

console.log(it.next());
var clone = it.clone();
console.log(clone.next());
console.log(it.next());

Obviously this approach has the problem that it keeps the entire history of the iterator. One optimization would be to keep a WeakMap of all the cloned iterators and how far they have progressed, and then clean up the history to eliminate all the past values that have already been consumed by all clones.

Klein

Nice implementation, +1! You might also want to forward throw and return invocations. If you're interested only in iterators, you should not pass through arg. – Cleptomania

Answer 4

You could do something like is provided in Python itertools.tee, i.e. let a function return multiple iterators that take off from where the given iterator is at.

Once you call tee, you should no longer touch the original iterator, since tee is now managing it. But you can continue with the 2 or more "copies" you got back from it, which will have their independent iterations.

Here is how that function tee can be defined, with a simple example use of it:

function tee(iter, length=2) {
    const buffers = Array.from({length}, () => []);
    return buffers.map(function* makeIter(buffer) {
        while (true) {
            if (buffer.length == 0) {
                let result = iter.next();
                for (let buffer of buffers) {
                    buffer.push(result);
                }
            }
            if (buffer[0].done) return;
            yield buffer.shift().value;
        }
    });
}

// Demo
function* naturalNumbers() {
    let i = 0;
    while (true) yield ++i;
}

let iter = naturalNumbers();

console.log(iter.next().value); // 1
console.log(iter.next().value); // 2

let saved;
[iter, saved] = tee(iter);

console.log("Saved. Continuing...");
console.log(iter.next().value); // 3
console.log(iter.next().value); // 4

console.log("Restored");

iter = saved;

console.log(iter.next().value); // 3
console.log(iter.next().value); // 4
console.log(iter.next().value); // 5

Soult

Nice solution! Btw I think this approach would not have worked for the OP of the other question where you initially posted it, since they actually wanted to fork the generator state itself by passing different arguments to .next(…) on the two branches. A tee really only works for iterators where no argument is passed to .next(). – Cleptomania

Btw, an optimisation for now calling .next() on already closed iterators: const result = iter.next(); for (let buffer of buffers) buffer.push(result); if the buffer is empty, then const const {value, done} = buffer.shift(); if (done) return value; else yield value;. – Cleptomania

Thanks, @Bergi, that is a good idea. I went for leaving the item in the buffer when it has done true. Updated. – Soult

Answer 5

Thanks for the comments on my previous question. Inspired by those and some of the answers here I've made a cloneable_generator_factory to solve the problem:

function cloneable_generator_factory (args, generator_factory, next_calls = [])
{
    let generator = generator_factory(args)

    const cloneable_generator = {
        next: (...args) =>
        {
            next_calls.push(args)
            return generator.next(...args)
        },
        throw: e => generator.throw(e),
        return: e => generator.return(e),
        [Symbol.iterator]: () => cloneable_generator,
        clone: () =>
        {
            // todo, use structuredClone when supported
            const partial_deep_cloned_next_args = [...next_calls].map(args => [...args])
            return cloneable_generator_factory(args, generator_factory, partial_deep_cloned_next_args)
        },
    }

    // Call `generator` not `cloneable_generator`
    next_calls.forEach(args => generator.next(...args))

    return cloneable_generator
}


// Demo
function* jumpable_sequence (args) {
    let i = args.start
    while (true)
    {
        let jump = yield ++i
        if (jump !== undefined) i += jump
    }
}

let iter = cloneable_generator_factory({ start: 10 }, jumpable_sequence)

console.log(iter.next().value)  // 11
console.log(iter.next(3).value)  // 15  (from 11 + 1 + 3)

let saved = iter.clone()

console.log("Saved. Continuing...")
console.log(iter.next().value) // 16
console.log(iter.next(10).value)   // 27  (from 16 + 1 + 10)

console.log("Restored")

iter = saved

console.log(iter.next().value) // 16
console.log(iter.next().value) // 17
console.log(iter.next().value) // 18

For those using TypeScript, here's a link to the playground of the following code:

interface CloneableGenerator <A, B, C> extends Generator<A, B, C>
{
    clone: () => CloneableGenerator <A, B, C>
}

function cloneable_generator_factory <R, A, B, C> (args: R, generator_factory: (args: R) => Generator<A, B, C>, next_calls: ([] | [C])[] = []): CloneableGenerator<A, B, C>
{
    let generator = generator_factory(args)

    const cloneable_generator: CloneableGenerator<A, B, C> = {
        next: (...args: [] | [C]) =>
        {
            next_calls.push(args)
            return generator.next(...args)
        },
        throw: e => generator.throw(e),
        return: e => generator.return(e),
        [Symbol.iterator]: () => cloneable_generator,
        clone: () =>
        {
            // todo, use structuredClone when supported
            const partial_deep_cloned_next_args: ([] | [C])[] = [...next_calls].map(args => [...args])
            return cloneable_generator_factory(args, generator_factory, partial_deep_cloned_next_args)
        },
    }

    // Call `generator` not `cloneable_generator` to avoid args for `next` being multiplied indefinitely
    next_calls.forEach(args => generator.next(...args))

    return cloneable_generator
}


// Demo
function* jumpable_sequence (args: {start: number}): Generator<number, number, number | undefined> {
    let i = args.start
    while (true)
    {
        let jump = yield ++i
        if (jump !== undefined) i += jump
    }
}

let iter = cloneable_generator_factory({ start: 10 }, jumpable_sequence)

console.log(iter.next().value)  // 11
console.log(iter.next(3).value)  // 15  (from 11 + 1 + 3)

let saved = iter.clone()

console.log("Saved. Continuing...")
console.log(iter.next().value) // 16
console.log(iter.next(10).value)   // 27  (from 16 + 1 + 10)

console.log("Restored")

iter = saved

console.log(iter.next().value) // 16
console.log(iter.next().value) // 17
console.log(iter.next().value) // 18

Tocopherol