Problem with Recursion

Mar 20, 2011 at 6:32 AM

I've been building some recursive select methods for use with Obtics.  It had been going fairly well with the following methods working:

 

IEnumerable<T> SelectRecursive(T source, Func<T,T> selector)
IEnumerable<T> SelectManyRecursive(T source, Func<T,IEnumerable<T>> selector)
IEnumerable<T> SelectManyRecursive(IEnumerable<T> source, Func<T,IEnumerable<T>> selector)

Unfortunately, when I got to the SelectManyRecursiveCyclic method, designed to handle cycles, things fell apart.  I got a Linq expression to do the recursive select many and avoid cycles, but when I tried to make it observable, Obtics overflowed the stack when doing ExpressionObserver.Compile().  It didn't even care what the data was like.

 

 

// [SelectManyRecursive] Works, but doesn't handle cycles.
(IEnumerable<T> s, Func<T, IEnumerable<T>> sel) =>
	s.Concat(s.SelectMany(t => sel(t).Except(s).SelectManyRecursive(sel))));

// [SelectManyRecursiveCyclic] Expression works to handle cycles in plain Linq, but causes stack overflow when setting up with ExpressionObserver.Compile()
(IEnumerable<T> s, Func<T, IEnumerable<T>> sel) =>
	s.SelectMany(sel).Except(s).Transform(t => t.Any() ? s.Concat(t).SelectManyRecursiveCyclic(sel) : s));

I've tried many variations of the expression, all with the same result.  I'm at a bit of a loss as to how to make this recursive cycle-avoiding thing work.  I don't understand why Obtics seems to be creating inifinitely deep chains without even looking at the data.  Any thoughts?  I'm out of ideas at this point. :(

Appreciate any insight you might be able to offer.

 

Coordinator
Mar 21, 2011 at 7:02 PM

If I understood the intention of your SelectManyRecursiveCyclic method correctly, this is how I think I would implement it (not tested):

using System;
using System.Collections.Generic;
using System.Text;
using Obtics.Values;
using Obtics.Collections;

namespace Test2
{
    public static class SomeMethods
    {
        static IValueProvider<IEnumerable<T>> Recurse<T>(Tuple<IEnumerable<T>, IEnumerable<T>> t, Func<Tuple<IEnumerable<T>, IEnumerable<T>>, Tuple<IEnumerable<T>, IEnumerable<T>>> proc)
        {
            var newT = proc(t);
            return newT.Item2.Any().Select( anyNew => anyNew ? Recurse(newT, proc) : ValueProvider.Static(newT.Item1) );
        }

        public static IEnumerable<T> SelectManyRecursiveCyclic<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> select)
        {
            var distinctedSource = source.Distinct();

            return
                Recurse(
                    //Item1 = distinct elements collected sofar, Item2 = elements not traversed yet with select method
                    Tuple.Create(System.Linq.Enumerable.Empty<T>(), distinctedSource),
                    t =>
                    {
                        var sofar = t.Item1.Concat(t.Item2);
                        var newElts = t.Item2.SelectMany(select).Except(sofar);

                        return Tuple.Create(
                            sofar,
                            newElts
                        );
                    }
                )
                .Cascade()
            ;
        }
        
    }
}

When does the observer stack overflow? I can imagine it could do that when actually building a
transformation tree. Note that an "b ? T : F" expression when rewritten may not only follow the 
T or F branch but both. it may build a transformation subtree for the T value provider and a transformation 
subtree for the F value provider. If in that case there is a recursion for either the T or F branch it
will try to build an infinitly large transformation tree.
It would be very iteresting if the CollectionObserver would stack overflow while doing a rewriting. In that 
case, could you send some code that does this?
Mar 21, 2011 at 8:20 PM

I ended up coming up with the dual list approach myself as well later on.  This code worked for me.

[ExpressionObserverMapping(typeof(Observable))]
public static IEnumerable<T> SelectManyRecursiveCyclic<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> selector)
{
    return source.SelectManyUsed(Enumerable.Empty<T>(), selector).Distinct();
}

[ExpressionObserverMapping(typeof(Observable))]
private static IEnumerable<T> SelectManyUsed<T>(this IEnumerable<T> source, IEnumerable<T> used, Func<T, IEnumerable<T>> selector)
{
    return source.Concat(source.SelectMany(t => selector(t).Except(used).SelectManyUsed(used.Concat(new[] { t }), selector)));
}

Here is some code that produces the stack overflow. I don't recall what the nature of the overflow was.

[ExpressionObserverMapping(typeof(Observable))]
public static IEnumerable<T> SelectManyRecursiveCyclic<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> selector)
{
	return source.SelectMany(selector).Except(source).Transform(t => t.Any() ? source.Concat(t).SelectManyRecursiveCyclic(selector) : source);
}

public static class Observable
{
	public static IEnumerable<T> SelectManyRecursiveCyclic<T>(IEnumerable<T> source, Func<T, IEnumerable<T>> selector)
	{
		return ObservableGeneric<T>.SelectManyRecursiveCyclic(source, selector);
	}
}

public static class ObservableGeneric<T>
{
	public static IEnumerable<T> SelectManyRecursiveCyclic(IEnumerable<T> source, Func<T, IEnumerable<T>> selector)
	{
		if (_selectManyRecursiveCyclicFunc == null)
		{
			_selectManyRecursiveCyclicFunc = ExpressionObserver.Compile((IEnumerable<T> s, Func<T, IEnumerable<T>> sel) =>
				s.SelectMany(sel).Except(s).Transform(t => t.Any() ? s.Concat(t).SelectManyRecursiveCyclic(sel) : s));
		}
		return _selectManyRecursiveCyclicFunc(source, selector).Cascade();
	}
	private static Func<IEnumerable<T>, Func<T, IEnumerable<T>>, IValueProvider<IEnumerable<T>>> _selectManyRecursiveCyclicFunc;
}

Coordinator
Mar 24, 2011 at 11:40 AM

Yes, whatever works.

A few small things though; seeing the level you are working at it may be better not to work via ExpressionObserver.Compile. Rewritten expressions will always be eagerly change aware, possibly looking and reserving resources for changes the will never happen. It may be better if you would use ObservableEnumerable methods directly. I gives you direct control over how the transformation tree is built.

In the SelectManyUsed method you do a selector(t).Except(used).SelectManyUsed( .. etc. for every element in the source. Might it not be beter to first collect all new elements (like you actually do in SelectManyRecursiveCyclic) and the do the Except rule etc. on the entire collection of new elements?

Transformation pipelines/tree are not cheap so, if you are working on core methods, it would be best to minimize their size.