Deferred execution again: Local instance of Random inside LINQ query/queries

I wish to understand the following behaviour I stumbled across today. This small program showcases the "problem":

class Bar
{
  public int ID { get; set; }
}

class Foo
{
  public Bar Bar { get; set; }
}

class Program
{
  private static IEnumerable<Bar> bars;
  private static IEnumerable<Foo> foos;

  static void Main(string[] args)
  {
    Random rng = new Random();
    bars = Enumerable.Range(1, 5).Select(i => new Bar { ID = i });
    foos = Enumerable.Range(1, 10).Select(i => new Foo
    {
      Bar = bars.First(b => b.ID == rng.Next(5) + 1)
    });
    var result = foos.ToList();
  }
}

This code does not work; it throws an InvalidOperationException saying "sequence does not contain a matching element".

However, once I calculate the random integer beforehand, it does work as expected:

var f = new List<Foo>();
for (int i = 0; i <= 20; i++)
{
  int r = rng.Next(5) + 1;
  f.Add(new Foo
  {
    Bar = bars.First(b => b.ID == r)
  });
}
foos = f;

As the title states, I suspect deferred execution to be the reason for this. But I'd be glad if anyone could pinpoint the problem with the first code and explain the exact reason behind this.

(Anecdote: rng.Next(1) + 1 does work, but I guess that the compiler is smart enough to replace this with the constant 1.)

Jon Skeet
people
quotationmark

The problem is that you're testing against different IDs each time you evaluate the predicate.

You don't need foos at all for this. You can just have:

var bar = bars.First(b => b.ID == rng.Next(5) + 1);

That will execute the predicate up to 5 times - one per element of bar - generating a new ID to test against each time. In other words, it's something like this:

public Bar FindRandomBarBroken(IEnumerable<Bar> bars, Random rng)
{
    foreach (var bar in bars)
    {
        if (bar.ID == rng.Next(bar.Count) + 1)
        {
            return bar;
        }
    }
    throw new Exception("I didn't get lucky");
}

Whereas you want something like:

public Bar FindRandomBarFixed(IEnumerable<Bar> bars, Random rng)
{
    // Only generate a single number!
    int targetId = rng.Next(bar.Count) + 1;
    foreach (var bar in bars)
    {
        if (bar.ID == targetId)
        {
            return bar;
        }
    }
    throw new Exception("Odd - expected there to be a match...");
}

You can fix this using another Select call to generate the random ID:

foos = Enumerable.Range(1, 10)
                 .Select(_ => rng.Next(5) + 1)
                 .Select(id => new Foo { Bar = bars.First(b => b.ID == id) } );

Note that you may well now get multiple Bar instances with the same ID, due to the lazy evaluation of bars - you probably want a ToList() call at the end of the assignment to bars.

people

See more on this question at Stackoverflow