避免堆栈溢出（使用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之上，如果你使用一个结构作为累加器，那么这个结果可以被分解出来并在功能上使用而不会有太多的性能下降。