避免堆栈溢出（使用 F# 无限序列序列）

Question

我有一个为 f# 中的 morris seq 编写的“学习代码”，它遭受堆栈溢出的困扰，我不知道如何避免。 “morris”返回“看和说”序列的无限序列（即，{{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 个序列上调用“enum”的时候。 请注意，这是 F# 1.9.6.16 的情况，之前的版本最高可达 14000 以上）。 这是因为链接序列的解析方式。 序列是惰性的，因此“递归”是惰性的。 也就是说，seq n 调用 seq n-1，而 seq n-1 又调用 seq n-2，依此类推来获取第一项（第一个 # 是最坏的情况）。

我明白 [|0|] |> Seq.append str |> Seq.windowed 2 使我的问题变得更糟，如果消除它，我可以将生成的 # 增加三倍。 实际上，该代码运行良好。 morris 的第 3125 次迭代长度将超过 10^359 个字符。

我真正想要解决的问题是如何保留惰性评估，并且对我可以选择的迭代的堆栈大小没有限制。 我正在寻找合适的 F# 习惯用法来根据内存大小进行限制。

2010 年 10 月更新

在更好地学习 F#、一点点 Haskell、思考和学习之后， 研究这个问题一年多了，我终于可以回答我自己的问题了。 但与困难问题一样，问题始于错误的问题。 问题不在于序列的序列——这实际上是因为递归定义的序列。 我的函数式编程技能现在好一点了，所以更容易看到下面的版本发生了什么，它仍然得到一个 stackoverflow，

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))

它基本上创建了一个非常长的 Seq 处理函数调用链来生成序列。 F# 自带的 Seq 模块是不使用堆栈就无法跟踪链的。 它对追加和递归定义的序列使用了一种优化，但该优化仅在递归实现追加时才有效。

所以这会起作用

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

并且这个会得到 stackoverflow。

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

为了证明 F# 库是问题所在，我编写了自己的 Seq 模块，该模块使用连续性实现了追加、成对、扫描和收集，现在我可以毫无问题地开始生成和打印 50,000 个 seq（它永远不会完成，因为它已经结束了） 10^5697 位长）。

一些附加说明：

• 延续是我正在寻找的习惯用法，但在这种情况下，它们必须进入 F# 库，而不是我的代码。 我从 Tomas Petricek 的真实世界函数式编程一书中了解了 F# 中的延续。
• 我接受的懒惰列表答案包含了另一个习语； 懒惰评价。 在我重写的库中，我还必须利用惰性类型来避免堆栈溢出。
• 惰性列表版本有点幸运（可能是设计使然，但这超出了我目前的确定能力）-它在构造和迭代时使用的活动模式匹配导致列表在所需的递归变得太深之前计算值，所以它很懒，但又没有懒到需要延续来避免堆栈溢出。 例如，当第二个序列需要第一个序列中的一个数字时，它已经被计算出来了。 换句话说，LL版本对于序列生成并不是严格的JIT惰性，只是列表管理。

Answer 1

您绝对应该查看

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

但我会尝试稍后发布更全面的答案。

更新

好的，解决方案如下。 它将 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

我相信这里有两个主要问题：

• 惰性非常低效，因此您可以预期惰性函数实现的运行速度会慢几个数量级。 例如，此处描述的 Haskell 实现比 F# 慢 2,400 倍我在下面给出。 如果您想要一种解决方法，最好的选择可能是通过将计算集中到急切的批次中来摊销计算，其中批次是按需生成的。

• Seq.append 函数实际上是从 IEnumerable 调用 C# 代码，因此，它的尾部调用不会被消除，并且会泄漏更多的堆栈空间每次你经历它。 当您枚举序列时，就会出现这种情况。

在计算第 50 个子序列的长度时，以下代码比您的实现快 80 倍以上，但也许它对您来说还不够懒：

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 的折叠如果您使用结构体作为累加器，则可以在功能上使用，而不会降低太多性能。

Answer 3

只需保存您查找的前一个元素即可。

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)
}