Linq statement for an infinite sequence of success

问题:

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?

回答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))
{
    ...
}

回答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));

回答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);

回答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

回答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.