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

Question

声明：这是我维护的F#随机测试框架FsCheck中出现的问题。我有一个解决方案，但我不喜欢它。此外，我也不理解这个问题——那只是被规避了。

(如果我们要使用专业术语)序列的一个相当标准的实现是:

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#团队的聪明兔子们已经规避了这个问题。计算生成器实现是否存在问题？

如果我将实现更改为以下内容，则一切正常：

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类型和计算生成器。

- Kurt Schelfthout

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 }

现在，无论是基于Kurt.gen还是Tomas.gen定义的sequence [for i in 1 .. 100000 -> unit i]，都将运行到完成。问题不在于使用您的定义时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需要对sequence进行非尾递归调用并评估结果函数，因此每个递归调用都会有一个堆栈帧。

将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)

- kvb

---

现在非常清楚了。感谢您提供如此详细的说明。 - Kurt Schelfthout

Answer 2

你是正确的-你遇到堆栈溢出的原因是单子的bind操作需要尾递归（因为它用于在折叠期间聚合值）。

FsCheck中使用的单子本质上是一个状态单子（它保持当前生成器和一些数字）。我进行了简化，得到了类似以下内容：

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更改为continuation monad。 它被实现为一个函数，该函数接受状态和continuation - 一个用结果作为参数调用的函数。 对于这个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)

- Tomas Petricek

---

嗯... bind 在任何情况下都不是尾递归，因为它本身就不是递归的。此外，在两种情况下，对 Gen 构造函数的调用都处于尾部位置。我认为这个解释不足够。 - kvb

非常感谢您查看这个问题，Tomas。正如kvb所说，这引发了比回答更多的问题。特别是，计算表达式是否有什么使编译器失去使用bind编写的函数的“尾递归性”的东西，如果bind不是以续传风格编写的？这是否意味着几乎任何真实世界的计算构建器都需要续传？ - Kurt Schelfthout