具有单子绑定的 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

绑定：

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

因为所有日志都必须保留在队列中，直到递归结束（然后加入）。

所以一个问题是 Writer 上的绑定使递归不是尾调用是否正确。第二个问题是是否切换到 Either monad：

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

绑定：

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的bind逻辑短路了？或者 adjustment >>= 可以保持堆栈位置吗？

编辑：

因此，鉴于明确的答案，我可以澄清并回答我的问题——现在相当于尾调用位置是否为 "transitive"。 (1) nextStep的递归调用是nextStep中的尾调用。 (2) 对 nextStep 的（初始）调用是 bind 中的尾调用（我的 Either/Result monad）。 (3) bind 是外层（递归）solve 函数中的尾调用。

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

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。所以你有一个适当的尾递归算法，无论你必须经过多少调整，你都不会炸毁堆栈。

具有单子绑定的 F# 尾递归

F# tail recursion with monadic bind

f#

bind

monads

tail-recursion