Why does this fail when I don't use the ToList method in a for loop?

Question

I am wondering why if I change the line

"sub = sub.SelectMany(x => x.Next(i)).ToList();" 

to

"sub = sub.SelectMany(x => x.Next(i));"  

I get the error

Line 48: System.IndexOutOfRangeException: Index was outside the bounds of the array" when I provide an input of 4 to the method SolveNQueens.

I believe it may have something to do with lazy evaluation.

The full code sample is listed below and is a valid solution to the n queens problem.

  public class Solution {
        public IList<IList<string>> SolveNQueens(int n) 
        {
            IEnumerable<PartialQueens> sub = new List<PartialQueens>(){
                new PartialQueens(n)};

            for(int i=0;i<n;i++)
            {
                sub = sub.SelectMany(x => x.Next(i)).ToList(); 
            }

           return sub.Select(x => x.ToPosition()).ToList();
        }
    }

   public class PartialQueens
    {
    public byte FREE   = 0;
    public byte BLOCKED = 1;
    public byte QUEEN    = 2; 

    public byte[,] fill;
    int n;

    public PartialQueens(int n)
    {
        this.n = n;
        fill = new byte[n,n];
    }

    public PartialQueens(byte[,] fill, int n)
    {
        this.fill = fill;
        this.n    = n;
    }

    public PartialQueens Fill(int row, int column)
    {
        byte[,] newFill = fill.Clone() as byte[,];

        newFill[row,column] = QUEEN;

        Action<int,int> f = (x,y) => 
        {
            if(y >= 0 && y < n)
                newFill[x,y] = BLOCKED;
        };

        for(int i=1;i<n-row;i++)
        {
            f(row+i,column+i);
            f(row+i,column-i);
            f(row+i,column);
        }

        return new PartialQueens(newFill,n);
    }

    public IEnumerable<PartialQueens> Next(int row)
    { 
        for(int j=0;j<n;j++)
        {            
            if(fill[row,j] == FREE)
                yield return Fill(row,j);
        }
    }  

    public IList<string> ToPosition()
    {
        return Enumerable.Range(0,n).Select(i => ConvertRow(i)).ToList();
    }

    public string ConvertRow(int i)
    {
        StringBuilder builder = new StringBuilder();

        for(int j=0;j<n;j++)
        {
            if(fill[i,j] == QUEEN)
                builder.Append("Q");
            else
                builder.Append(".");
        }

        return builder.ToString();
    }
}

Answer 1

The reason this fails is because of the way that the iterator variable used in a for loop is evaluated when it is captured by a closure. When you remove the ToList() inside the loop, the sub IEnumerable is only evaluated when sub is materialized in the return statement return sub.Select(x => x.ToPosition()).ToList();. At this time, the for loop variable i will have a value of n (e.g. 8 on a standard chess board), which is outside the array bounds.

However, when you materialize the List immediately, the side effect isn't encountered, since the value of i is used before the next iteration (ToList materializes).

Works:

for (int i = 0; i < n; i++)
{
    // Materialized here so `i` evaluated immediately
    sub = sub.SelectMany(x => x.Next(i)).ToList(); 
}

Broken:

for (int i = 0; i < n; i++)
{
    sub = sub.SelectMany(x => x.Next(i));
}
return sub.Select(x => x.ToPosition()).ToList(); // `i` evaluated here

To fix the for loop variable evaluation issue, you can explicitly capture the current value of the iterator variable:

for (int i = 0; i < n; i++)
{
    var loop = i;
    sub = sub.SelectMany(x => x.Next(loop)); // No To List - lazy evaluation
}

Re : Avoiding for loops in FP Paradigm code

OP's SolveNQueens method uses a loop which progressively changes the sub, rather than recursion, but the for can also be replaced with a foreach and a range:

foreach(var i in Enumerable.Range(0, n))
{
    sub = sub.SelectMany(x => x.Next(i));
}

Which Resharper then offers to re-write as a left fold:

sub = Enumerable.Range(0, n)
    .Aggregate(sub, (current, i) => current.SelectMany(x => x.Next(i)));

Either way, the flaw in lazy evaluation of the iterator variable inside a for loop is avoided.