C# LINQ – Implementing Infinite IEnumerable Without Using Yield

\clrclinq

Motivation

The main idea is to explore and understand the limits of how far one can go with the basic LINQ primitives (Select, SelectMany, Concat, etc.). These primitives can all be considered functional operations on a theoretical sequence type. Taking examples from Haskell:

Select 'lifts' a function into the sequence (like fmap in Haskell)
Concat is composition
Aggregate is the sequence type's catamorphism (fold)
SelectMany 'extracts' information from the sequence (the Monad bind, >>= operation)
etc. (and I'm sure there are better abstractions for the above)

So the question is whether or not the basic sequence (Enumerable) operations in C# are enough to construct an infinite sequence. More concretely it is the following problem:

Problem

I'm curious to know if there's a way to implement something equivalent to the following, but without using yield:

IEnumerable<T> Infinite<T>()
{
    while (true) { yield return default(T); }
}

Is it possible to do sue using the built-in LINQ operators only?

The short answer is that theoretically yes, but practically not because of how Linq is implemented (causing stack overflows).

That's why here are less restrictive rules:

Rules

Alternatively a less restrictive question would go by the rules

You can't use the yield keyword directly
Use only C# itself directly – no IL code, no constructing dynamic assemblies etc.
You can only use the basic .NET lib (only mscorlib.dll, System.Core.dll? not sure what else to include). However if you find a solution with some of the other .NET assemblies (WPF?!), I'm also interested.
Don't implement IEnumerable or IEnumerator.

Notes

An example theoretically correct definition is:

IEnumerable<int> infinite = null;
infinite = new int[1].SelectMany(x => new int[1].Concat(infinite));

This is "correct" but hits a StackOverflowException after 14399 iterations through the enumerable (not quite infinite).

I'm thinking there might be no way to do this due to the C#'s compiler lack of tail recursion optimization. A proof would be nice 🙂

Best Answer

Even if your assertion was true, proving it would be infeasible, because the proof would have to go through all implementations of IEnumerable in the framework and prove for each one of those that it can't be infinite.

And your assertion actually isn't true, there is at least one implementation of IEnumerable in the framework that can be infinite: BlockingCollection.GetConsumingEnumerable():

What you would do is to create a bounded BlockingCollection that's filled in an infinite loop from a separate thread. Calling GetConsumingEnumerable() will then return an infinite IEnumerable:

var source = new BlockingCollection<int>(boundedCapacity: 1);
Task.Run(() => { while (true) source.Add(1); });
return source.GetConsumingEnumerable();

Related Solutions

C# – suggest structure for classes that maps to json with dynamic data without using dynamic or object reference

If I'm understanding you correctly, you're trying to find a statically-typed way to say "a value of type Section can be either a value of type Highlights, Chart, or Tweets". There are many terms for this, including tagged union, discriminated union, variant, or sum type but they all refer to the same concept. Sum types are a standard feature in statically-typed functional programming languages, but with a bit of ingenuity you can roll your own in C#. Using that answer as a template, and adding sealed to make sure no one adds any extra subclasses, your Section type would look something like this:

public abstract class Section
{
    // Prevent subclassing outside of this scope
    private Section() {}

    // Subclass implementation calls the appropriate function.
    public abstract R Match<R>(Func<H, R> IfHighlight, Func<C, R> IfChart, Func<T, R> IfTweet);

    // Convenience wrapper for when the caller doesn't want to return a value
    // from the match expression.
    public sealed void Match(Action<H> IfHighlight, Action<C> IfChart, Action<T> IfTweet)
    {
        this.Match<int>(
            IfHighlight: Section => { IfHighlight(Section); return 0; },
            IfChart: Section => { IfChart(Section); return 0; },
            IfTweet: Section => { IfTweet(Section); return 0; }
        );
    }

    // From here on down, you define your specific types as usual, and override Match to call
    // the correct function

    public sealed class Highlight : Section
    {
        // Implementation goes here

        public override R Match<R>(Func<H, R> IfHighlight, Func<C, R> IfChart, Func<T, R> IfTweet)
        {
            return IfHighlight(this);
        }
    }

    public class Chart : Section
    {
        // Implementation goes here

        public override R Match<R>(Func<H, R> IfHighlight, Func<C, R> IfChart, Func<T, R> IfTweet)
        {
            return IfChart(this);
        }
    }

    public class Tweet : Section
    {
        // Implementation goes here

        public override R Match<R>(Func<H, R> IfHighlight, Func<C, R> IfChart, Func<T, R> IfTweet)
        {
            return IfTweet(this);
        }
    }
}

With that in place, you can declare variables of type Section, and act on them by passing 3 functions to the Match methods:

Section section = deserializeJson()
section.Match(
    IfHighlight: highlight => /* code to use if you get a Highlight */
    IfChart: chart => /* ... */
    IfTweet: tweet => /* ... */
);

You could just as easily have a collection of Sections and operate on them that way when you iterate over it.

C# IEnumerator – Implementing IEnumerator Without Using ‘yield return’

MoveNext() is a method that is called over and over and every time it has to move to the next item. This means you can't implement it by simply using a for loop (unless you use yield return, which is pretty much the reason why yield return exists), you need to rewrite it so that each MoveNext() call executes just part of that loop.

Specifically, it would look like this:

class Enumerator : IEnumerator<int>
{
    private int i = -1;
    private ImplementList list;

    public Enumerator(ImplementList list)
    {
        this.list = list;
    }

    public bool MoveNext()
    {
        i++;
        return i < list.myList.Count;
    }

    public int Current { get { return list.myList[i]; } }

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

    public void Dispose() {}

    public void Reset() { throw new NotSupportedException(); }
}

This way, every call to MoveNext() performs the i++ and i < list.Count parts of the for loop.