f# - 为什么这个 F# 序列函数不是尾递归的？

Question

披露:这出现在我维护的 F# 随机测试框架 FsCheck 中。我有一个解决方案，但我不喜欢它。此外，我不明白这个问题 - 它只是被规避了。

(monadic, if we're going to use big words) 序列的一个相当标准的实现是:

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)

为了完整起见，可以找到 Gen 类型和计算构建器 in the FsCheck source

Answer 1

基于 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 [for i in 1 .. 100000 -> unit i]不管 sequence 是否会运行到完成定义为 Kurt.gen或 Tomas.gen .问题不在于 sequence使用您的定义时导致堆栈溢出，这是从调用返回的函数 sequence调用时会导致堆栈溢出。

要了解为什么会这样，让我们​​扩展 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溢出堆栈: 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))))

关于这个变体的推理很棘手。您可以凭经验验证它不会因某些任意大的输入而破坏堆栈(正如 Tomas 在他的回答中所显示的那样)，并且您可以逐步进行评估以说服自己相信这一事实。但是，堆栈消耗取决于 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)