Apply function repeatedly to its result

Question

Do .NET or LINQ offer any standard methods to apply a function repeatedly to itself until the result fulfils a termination criterion and that returns an IEnumerable of all results?

For example, suppose you have a tree and want to find the path from a node to the root: then the function is "get parent of node n" and the termination criterion is "node is root".

Here is a small example with integer values where the function is "return halfed value" and termination criterion is "value is 0":

static void Main(string[] args)
{
    int val = 4321;
    List<int> pathToRoot = new List<int>{val};
    for (;;)
    {
        val = GetParent(val);
        if (val == 0)
        {
            break;
        }
        pathToRoot.Add(val);
    }
    // Prints: 4321,2160,1080,540,270,135,67,33,16,8,4,2,1
    Console.WriteLine(string.Join(",", pathToRoot));
}

private static int GetParent(int child)
{
    return child / 2;
}

I want to replace the for loop by a standard .NET or LINQ method. If I had to write that function myself, it would look like this:

public static class Generator
{
    public static IEnumerable<T> ApplyRepeatedly<T>(T seed,
        Func<T, T> func, Func<T, bool> predicate)
    {
        yield return seed;
        for (;;)
        {
            seed = func(seed);
            if (predicate(seed))
            {
                yield break;
            }
            yield return seed;
        }
    }

And you would use it like this:

IEnumerable<int> pathToRoot = Generator.ApplyRepeatedly(
    4321, GetParent, i => i == 0);

Since I do not want to reinvent the wheel, my question is: do .NET or LINQ already offer something like ApplyRepeatedly<T>()?

See also [this question](http://stackoverflow.com/questions/4814242/linq-recursion-function) with similar requirements. It has answers which may help. — Andy Nichols, Jun 12 '14 at 10:39

score 0 · Answer 1 · answered Jun 12 '14 at 10:29

There's nothing in System.Linq but F# has seq.unfold so you could use that:

var uf = FSharpFunc<int, FSharpOption<Tuple<int, int>>>.FromConverter(i =>
        {
            if (i == 0) return FSharpOption<Tuple<int, int>>.None;
            else return FSharpOption<Tuple<int, int>>.Some(Tuple.Create(i, i / 2));
        });

IEnumerable<int> pathToRoot = SeqModule.Unfold(uf, 4321);

Apply function repeatedly to its result

1 Answers1