具有单子(monad)绑定(bind)的 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)

如果我有一个递归函数(收敛，牛顿法)，每次迭代都绑定(bind) 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 上的绑定(bind)使递归成为尾调用是否正确。第二个问题是是否切换到 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的bind逻辑短路了？或者 adjustment >>= 可以保持堆栈位置吗？

编辑:

因此，根据明确的答案，我可以澄清并回答我的问题——现在相当于尾调用位置是否“可传递”。 (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 函数做的最后一件事(即，它不在 tail position)，我知道该调用不是尾递归的，并且会用完堆栈帧。

现在让我们看一下 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 的结果code> 因此是 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。所以你有一个适当的尾递归算法，无论你必须经过多少调整，你都不会炸毁堆栈。