为什么这个F＃序列函数不是尾递归？
披露：这发生在我维护的F＃随机测试框架FsCheck中。 我有一个解决方案，但我不喜欢它。 而且，我不明白这个问题 - 它只是被规避了。
一个相当标准的实现（如果我们打算使用大词汇，monadic）是：
let sequence l =
let k m m' = gen { let! x = m
let! xs = m'
return (x::xs) }
List.foldBack k l (gen { return [] })
凡gen可以被选择的计算生成器替换。 不幸的是，这个实现消耗了堆栈空间，所以如果列表足够长，最终会导致堆栈溢出。问题是：为什么？ 我原则上知道foldBack不是尾递归，但F＃团队的聪明兔子已经在foldback实现中规避了这一点。 计算构建器实现中是否存在问题？
如果我将实现更改为下面，一切都很好：
let sequence l =
let rec go gs acc size r0 =
match gs with
| [] -> List.rev acc
| (Gen g)::gs' ->
let r1,r2 = split r0
let y = g size r1
go gs' (y::acc) size r2
Gen(fun n r -> go l [] n r)
为了完整起见，可以在FsCheck源中找到Gen类型和计算构建器
基于Tomas的回答，我们定义两个模块：
module Kurt =
type Gen<'a> = Gen of (int -> 'a)
let unit x = Gen (fun _ -> x)
let bind k (Gen m) =
Gen (fun n ->
let (Gen m') = k (m n)
m' n)
type GenBuilder() =
member x.Return(v) = unit v
member x.Bind(v,f) = bind f v
let gen = GenBuilder()
module Tomas =
type Gen<'a> = Gen of (int -> ('a -> unit) -> unit)
let unit x = Gen (fun _ f -> f x)
let bind k (Gen m) =
Gen (fun n f ->
m n (fun r ->
let (Gen m') = k r
m' n f))
type GenBuilder() =
member x.Return v = unit v
member x.Bind(v,f) = bind f v
let gen = GenBuilder()
为了简化一些事情，让我们将原始序列函数重写为
let rec sequence = function
| [] -> gen { return [] }
| m::ms -> gen {
let! x = m
let! xs = sequence ms
return x::xs }
现在，无论sequence是按照Kurt.gen还是Tomas.gen定义的， sequence [for i in 1 .. 100000 -> unit i] Kurt.gen sequence [for i in 1 .. 100000 -> unit i]都将运行到完成。 问题不在于，在使用定义时， sequence会导致堆栈溢出，而是从调用返回到sequence的函数在调用时会导致堆栈溢出。
要明白为什么这样，让我们用下面的monadic操作来扩展sequence的定义：
let rec sequence = function
| [] -> unit []
| m::ms ->
bind (fun x -> bind (fun xs -> unit (x::xs)) (sequence ms)) m
内联Kurt.unit和Kurt.bind价值观和简化如疯狂，我们得到
let rec sequence = function
| [] -> Kurt.Gen(fun _ -> [])
| (Kurt.Gen m)::ms ->
Kurt.Gen(fun n ->
let (Kurt.Gen ms') = sequence ms
(m n)::(ms' n))
现在希望清楚为什么let (Kurt.Gen f) = sequence [for i in 1 .. 1000000 -> unit i] in f 0调用let (Kurt.Gen f) = sequence [for i in 1 .. 1000000 -> unit i] in f 0溢出堆栈： f需要一个非尾递归调用来序列化和评估结果函数，所以每次递归调用都会有一个栈帧。
内联Tomas.unit和Tomas.bind插入到sequence的定义中，我们得到以下简化版本：
let rec sequence = function
| [] -> Tomas.Gen (fun _ f -> f [])
| (Tomas.Gen m)::ms ->
Tomas.Gen(fun n f ->
m n (fun r ->
let (Tomas.Gen ms') = sequence ms
ms' n (fun rs -> f (r::rs))))
推理这个变体是棘手的。 你可以凭经验验证它不会因为一些任意大的输入而打击堆栈（正如托马斯在他的回答中所表明的那样），你可以逐步完成评估以说服你自己。 然而，堆栈消耗取决于Gen则传递在列表中的实例，并有可能吹堆栈本身不是尾递归输入：
// ok
let (Tomas.Gen f) = sequence [for i in 1 .. 1000000 -> unit i]
f 0 (fun list -> printfn "%i" list.Length)
// not ok...
let (Tomas.Gen f) = sequence [for i in 1 .. 1000000 -> Gen(fun _ f -> f i; printfn "%i" i)]
f 0 (fun list -> printfn "%i" list.Length)
你是正确的 - 你得到堆栈溢出的原因是monad的bind操作需要是尾递归的（因为它用于在折叠过程中聚合值）。
FsCheck中使用的monad本质上是一个状态monad（它保留当前的生成器和一些数字）。 我简化了一下，得到了如下内容：
type Gen<'a> = Gen of (int -> 'a)
let unit x = Gen (fun n -> x)
let bind k (Gen m) =
Gen (fun n ->
let (Gen m') = k (m n)
m' n)
在这里， bind函数不是尾递归的，因为它调用了k ，然后做了一些更多的工作。 您可以将monad更改为延续monad。 它是作为一个函数实现的，它接受状态和延续 - 一个以结果作为参数调用的函数。 对于这个monad，你可以使bind尾递归：
type Gen<'a> = Gen of (int -> ('a -> unit) -> unit)
let unit x = Gen (fun n f -> f x)
let bind k (Gen m) =
Gen (fun n f ->
m n (fun r ->
let (Gen m') = k r
m' n f))
以下示例不会堆栈溢出（并且它与原始实现一起）：
let sequence l =
let k m m' =
m |> bind (fun x ->
m' |> bind (fun xs ->
unit (x::xs)))
List.foldBack k l (unit [])
let (Gen f) = sequence [ for i in 1 .. 100000 -> unit i ]
f 0 (fun list -> printfn "%d" list.Length)