避免堆棧溢出（使用F＃無限序列的序列）

Question

我有我爲f＃中morris seq編寫的「學習代碼」，該代碼遭遇堆棧溢出，我不知道如何避免。 「morris」返回無限序列的「see and say」序列（即{{1}，{1,1}，{2,1}，{1,2,1,1}，{1,1,1 ，2,2,1}，{3,1,2,2,1,1}，...}）。

let printList l = 
     Seq.iter (fun n -> printf "%i" n) l 
     printfn "" 

    let rec morris s = 
     let next str = seq { 
      let cnt = ref 1 // Stack overflow is below when enumerating 
      for cur in [|0|] |> Seq.append str |> Seq.windowed 2 do 
       if cur.[0] <> cur.[1] then 
        yield!([!cnt ; cur.[0]]) 
        cnt := 0 
       incr cnt 
     } 
     seq { 
     yield s 
     yield! morris (next s) // tail recursion, no stack overflow 
     } 

    // "main" 
    // Print the nth iteration 
    let _ = [1] |> morris |> Seq.nth 3125 |> printList 

可以摘掉使用Seq.nth第n次迭代，但你只能得到到目前爲止，你打一個堆棧溢出之前。遞歸的一點是尾遞歸，它實質上構建了一組鏈接的枚舉器。這不是問題所在。它是在第4000個序列中調用「枚舉」的時候。請注意，使用F＃1.9.6.16，以前的版本超過14000）。這是因爲鏈接序列被解析的方式。序列是懶惰的，所以「遞歸」是懶惰的。也就是說，seq n調用seq n-1調用seq n-2等等來獲得第一個項目（第一個＃是最差的情況）。

據我所知，[|0|] |> Seq.append str |> Seq.windowed 2正在讓我的問題變得更糟，如果我消除了這個問題，我可以將＃產生的三倍。實際上，代碼工作得很好。 morris的第3125次迭代的長度將超過10^359個字符。

我真的想解決的問題是如何留住懶惰EVAL和有根據的迭代，我可以摘掉堆棧大小沒有限制。我正在尋找適當的F＃成語，以根據內存大小制定限制。

消息：十月'10

學習F＃好一點後，哈斯克爾的一點點，思索&調查這個問題已有一年，我終於可以回答我的問題。但是，一如既往地遇到困難問題，問題始於它是一個錯誤的問題。問題不是序列的序列 - 這是因爲遞歸定義的序列。我的函數式編程技能現在好一點，所以它更容易看到發生了什麼事情與下面的版本，它仍然得到一個計算器

let next str = 
    Seq.append str [0] 
    |> Seq.pairwise 
    |> Seq.scan (fun (n,_) (c,v) -> 
      if (c = v) then (n+1,Seq.empty) 
      else (1,Seq.ofList [n;c])) (1,Seq.empty) 
    |> Seq.collect snd 

let morris = Seq.unfold(fun sq -> Some(sq,next sq)) 

這basicially創建了一個很長的序列處理函數的調用鏈生成sequnces。 F＃附帶的Seq模塊是不能在不使用堆棧的情況下跟隨鏈的。有一個優化用於追加和遞歸定義的序列，但只有當遞歸實現附加時，該優化纔有效。

那麼這將工作

let rec ints n = seq { yield n; yield! ints (n+1) } 
printf "%A" (ints 0 |> Seq.nth 100000);; 

而這一次會得到一個計算器。

let rec ints n = seq { yield n; yield! (ints (n+1)|> Seq.map id) } 
printf "%A" (ints 0 |> Seq.nth 100000);; 

爲了證明F＃libary是問題，我寫了實施追加，成對，掃描和使用continutions收集，現在我可以開始沒有問題產生，並打印出50000 SEQ（我自己的序列模塊因爲長度超過10^5697位，所以永遠不會完成）。

一些其他注意事項：

• 延續是我一直在尋找的成語，但在這種情況下，他們不得不進入F＃庫，而不是我的代碼。我瞭解到的，Tomas Petricek's現實世界的函數式編程書在F＃的延續。
• 我接受的懶惰列表答案持有其他成語;懶惰的評價。在我重寫的庫中，我還必須利用惰性類型來避免堆棧溢出。
• 靠運氣作品的懶列表版本八九不離十（也許設計，但已經超出了我目前的判斷能力） - 主動模式匹配其使用，而它的建設和迭代導致列出了所需的遞歸過於之前計算值深，所以它很懶，但不是很懶，它需要延續，以避免stackoverflow。例如，當第二個序列需要第一個序列中的一個數字時，它已經被計算出來了。換句話說，LL版本並非嚴格的JIT懶序列生成，只有列表管理。

Answer 1

你一定要看看

http://research.microsoft.com/en-us/um/cambridge/projects/fsharp/manual/FSharp.PowerPack/Microsoft.FSharp.Collections.LazyList.html

但我會嘗試後發佈更全面的答案。

UPDATE

好的，一個解決方案是下文。它將Morris序列表示爲int的LazyLists的LazyList，因爲我認爲你希望它在兩個方向都是懶惰的。

的F＃LazyList（在FSharp.PowerPack.dll）有三個有用的特性：（不會發生的第n個元素的評價，直到它首先要求）

• 是懶惰
• 它不重新計算（重新計算同一對象實例上的第n個元素將不會重新計算它 - 它在首次計算後緩存每個元素）
• 您可以'忘記'前綴（當您'追尾'到列表中時， - 更長的引用前綴可用於垃圾收集）

第一個屬性與seq（IEnumerable）是相同的，但其他兩個對LazyList是唯一的，對計算問題非常有用，例如在此問題中提出的計算問題。

事不宜遲，代碼：

// print a lazy list up to some max depth 
let rec PrintList n ll = 
    match n with 
    | 0 -> printfn "" 
    | _ -> match ll with 
      | LazyList.Nil -> printfn "" 
      | LazyList.Cons(x,xs) -> 
       printf "%d" x 
       PrintList (n-1) xs 

// NextMorris : LazyList<int> -> LazyList<int> 
let rec NextMorris (LazyList.Cons(cur,rest)) = 
    let count = ref 1 
    let ll = ref rest 
    while LazyList.nonempty !ll && (LazyList.hd !ll) = cur do 
     ll := LazyList.tl !ll 
     incr count 
    LazyList.cons !count 
     (LazyList.consf cur (fun() -> 
      if LazyList.nonempty !ll then 
       NextMorris !ll 
      else 
       LazyList.empty())) 

// Morris : LazyList<int> -> LazyList<LazyList<int>> 
let Morris s = 
    let rec MakeMorris ll = 
     LazyList.consf ll (fun() -> 
      let next = NextMorris ll 
      MakeMorris next 
     ) 
    MakeMorris s 

// "main" 
// Print the nth iteration, up to a certain depth 
[1] |> LazyList.of_list |> Morris |> Seq.nth 3125 |> PrintList 10 
[1] |> LazyList.of_list |> Morris |> Seq.nth 3126 |> PrintList 10 
[1] |> LazyList.of_list |> Morris |> Seq.nth 100000 |> PrintList 35 
[1] |> LazyList.of_list |> Morris |> Seq.nth 100001 |> PrintList 35 

UPDATE2

如果你只是想算，那也太細：

let LLLength ll = 
    let rec Loop ll acc = 
     match ll with 
     | LazyList.Cons(_,rest) -> Loop rest (acc+1N) 
     | _ -> acc 
    Loop ll 0N 

let Main() = 
    // don't do line below, it leaks 
    //let hundredth = [1] |> LazyList.of_list |> Morris |> Seq.nth 100 
    // if we only want to count length, make sure we throw away the only 
    // copy as we traverse it to count 
    [1] |> LazyList.of_list |> Morris |> Seq.nth 100 
     |> LLLength |> printfn "%A" 
Main()  

內存使用率保持平坦（下16M在我的盒子上）...還沒有完成運行，但我計算了第55長度快，即使在我的慢箱子，所以我認爲這應該工作得很好。請注意，我使用'bignum'的長度，因爲我認爲這會溢出'int'。

Answer 2

只保存您查找的前一個元素。

let morris2 data = seq { 
    let cnt = ref 0 
    let prev = ref (data |> Seq.nth 0) 

    for cur in data do 
     if cur <> !prev then 
      yield! [!cnt; !prev] 
      cnt := 1 
      prev := cur 
     else 
      cnt := !cnt + 1 

    yield! [!cnt; !prev] 
} 

let rec morrisSeq2 cur = seq { 
    yield cur 
    yield! morrisSeq2 (morris2 cur) 
} 

Answer 3

我相信這裏有兩個主要問題：

• 懶惰是非常低效的，所以你可以期待一個懶惰的功能實現運行量級慢。例如，描述here的Haskell實現是比下面給出的F＃I更慢的2,400,×。如果你想要一個解決方法，你最好的辦法可能是通過將計算結果聚合成批量按需生產的批量批次來分攤計算。

• 的Seq.append功能實際上是調用到C＃代碼IEnumerable，因此，它的尾巴呼籲沒有得到消除，你每次都要經過它時泄漏更多的堆棧空間。當你列舉整個序列時，就會顯示出來。

以下是比你實現更快的超過80 ×在計算50序列的長度，但也許它不是懶惰足以讓你：

let next (xs: ResizeArray<_>) = 
    let ys = ResizeArray() 
    let add n x = 
    if n > 0 then 
     ys.Add n 
     ys.Add x 
    let mutable n = 0 
    let mutable x = 0 
    for i=0 to xs.Count-1 do 
    let x' = xs.[i] 
    if x=x' then 
     n <- n + 1 
    else 
     add n x 
     n <- 1 
     x <- x' 
    add n x 
    ys 

let morris = 
    Seq.unfold (fun xs -> Some(xs, next xs)) (ResizeArray [1]) 

此功能的核心是一個倍在ResizeArray之上，如果你使用一個結構作爲累加器，那麼這個結果可以被分解出來並在功能上使用而不會有太多的性能下降。