F＃Seq

Question

的實現問題我正在深入研究F＃源代碼。

在Seq.fs：

// Binding. 
// 
// We use a type defintion to apply a local dynamic optimization. 
// We automatically right-associate binding, i.e. push the continuations to the right. 
// That is, bindG (bindG G1 cont1) cont2 --> bindG G1 (cont1 o cont2) 
// This makes constructs such as the following linear rather than quadratic: 
// 
// let rec rwalk n = { if n > 0 then 
//       yield! rwalk (n-1) 
//       yield n } 

看到上面的代碼後，我測試兩個代碼：

let rec rwalk n = seq { if n > 0 then 
         yield n 
         yield! rwalk (n-1) 
         } 

和

let rec rwalk n = seq { if n > 0 then 
         yield! rwalk (n-1) 
         yield n 
         } 

我找到的第一個是非常快的，而第二個很慢。如果n = 10000，則在我的機器上花費3秒鐘來生成該序列，因此爲二次時間。

二次時間是合理的，例如，

seq { yield! {1; 2; ...; n-1}; yield n }轉化爲

Seq.append {1; 2; ...; n-1} {n} 

此附加操作應採取線性時間，我猜。在第一個代碼中，附加操作如下所示：seq { yield n; yield! {n-1; n-2; ...; 1} }，這會花費時間不變。

代碼中的註釋說它是linear（也許這個線性不是線性時間）。也許這個linear涉及到使用自定義的實現序列而不是Moand/F＃計算表達式（如F＃規範中所述，但是規範沒有提及這樣做的原因......）。

有人能澄清這裏的模糊嗎？非常感謝！

（PS，因爲這是一個語言的設計和優化的問題，我還附上哈斯克爾標籤，看看那裏的人有見解。）

Answer 1

當yield!出現在非尾調用位置，它essentiall意味着同樣的事情：

for v in <expr> do yield v 

的問題與此（爲什麼是二次的原因）是遞歸調用，這將創建嵌套for循環迭代器的鏈條。您需要遍歷由<expr>生成的每個單元的整個序列，因此如果迭代是線性的，則會得到二次時間（因爲線性迭代發生在每個元素上）。

讓我們假設rwalk函數生成[ 9; 2; 3; 7 ]。在第一次迭代中，遞歸生成的序列有4個元素，所以你需要迭代4個元素並添加1.在遞歸調用中，你需要迭代3個元素並添加1等。使用圖表，你可以怎麼看這就是二次：

x 
x x 
x x x 
x x x x 

此外，每個遞歸調用創建對象（IEnumerator）的新實例，所以也有一些內存成本（雖然只是線性）。

在尾呼位置中，F＃編譯器/庫管理器進行了優化。它用遞歸調用返回的那個「替換」當前的IEnumerable，所以它不需要迭代它以生成所有元素 - 它只是返回（並且這也消除了內存成本）。

相關。在C＃lanaugage設計中已經討論過相同的問題，並且有interesting paper about it（其名稱爲yield!是yield foreach）。

Answer 2

我不確定你要找什麼樣的答案。正如您已經注意到的那樣，註釋與編譯器的行爲不匹配。我不能說這是否是與實現不同步的評論實例，還是實際上是性能缺陷（例如，規範似乎沒有提出任何特定的性能要求）。

但是，編譯器的機器在理論上應該可以生成一個在線性時間內對您的示例進行操作的實現。實際上，甚至可以使用計算表達式在庫中構建這樣的實現。這裏有一個粗略的例子，在紙上托馬斯引用主要是基於：

open System.Collections 
open System.Collections.Generic 

type 'a nestedState = 
/// Nothing to yield 
| Done 
/// Yield a single value before proceeding 
| Val of 'a 
/// Yield the results from a nested iterator before proceeding 
| Enum of (unit -> 'a nestedState) 
/// Yield just the results from a nested iterator 
| Tail of (unit -> 'a nestedState) 

type nestedSeq<'a>(ntor) = 
    let getEnumerator() : IEnumerator<'a> = 
    let stack = ref [ntor] 
    let curr = ref Unchecked.defaultof<'a> 
    let rec moveNext() = 
     match !stack with 
     | [] -> false 
     | e::es as l -> 
      match e() with 
      | Done -> stack := es; moveNext() 
      | Val(a) -> curr := a; true 
      | Enum(e) -> stack := e :: l; moveNext() 
      | Tail(e) -> stack := e :: es; moveNext() 
    { new IEnumerator<'a> with 
     member x.Current = !curr 
     interface System.IDisposable with 
     member x.Dispose() =() 
     interface IEnumerator with 
     member x.MoveNext() = moveNext() 
     member x.Current = box !curr 
     member x.Reset() = failwith "Reset not supported" } 
    member x.NestedEnumerator = ntor 
    interface IEnumerable<'a> with 
    member x.GetEnumerator() = getEnumerator() 
    interface IEnumerable with 
    member x.GetEnumerator() = upcast getEnumerator() 

let getNestedEnumerator : 'a seq -> _ = function 
| :? ('a nestedSeq) as n -> n.NestedEnumerator 
| s -> 
    let e = s.GetEnumerator() 
    fun() -> 
     if e.MoveNext() then 
     Val e.Current 
     else 
     Done 

let states (arr : Lazy<_[]>) = 
    let state = ref -1 
    nestedSeq (fun() -> incr state; arr.Value.[!state]) :> seq<_> 

type SeqBuilder() = 
    member s.Yield(x) = 
    states (lazy [| Val x; Done |]) 
    member s.Combine(x:'a seq, y:'a seq) = 
    states (lazy [| Enum (getNestedEnumerator x); Tail (getNestedEnumerator y) |]) 
    member s.Zero() = 
    states (lazy [| Done |]) 
    member s.Delay(f) = 
    states (lazy [| Tail (f() |> getNestedEnumerator) |]) 
    member s.YieldFrom(x) = x 
    member s.Bind(x:'a seq, f) = 
    let e = x.GetEnumerator() 
    nestedSeq (fun() -> 
       if e.MoveNext() then 
        Enum (f e.Current |> getNestedEnumerator) 
       else 
        Done) :> seq<_> 

let seq = SeqBuilder() 

let rec walkr n = seq { 
    if n > 0 then 
    return! walkr (n-1) 
    return n 
} 

let rec walkl n = seq { 
    if n > 0 then 
    return n 
    return! walkl (n-1) 
} 

let time = 
    let watch = System.Diagnostics.Stopwatch.StartNew() 
    walkr 10000 |> Seq.iter ignore 
    watch.Stop() 
    watch.Elapsed 

注意，我SeqBuilder不穩健;它缺少幾個工作流成員，並且在處理對象或錯誤處理時不做任何事情。但是，它確實證明了SequenceBuilder s不需要需要在類似於您的示例上展示二次運行時間。

另請注意，這裏存在時間空間折衷 - walkr n的嵌套迭代器將在O（n）時間內遍歷序列，但它需要O（n）空間才能完成此操作。