F#尾递归及单子绑定

Question

使用Writer Monad：

type Writer< 'w, 'a when 'w : (static member add: 'w * 'w -> 'w) 
                    and  'w : (static member zero: unit -> 'w) > = 

    | Writer of 'a * 'w 

使用 bind：

let inline bind ma fm =
    let (Writer (a, log1)) = ma 
    let mb = fm a
    let (Writer (b, log2)) = mb
    let sum = ( ^w : (static member add :  ^w * ^w -> ^w) (log1, log2) )
    Writer (b, sum)

如果我有一个递归函数（收敛，牛顿法），每次迭代都会绑定Writer结果，我认为这不可能是尾递归的（即使从递归调用中判断出来看起来像）。

let solve params =
    let rec solve guess iteration = 
        let (adjustment : Writer<Error,float>) = getAdjustment params guess
        let nextStep adjustment = 
            if (abs adjustment) <= (abs params.tolerance) then
                Writer.rtn guess
            elif iteration > params.maxIter then
                Writer (0.0, Error.OverMaxIter)
            else
                solve (guess + adjustment) (iteration + 1)

        adjustment >>= nextStep

    sovle params.guess 1

因为所有的日志都必须在递归结束之前保留在队列中（然后连接）。因此，一个问题是绑定写入器是否使递归不是尾调用。第二个问题是是否切换到Either monad：

type Result<'e, 'a> = 
    | Ok of 'a
    | Err of 'e

使用 bind：

let bind ma fm =
    match ma with 
    | Ok a  -> fm a
    | Err e -> Err e

现在将实现尾递归：

//...
        let (adjustment : Result<Error,float>) = getAdjustment params guess
        let nextStep adjustment = 
            if (abs adjustment) <= (abs params.tolerance) then
                Result.rtn guess
            elif iteration > params.maxIter then
                Result.fail Error.OverMaxIter
            else
                solve (guess + adjustment) (iteration + 1)

        adjustment >>= nextStep
//...

由于Either的绑定逻辑是短路的，所以adjustment >>=是否会保留堆栈位置？

编辑：

鉴于明确的答案，我可以澄清和回答我的问题——现在问题变成了尾调用位置是否“可传递”。(1)对于nextStep的递归调用是在nextStep中的尾调用。(2)对于Either/Result单子的bind，(initial)调用在bind中是一个尾调用。(3)solve函数的外部(递归)中的bind是一个尾调用。

尾调用分析和优化是否通过这种嵌套？是的。

- RomnieEE

---

假设您已将>>=运算符定义为对bind的简单调用，则行adjustment >>= nextStep与bind adjustment nextStep完全等效：仅当函数执行更多工作时，它将保留堆栈帧。由于此处的bind调用位于尾部位置，因此不会有额外的堆栈帧。请参见下面的答案以获取更多信息。 - rmunn

是的，你说的操作符是这样的：let (>>=) ma fm = Result.bind ma fm。 - RomnieEE

Answer 1

要判断一个函数调用是否是尾递归，其实非常简单：只需查看调用函数是否需要在该调用之后执行其他操作，或者该调用是否处于尾部位置（即它是函数执行的最后一件事情，并且该调用的结果也是调用函数返回的结果）。可以通过简单的静态代码分析来完成此操作，而无需理解代码的实际功能——这就是编译器能够做到这一点并在生成的 .DLL 中产生正确的 .tail 操作码的原因。

您说的没错，对于 Writer 的 bind 函数，无法以尾递归的方式调用其 fm 参数 —— 当您查看问题中编写的 bind 实现时，这一点非常容易证明。

let inline bind ma fm =
    let (Writer (a, log1)) = ma 
    let mb = fm a   // <--- here's the call
    let (Writer (b, log2)) = mb   // <--- more work after the call
    let sum = ( ^w : (static member add :  ^w * ^w -> ^w) (log1, log2) )
    Writer (b, sum)

这就是我需要查看的全部内容。因为对fm的调用不是bind函数执行的最后一件事情（即它不在尾部位置），所以我知道该调用不是尾递归的，会使用一个堆栈帧。

现在让我们看一下Result的bind实现：

let bind ma fm =
    match ma with 
    | Ok a  -> fm a  // <--- here's the call
    | Err e -> Err e // <--- not the same code branch
    // <--- no more work!

因此，在这个bind的实现中，对fm的调用是函数在该代码分支上执行的最后一件事情，因此fm的结果就是bind的结果。所以编译器将把对fm的调用转换为适当的尾调用，并且它不会占用栈帧。

现在让我们看一下你调用bind的层次。 （好吧，你使用>> =运算符，但我假设你已将其定义为let（>> =）ma fm = bind ma fm或等效的内容。注意：如果您的定义与此显著不同，则下面的分析将不正确。）您对bind的调用如下：

let rec solve guess iteration =
    // Definition of `nextStep` that calls `solve` in tail position
    adjustment >>= nextStep

从编译器的角度来看，代码行 adjustment >>= nextStep 与 bind adjustment nextStep 完全等价。因此为了进行尾部位置代码分析，我们将假定该行代码为 bind adjustment nextStep。

假设这就是 solve 的整个定义，并且你没有展示其他未知代码，那么对 bind 的调用处于尾部位置，因此它不会消耗栈帧。而 bind 在尾部位置调用 fm（这里是 nextStep）。nextStep 在尾部位置调用 solve。因此你拥有一个正确的尾递归算法，无论需要经过多少次调整，都不会爆栈。

- rmunn

---

不错的分析。谢谢。我看到最终位置的分析是如何贯穿或流经所有作用域的。这不仅仅关注于递归声明函数调用的具体位置。非常有帮助。再次感谢。 - RomnieEE