当我不在 for 循环中使用 ToList 方法时，为什么会失败？

Question

我想知道为什么我要更改行

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

到

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

我收到错误

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

我认为这可能与惰性评估有关。

下面列出了完整的代码示例，它是一个有效的解决方案到 n 皇后问题。

  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

失败的原因是 for loop 中使用的迭代器变量在 captured by a closure 时的计算方式。当您删除循环内的 ToList() 时，仅当 sub 在 return 语句 return sub.Select(x => x.ToPosition()).ToList(); 中实现时，才会计算 sub IEnumerable。此时，for 循环变量 i 的值为 n（例如标准棋盘上的 8），该值在数组边界之外。

但是，当您立即具体化 List 时，不会遇到副作用，因为 i 的值在下一次迭代（ToList 具体化）之前使用。

作品：

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

损坏：

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

对于fixfor循环变量求值问题，可以显式捕获迭代器变量的当前值：

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

回复：避免 FP 范式代码中的循环

OP 的 SolveNQueens 方法使用循环逐渐改变 sub，而不是递归，但是 for 也可以用 foreach 和范围替换：

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

然后 Resharper 提出重写为左折：

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

无论哪种方式，都避免了 for 循环中迭代器变量惰性求值的缺陷。

当我不在 for 循环中使用 ToList 方法时，为什么会失败？

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

c#

ienumerable

functional-programming