列表中的for循环

Question

人们经常使用

for i in [0 .. 10] do something

但是 afaik 创建了一个列表，然后对其进行迭代，在我看来使用

更有意义

for i = 0 to 10 do something

没有创建不必要的列表但具有相同的行为。我错过了什么吗？（我猜是这样的）

Answer 1

你是对的，写 for i in [0 .. 10] do something 会生成一个列表，它确实有很大的开销。尽管您也可以省略方括号，在这种情况下它只会构建一个惰性序列（而且，事实证明编译器甚至优化了这种情况）。我通常更喜欢写 in 0 .. 100 do，因为它看起来与迭代序列的代码相同。

利用F#交互的#time特性做一个简单的分析：

for i in [ 0 .. 10000000 ] do // 3194ms (yikes!)
  last <- i

for i in 0 .. 10000000 do     // 3ms
  last <- i

for i = 0 to 10000000 do      // 3ms
  last <- i

for i in seq { 0 .. 10000000 } do // 709ms (smaller yikes!)
  last <- i

因此，事实证明编译器实际上将 in 0 .. 10000000 do 优化为与 0 to 10000000 do 循环相同的东西。您可以强制它显式创建惰性序列（最后一种情况），这比列表快，但仍然很慢。

Answer 2

前一种形式需要语言中的特殊构造（对于 var from ... to ... by），这是古代编程语言遵循的方式:

'do' Fortran 中的循环
对于 var:= expr 到 Pascal 中的 expr
等等

后一种形式（对于 var in something）更为通用。它适用于普通列表，但也适用于生成器（如 python）等。在运行列表之前可能不需要构建完整列表。这允许在潜在的无限列表上编写循环。

无论如何，一个体面的compiler/interpreter应该能识别出比较频繁的特例[expr1..expr2]，避免中间列表的计算和存储。

Answer 3

给出一个有点不同的答案，但希望对某些人感兴趣

您是正确的，因为 F# 编译器在这种情况下无法应用快速循环优化。好消息，F# 编译器是开源的，我们可以改进它的行为。

这是我的免费赠品：

快速循环优化发生在 tastops.fs。目前还比较原始，这是我们改进的好机会。

// Detect the compiled or optimized form of a 'for <elemVar> in <startExpr> .. <finishExpr>  do <bodyExpr>' expression over integers
// Detect the compiled or optimized form of a 'for <elemVar> in <startExpr> .. <step> .. <finishExpr>  do <bodyExpr>' expression over integers when step is positive
let (|CompiledInt32ForEachExprWithKnownStep|_|) g expr = 
    match expr with 
    | Let (_enumerableVar, RangeInt32Step g (startExpr, step, finishExpr), _, 
           Let (_enumeratorVar, _getEnumExpr, spBind,
              TryFinally (WhileLoopForCompiledForEachExpr (_guardExpr, Let (elemVar,_currentExpr,_,bodyExpr), m), _cleanupExpr))) -> 

        let spForLoop = match spBind with SequencePointAtBinding(spStart) -> SequencePointAtForLoop(spStart) |  _ -> NoSequencePointAtForLoop 

        Some(spForLoop,elemVar,startExpr,step,finishExpr,bodyExpr,m)
    | _ -> 
        None

let DetectFastIntegerForLoops g expr = 
    match expr with 
    | CompiledInt32ForEachExprWithKnownStep g (spForLoop,elemVar,startExpr,step,finishExpr,bodyExpr,m) 
         // fast for loops only allow steps 1 and -1 steps at the moment
         when step = 1 || step = -1 -> 
            mkFastForLoop  g (spForLoop,m,elemVar,startExpr,(step = 1),finishExpr,bodyExpr)
    | _ -> expr

这里的问题是 RangeInt32Step 只检测像 0..10 和 0..1..10 这样的模式。它错过了例如 [0..10]

让我们介绍另一个匹配这些表达式的活动模式SeqRangeInt32Step：

let (|SeqRangeInt32Step|_|) g expr =
    match expr with
    // detect '[n .. m]'
    | Expr.App(Expr.Val(toList,_,_),_,[TType_var _],
                [Expr.App(Expr.Val(seq,_,_),_,[TType_var _],
                          [Expr.Op(TOp.Coerce, [TType_app (seqT, [TType_var _]); TType_var _],
                                    [RangeInt32Step g (startExpr, step, finishExpr)], _)],_)],_)
        when
            valRefEq g toList (ValRefForIntrinsic g.seq_to_list_info) &&
            valRefEq g seq g.seq_vref &&
            tyconRefEq g seqT g.seq_tcr ->
            Some(startExpr, step, finishExpr)

    | _ -> None

你怎么知道这是你需要模式匹配的？我经常采用的方法是，我编写一个具有正确属性的简单 F# 程序，并在编译期间放置一个断点以检查表达式。从中我创建了匹配的模式：

让我们把这两个模式放在一起：

let (|ExtractInt32Range|_|) g expr =
  match expr with
  | RangeInt32Step g range -> Some range
  | SeqRangeInt32Step g range -> Some range
  | _ -> None

CompiledInt32ForEachExprWithKnownStep 更新为使用 ExtractInt32Range 而不是 RangeInt32Step

完整的解决方案是这样的：

let (|SeqRangeInt32Step|_|) g expr =
    match expr with
    // detect '[n .. m]'
    | Expr.App(Expr.Val(toList,_,_),_,[TType_var _],
                [Expr.App(Expr.Val(seq,_,_),_,[TType_var _],
                          [Expr.Op(TOp.Coerce, [TType_app (seqT, [TType_var _]); TType_var _],
                                    [RangeInt32Step g (startExpr, step, finishExpr)], _)],_)],_)
        when
            valRefEq g toList (ValRefForIntrinsic g.seq_to_list_info) &&
            valRefEq g seq g.seq_vref &&
            tyconRefEq g seqT g.seq_tcr ->
            Some(startExpr, step, finishExpr)

    | _ -> None

let (|ExtractInt32Range|_|) g expr =
  match expr with
  | RangeInt32Step g range -> Some range
  | SeqRangeInt32Step g range -> Some range
  | _ -> None

// Detect the compiled or optimized form of a 'for <elemVar> in <startExpr> .. <finishExpr>  do <bodyExpr>' expression over integers
// Detect the compiled or optimized form of a 'for <elemVar> in <startExpr> .. <step> .. <finishExpr>  do <bodyExpr>' expression over integers when step is positive
let (|CompiledInt32ForEachExprWithKnownStep|_|) g expr = 
    match expr with 
    | Let (_enumerableVar, ExtractInt32Range g (startExpr, step, finishExpr), _,
           Let (_enumeratorVar, _getEnumExpr, spBind,
              TryFinally (WhileLoopForCompiledForEachExpr (_guardExpr, Let (elemVar,_currentExpr,_,bodyExpr), m), _cleanupExpr))) -> 

        let spForLoop = match spBind with SequencePointAtBinding(spStart) -> SequencePointAtForLoop(spStart) |  _ -> NoSequencePointAtForLoop 

        Some(spForLoop,elemVar,startExpr,step,finishExpr,bodyExpr,m)
    | _ -> 
        None

使用简单的测试程序

let print v =
    printfn "%A" v

[<EntryPoint>]
let main argv =
    for x in [0..10] do
        print x

    0

在优化之前，相应的 C# 代码看起来像这样（IL 代码更易于检查，但如果不使用它可能有点难以理解）：

// Test
[EntryPoint]
public static int main(string[] argv)
{
    FSharpList<int> fSharpList = SeqModule.ToList<int>(Operators.CreateSequence<int>(Operators.OperatorIntrinsics.RangeInt32(0, 1, 10)));
    IEnumerator<int> enumerator = ((IEnumerable<int>)fSharpList).GetEnumerator();
    try
    {
        while (enumerator.MoveNext())
        {
            Test.print<int>(enumerator.Current);
        }
    }
    finally
    {
        IDisposable disposable = enumerator as IDisposable;
        if (disposable != null)
        {
            disposable.Dispose();
        }
    }
    return 0;
}

F# 创建一个列表，然后使用枚举器对其进行迭代。难怪它比经典的 for 循环要慢。

应用优化后，我们得到以下代码：

// Test
[EntryPoint]
public static int main(string[] argv)
{
    for (int i = 0; i < 11; i++)
    {
        Test.print<int>(i);
    }
    return 0;
}

显着改善。

所以窃取此代码，post PR 到 https://github.com/Microsoft/visualfsharp/ and bask in glory. Of course you need to add unit tests and emitted IL code tests which can be somewhat tricky to find the right level for, check this commit 以获得灵感

PS。应该也支持 [|0..10|] seq {0..10}

PS。此外 for v in 0L..10L do print v 以及 for v in 0..2..10 do print v 在 F# 中的实现效率也很低。

列表中的for循环

For loop in list

f#

control-flow