Как реализовать рекурсивный обход внутри генератора итератора в javascript?

Question

Скажет, у меня есть дерево, что-то вроде следующего, в 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:[]}, 
        ]}, 
       ]}; 

И я хочу сделать обход на него, я мог бы сделать это следующим образом:

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+"'"); 
}); 

, который дает ожидаемый выход:

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

Теперь предположим, что я хочу сделать то же самое, что и генератор ES6. Я думал, что будет выглядеть следующим образом:

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+"'"); 
} 

Но очевидно, что это незаконно: Uncaught SyntaxError: Unexpected strict mode reserved word на yield.

Разочарование! Есть ли какой-то синтаксис, который мне не хватает? Какой самый чистый способ сделать генератор, выражающий этот алгоритм? Возможно, используя некоторую вспомогательную библиотеку?

Я знаю, что можешь использовать явный стек следующим образом, но это не является удовлетворительным по нескольким причинам: (1) логика затемняются до точки, где нет никакого читаемости преимущества использования генератора; может также вернуться обратно к версии с рекурсивным обратным вызовом и (2) это не совсем тот же алгоритм, поскольку он выполняет итерацию назад над каждым узлом. В частности, это означает, что он не будет работать , если node.children - это другой тип итерации, возможно, от другого генератора.

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+"'"); 
} 

Чтобы было ясно: я не заинтересован в качестве помощника специального назначения, который скрывает ужасные подробности о реализации обхода явного стека. Я хочу знать, есть ли способ написать алгоритмы генератора итераторов, даже если они оказались рекурсивными.

Answer 1

Это действительно предусмотрено для оператора yield*. По сути, вам нужно подумать об этом, поскольку один генератор делегирует свои функции другому. (. В самом деле, вы можете делегировать любую итерацию значения)

Например, вы могли бы сделать это:

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

Это даст 1, 2, 3 и 4, потому что yield* работает итератор и дает все значений этого итератора в свою очередь. Точно такое же поведение происходит, если вы передаете генератор.

В вашем случае, если вы хотите сделать recurse генератор, а затем вызвать его с 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+"'"); 
} 

Answer 2

Проблема заключается в том, что ваша recurse функция, в которой вы пытаетесь использовать yield, не объявлен генератор. Вот почему вы получаете синтаксическую ошибку.Он должен был бы быть

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

или просто

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