避免堆栈溢出(使用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个序列那样调用"枚举"时.请注意,使用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#成语来根据内存大小制定限制.

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处理函数调用来生成sequnces.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#libary是问题,我编写了自己的Seq模块,使用continuation实现了追加,成对,扫描和收集,现在我可以开始生成并打印50,000 seq而没有问题(它永远不会完成,因为它结束了10 ^ 5697位长).

一些额外的说明:

• 延续是我正在寻找的习语,但在这种情况下,他们必须进入F#库,而不是我的代码.我从Tomas Petricek的 真实世界功能编程书中学到了F#的延续.
• 我接受的懒惰列表答案持有另一个成语; 懒惰的评价.在我重写的库中,我还必须利用惰性类型来避免stackoverflow.
• 运行的懒惰列表版本排序(可能是通过设计,但超出了我目前的确定能力) - 它在构造和迭代时使用的活动模式匹配导致列表在所需的递归变得太深之前计算值,所以它是懒惰的,但不是那么懒,它需要延续以避免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个元素不会重新计算它 - 它会在第一次计算后缓存每个元素)
• 你可以'忘记'前缀(当你'尾'进入列表时,不再引用的前缀可用于垃圾收集)

第一个属性与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函数实际上是从 C# 代码中调用的IEnumerable，因此，它的尾部调用不会被消除，并且每次调用它时都会泄漏更多的堆栈空间。当您枚举序列时，就会出现这种情况。

在计算第 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])

该函数的核心是对 a 的折叠，ResizeArray如果您使用结构体作为累加器，则可以将其分解并在功能上使用，而不会降低太多性能。