CODEWITHSUNDEEP
javascriptecmascript-6generator
Don Hatch
Don Hatch

Reputation: 5402

how to implement a recursive traversal inside an iterator generator in javascript?

Say I have a tree, something like the following, in javascript:

let rootNode = {name:'', children:[
                   {name:'0', children:[
                       {name:'00', children:[]},
                       {name:'01', children:[
                           {name:'010', children:[]},
                       ]},
                       {name:'02', children:[]},
                   ]},
                   {name:'1', children:[
                       {name:'10', children:[]},
                   ]},
               ]};

And I want to do a preorder traversal on it, I could do it like this:

function preOrderTraversalRecursive(rootNode, visitNodeCallback) {
    function recurse(node) {
        visitNodeCallback(node);
        for (let childNode of node.children)
          recurse(childNode);
    }
    recurse(rootNode);
};
console.log("Pre-order traveral, recursive:");
preOrderTraversalRecursive(rootNode, function visitNodeCallback(node) {
    console.log("  '"+node.name+"'");
});

which gives the expected output:

  Pre-order traveral, recursive:
    ''
    '0'
    '00'
    '01'
    '010'
    '02'
    '1'
    '10'

Now let's say I want to do the same thing ES6 generator-style. I thought that would look like this:

function *preOrderGeneratorIteratorRecursive(rootNode) {
    function recurse(node) {
        yield node;
        for (let childNode of node.children)
            recurse(childNode);
    }
    recurse(rootNode);
};
console.log("Pre-order generator iterator, recursive:");
for (let node of preOrderGeneratorIteratorRecursive(rootNode)) {
    console.log("  '"+node.name+"'");
}

But apparently that's illegal: Uncaught SyntaxError: Unexpected strict mode reserved word at the yield.

Disappointing! Is there some syntax I'm missing? What's the cleanest way to make a generator expressing this algorithm? Perhaps using some helper library?

I know I can use an explicit stack as follows, but this isn't satisfactory for several reasons: (1) the logic is obscured to the point where there's no readability advantage to using the generator; might as well go back to the recursive-with-callback version, and (2) it's not really the same algorithm, since it's iterating backwards over each node.children. In particular, this means it won't work if node.children is some other kind of iterable, perhaps from another generator.

function *preOrderTraversalIteratorGeneratorExplicitStackCheating(rootNode) {
  let stack = [rootNode];
  while (stack.length > 0) {
    let node = stack.pop();
    yield node;
    for (let i = node.children.length-1; i >= 0; --i) // backwards
      stack.push(node.children[i]);
  }
} // preOrderIteratorGeneratorExplicitStackCheating
console.log("Pre-order traveral of tree with explicit stack, cheating:");
for (let node of preOrderTraversalIteratorGeneratorExplicitStackCheating(rootNode)) {
  console.log("  '"+node.name+"'");
}

To be clear: I'm not interested in a special-purpose helper that hides the horrible details of an explicit-stack traversal implementation. I want to know if there's a way to write iterator generator algorithms clearly, even if they happen to be recursive.

Upvotes: 4

Views: 116

Answers (2)

Bergi
Bergi

Reputation: 664297

The problem is that your recurse function, in which you're trying to use yield, is not declared as a generator. That's why you're getting a syntax error. It would need to be

function preOrderGeneratorIteratorRecursive(rootNode) {
    function* recurse(node) {
        yield node;
        for (let childNode of node.children)
            yield* recurse(childNode);
    }
    return recurse(rootNode);
}

or simply

function* preOrderGenerator(node) {
    yield node;
    for (let childNode of node.children)
        yield* preOrderGenerator(childNode);
}

Upvotes: 0

lonesomeday
lonesomeday

Reputation: 237847

This is indeed provided for with the yield* operator. Essentially, you need to think of this as one generator delegating its functionality to another. (Indeed, you can delegate to any iterable value.)

For example, you could do this:

function *pointlessGenerator() {
    yield* [1, 2, 3, 4];
}

This would yield 1, 2, 3 and 4, because yield* runs the iterator and yields all of that iterator's values in turn. Exactly the same behaviour takes place if you pass a generator.

In your case you want to make recurse a generator and then call it with yield*: 

function *preOrderGeneratorIteratorRecursive(rootNode) {
    function *recurse(node) {
        yield node;
        for (let childNode of node.children)
            yield* recurse(childNode);
    }
    yield* recurse(rootNode);
};
console.log("Pre-order generator iterator, recursive:");
for (let node of preOrderGeneratorIteratorRecursive(rootNode)) {
    console.log("  '"+node.name+"'");
}

Upvotes: 2

Related Questions