我有一段关于F#中morris序列的“学习代码”，它遇到了堆栈溢出问题，我不知道如何避免。 "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-2，以此类推，以获取第一个项目（最初的＃是最坏的情况）。
我明白 [|0|] |> Seq.append str |> Seq.windowed 2 正使我的问题更加严重，如果消除它，我可以生成三倍于现在的数量。实际上，代码已经足够好了。Morris的第3125次迭代将超过10^359个字符长度。
我真正要解决的问题是如何保留惰性计算并具有基于内存大小的无限制迭代选择。我正在寻找适当的F#习语来使限制基于内存大小。
更新Oct '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 模块，使用连续性实现了 append、pairwise、scan 和 collect，现在我可以开始生成并打印 50,000 个序列，而不会出现问题（它永远不会完成，因为它超过了 10^5697 位数）。
一些额外的说明：
- 连续性是我正在寻找的习惯用语，但在这种情况下，它们必须进入 F# 库，而不是我的代码。我从 Tomas Petricek 的《Real-World Functional Programming》书中了解到 F# 中的连续性。 - 我接受的惰性列表答案持有另一个习惯用语：惰性求值。在我重写的库中，我还必须利用惰性类型以避免堆栈溢出。 - 惰性列表版本有点运气（也许是有意设计的，但超出了我当前的能力来确定）——它在构建和迭代时使用的活动模式匹配会导致列表在需要递归太深之前计算值，因此它是惰性的，但不是那么惰性，需要连续性来避免堆栈溢出。例如，当第二个序列需要第一个序列的数字时，它已经被计算出来了。换句话说，LL 版本在序列生成方面不是严格的 JIT 惰性，只是列表管理。