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

Question

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

一个相当标准的实现(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类型和计算构建器

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基础monadic操作的定义:

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)

Answer 2

您是对的 - 出现堆栈溢出的原因是bindmonad的操作需要尾递归（因为它用于在折叠期间聚合值）。

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)