Is it possible to implement an infinite IEnumerable without using yield with only C# code?

Question

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

1. You can't use the yield keyword directly
2. Use only C# itself directly - no IL code, no constructing dynamic assemblies etc.
3. 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.
4. 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 :)

• svick: Rule 4 doesn't make any sense to me. You're basically asking "is there something in the .Net library I can abuse to do this?"
• svick: I'm curious, how would you do this if you had tail call optimization? Your current implementation doesn't seem tail recursive to me.
• sloth: do this due to the CLR's lack of tail recursion optimization. The CLR does not lack tail call optimization. It's the C# compiler that lacks support for it. It's even explained in the question you linked.
• Phoshi: Why are you doing this? If something has no practical purpose and only serves to obfuscate the meaning of the code, it might be a better fit for codegolf ;)
• KChaloux: SelectMany, along with almost every Linq query, uses yield in its implementation. That's what it's there for. If you don't want to use it, you're probably going to have to disregard Linq altogether. Unless your restrictions are "I can't write out the yield myself, but I can use other things that use it". Which would be a weird set of restrictions.

Answer 1

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();

• sinelaw: thanks - that does it. "I think there might not be" was more of a guess than an assertion, and you proved it wrong.
• sinelaw: By the way, I still think that using the basic LINQ primitives it isn't possible exactly because the compiler limitation on tail call optimizations - any composition of the basic linq primitives that would result in an infinite sequence would hit a stack overflow
• svick: @sinelaw I still don't see how the tail call optimization would help with that, it's not something that magically fixes all stack overflows.
• ta.speot.is: Won't this answer run out of memory fairly quickly? BlockingCollection is new to me, but as best I can tell it's a collection: msdn.microsoft.com/en-us/library/dd267312.aspx
• ta.speot.is: Then this is an elegant solution.

Answer 2

Sure. IEnumerable is basically just a call to IEnumerator. Implement an IEnumerator where the MoveNext function just sets an internal value to a random value, and Current returns that random value.

Answer 3

Following, and similar, functions have logarithmic stack growth, and for any practical purposes can be thought as not causing stack overflows:

public static partial class Extensions
{
 public static IEnumerable<T> Infinite<T>(this IEnumerable<T> source) =>
 source.Concat(new[] { source.Concat(source) }.SelectMany(Infinite));
}

Answer 4

Here is a practically infinite iterator:

using System;
using System.Linq;
public class Test
{
 public static void Main()
 {
 var infiniteIterator =
 Enumerable.Range(Int32.MinValue, Int32.MaxValue)
 .SelectMany(i => Enumerable.Range(Int32.MinValue, Int32.MaxValue))
 .SelectMany(i => Enumerable.Range(Int32.MinValue, Int32.MaxValue))
 .SelectMany(i => Enumerable.Range(Int32.MinValue, Int32.MaxValue))
 .Select(i => default(int));
 foreach (var infinite in infiniteIterator)
 Console.WriteLine(infinite);
 }
}

• sinelaw: For all practical purposes, it is. You could go even further by composing SelectMany in a loop. But it will never be infinite.
• sinelaw: I'm beginning to think the answer is "no, it isn't possible due to lack of tail recursion optimization and the way the compiler handles IEnumerable"
• Den: Enumerable.Range is implemented using yield.
• Servy: This sequence has 17179869184 items in it. That is not infinite.
• ta.speot.is: @Den That's not incorrect but it doesn't matter: You can't use the yield keyword directly