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 (likefmapin Haskell)Concatis compositionAggregateis 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
yieldkeyword 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 🙂
13
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();
8
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.
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));
}
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);
}
}
5