Linq statement for an infinite sequence of successive halves

Question

Given a starting number, imagine an infinite sequence of its successive halves.

1, 0.5, 0.25, 0.125, ...

(Ignore any numerical instabilities inherent in double.)

Can this be done in a single expression without writing any custom extension methods or generator methods?

Answer 1

I don't know of a single-expression way but I found this clever generator code here: http://csharpindepth.com/articles/Chapter11/StreamingAndIterators.aspx

public static IEnumerable<TSource> Generate<TSource>(TSource start,
                                                  Func<TSource,TSource> step)
{
   TSource current = start;
   while (true)
   {
       yield return current;
       current = step(current);
   }
}

In your case you'd use it:

foreach (double d in Generate<double>(1, c => c / 2))
{
    ...
}

Answer 2

For fun, here's a trick to create a real infinite sequence in a single expression. The first two definitions are class fields, so that they do not require an expression to be initialised.

double? helper;
IEnumerable<double> infinite;

infinite = new object[] { null }.SelectMany(dummy => new double[] { (helper = (helper / 2) ?? 1).Value }.Concat(infinite));

Answer 3

Here is an answer similar to the one @hvd provided, but using the Y operator defined here, this removes the need for the local variables:

public static Func<A, R> Y<A, R>(Func<Func<A, R>, Func<A, R>> f)
{
    return t => f(Y(f))(t);
}

var halves = Y<double, IEnumerable<double>>(self => d => new[] { 0d }.SelectMany(_ => new[] { d }.Concat(self(d / 2))));

An example use would be:

foreach (var half in halves(20))
    Console.WriteLine(half);

Which would output 20, 10, 5, 2.5 etc...

I wouldn't advise using this in production code but it is fun.

The Y operator also allows other recursive lambda expressions, e.g:

var fibonacci = Y<int, int>(self => n => n > 1 ? self(n - 1) + self(n - 2) : n);
var factorial = Y<int, int>(self => n => n > 1 ? n * self(n - 1) : n);
var hanoi = Y<int, int>(self => n => n == 1 ? 1 : 2 * self(n - 1) + 1);

Answer 4

Enumerable.Repeat(1, int.MaxValue).Select((x, i) => x / Math.Pow(2, i))

It isn't actually infinite, but as both Repeat and Select use deferred execution, you won't lose any performance.

Don't know any native way to create infinite linq expression.

Or you can manually write infinite version of .Repeat

Answer 5

I don't know of any way to make an infinite sequence with straight LINQ. But you could make a very long sequence.

var sequence = Enumerable.Range(0, int.MaxValue)
                         .Select(n => Math.Pow(2, -n));

However, since double has finite precision, you'll get nothing but zeroes after n gets too high.