Как сложить n-арное дерево в C#

Question

Я хотел бы сделать сгиб по n-арным структурам данных Tree. (сложный агрегат в Линке)
Мне удалось придумать рабочее решение:

public static R Aggregate<T, R>(T node,
          Func<T, IEnumerable<T>> getChildren,
       Func<T, IEnumerable<R>, R> aggregator)
{
    var childResults = getChildren(node)
                      .Select(c => Aggregate(c, getChildren, aggregator));

    return aggregator(node, childResults);
}

getChildren является функцией, определяющей, как получить дочерние элементы данного узла. Он должен возвращать пустой IEnumerable для конечных узлов.
aggregator определяет, как обрабатывать узел, используя текущий узел и результаты его дочерних узлов.

Решение, кажется, работает, но имеет некоторые проблемы:

• Алгоритм рекурсивен, он взорвёт стек для глубоких деревьев.
  Как я могу переписать функцию, чтобы предотвратить переполнение стека?

• Алгоритм ленив, но только отчасти.
  например, если aggregator использует только Enumerable.First Результатом дочерних узлов является только самая левая ветвь дерева. Однако с Enumerable.Last все дерево пройдено, хотя для вычисления требуется только самая правая ветвь.
  Как я могу сделать алгоритм действительно ленивым?

Решения F# приветствуются, но C# предпочтительнее.

Answer 1

Вы можете обходить дерево, используя явный стек, а не рекурсию, чтобы избежать использования стекового пространства:

public static IEnumerable<T> Traverse<T>(
    this IEnumerable<T> source
    , Func<T, IEnumerable<T>> childrenSelector)
{
    var stack = new Stack<T>(source);
    while (stack.Any())
    {
        var next = stack.Pop();
        yield return next;
        foreach (var child in childrenSelector(next))
            stack.Push(child);
    }
}

Если вы хотите затем перейти назад, вы можете просто настроить дочерний селектор при вызове, а не вызывать Last вместо First:

Traverse(root, node => nodes.Reverse());

Answer 2

• Вы тратите память при обходе деревьев, если хотите сохранить стек, вместо того, чтобы сначала переключаться на глубину, либо на какую-то технику обхода дерева, соответствующую вашим точным требованиям.

• Что касается того, чтобы сделать его "правильно" ленивым, отцепите агрегатор от обхода. Просто сначала создайте ленивый обход (в любом порядке) и передайте его своему агрегатору.

Кроме того, не очень уверен в выборе интерфейса в связи с вашими заботами о лени. Enumerable.First vs Enumerable.Last даст разные результаты для одного и того же дерева в зависимости от смены провайдера (getChildren), так зачем думать о лени? Так что я думаю, что схема упорядочения / обхода (даже глубина сначала зависит от ширины сначала) должна быть присуща вашему агрегатору или фиксирована для типа дерева? не внешний параметр?