为什么这个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类型和计算生成器

已邀请:

2 个回复

土投

以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 }

现在，无论以ѭ6completion还是ѭ7defined定义sequence，ѭ4都将完成。问题不在于ѭ5s在使用您的定义时导致堆栈溢出，而是从调用to5ѭ返回的函数在被调用时导致堆栈溢出。要了解为什么会这样，让我们根据底层单子运算扩展ѭ5的定义：

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

现在，希望可以清楚地知道为什么调用ѭ15会导致堆栈溢出：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)

期差骇蓟

您是正确的-之所以会导致堆栈溢出，是因为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。它被实现为带有状态和延续的函数-以结果作为参数调用的函数。对于这个单子，您可以使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)

要回复问题请先登录或注册

为什么这个F＃序列函数不尾递归？

2 个回复

发起人

f#

tail_recursion

tail_call_optimization

问题状态

为什么这个F＃序列函数不尾递归？

与内容相关的链接

2 个回复

发起人

f#

tail_recursion

tail_call_optimization

问题状态