NonRecursive Equivalent of Lazy Recursive Functions

Question

Consider the following code implementing a depth first search on a Rose Tree:

public class RoseTree<T>
{
    public T Value;
    public IEnumerable<Lazy<RoseTree<T>> Children;

    public IEnumerable<T> Flatten()
    {
        yield return Value;
        foreach (var childValue in Children.SelectMany(t => t.Value.Flatten()))
            yield return childValue;
    }
}

I was struggling to come up with an equivalent non-recursive equivalent. In particular, though a strict non-recursive, quasi-equivalent function is easy to come by, e.g:

public IEnumerable<T> FlattenIteratively()
{
    var roseTreeQueue = new Stack<RoseTree<T>>();
    var values = new Queue<T>();
    roseTreeQueue.Push(this);

    while (roseTreeQueue.Any())
    {
        var top = roseTreeQueue.Pop();
        values.Enqueue(top.Value);

        foreach (var child in top.Children.Reverse())
            roseTreeQueue.Push(child.Value);
    }

    return values;
}

While this yields the same result as Flatten for finite trees with defined values, it fails for infinite trees or for trees with undefined values. Does anyone see a way of writing a non-recursive method for traversing this structure with the same characteristics as the recursive method.

Note: given C#'s rewriting of yield return functions, calling the first method recursive is somewhat misleading. If anyone has a more precise term, I'd be happy to have it.

score 1 · Answer 1 · edited May 23 '17 at 11:51

A general lazy iterative tree traversal function taken from How to flatten tree via LINQ?

public static class TreeHelper
{
    public static IEnumerable<T> Expand<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> elementSelector)
    {
        var stack = new Stack<IEnumerator<T>>();
        var e = source.GetEnumerator();
        try
        {
            while (true)
            {
                while (e.MoveNext())
                {
                    var item = e.Current;
                    yield return item;
                    var elements = elementSelector(item);
                    if (elements == null) continue;
                    stack.Push(e);
                    e = elements.GetEnumerator();
                }
                if (stack.Count == 0) break;
                e.Dispose();
                e = stack.Pop();
            }
        }
        finally
        {
            e.Dispose();
            while (stack.Count != 0) stack.Pop().Dispose();
        }
    }
}

In your case it can be used as follows

public class RoseTree<T>
{
    public T Value;
    public IEnumerable<Lazy<RoseTree<T>>> Children;
    public IEnumerable<T> Flatten()
    {
        return Enumerable.Repeat(this, 1)
            .Expand(item => item.Children != null ? item.Children.Select(c => c.Value) : null)
            .Select(item => item.Value);
    }
}

score 0 · Answer 2 · answered Nov 17 '15 at 21:44

We can solve this by turning the FlattenIterative method explicitly into an IEnumerator<T>. We define:

public class RoseTreeEnumerator<T> : IEnumerator<T>, IEnumerable<T>
{
    public RoseTree<T> OriginalTree { get; private set; }

    private Stack<Lazy<RoseTree<T>>> TreeQueue { get; set; }

    private RoseTree<T> CurrentRoseTree { get; set; }


    public RoseTreeEnumerator(RoseTree<T> tree)
    {
        OriginalTree = tree;
        TreeQueue = new Stack<Lazy<RoseTree<T>>>();
        TreeQueue.Push(new Lazy<RoseTree<T>>(() => tree));
        CurrentRoseTree = null;
    }  

    #region IEnumerator<T> Members

    public T Current
    {
        get { return CurrentRoseTree.Value; }
    }

    public void Dispose()
    {
    }

    #endregion

    #region IEnumerator Members

    object System.Collections.IEnumerator.Current
    {
        get { return Current; }
    }

    public bool MoveNext()
    {
        if (TreeQueue.Any())
        {
            CurrentRoseTree = TreeQueue.Pop().Value;
            foreach (var tree in CurrentRoseTree.Children.Reverse())
            {
                TreeQueue.Push(tree);
            }
            return true;
        }
        else
        {
            return false;
        }
    }

    public void Reset()
    {
        TreeQueue.Clear();
        CurrentRoseTree = null;
        TreeQueue.Push(new Lazy<RoseTree<T>>(() => OriginalTree));
    }

    #endregion

    #region IEnumerable<T> Members

    public IEnumerator<T> GetEnumerator()
    {
        return this;
    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        return this;
    }
    #endregion
}

and then can define

public IEnumerable<T> FlattenPrime()
{
    return new RoseTreeEnumerator<T>(this);
}

NonRecursive Equivalent of Lazy Recursive Functions

2 Answers2