f控制单子绑定

Question

使用作家单子＃尾递归

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) 

如果我有一个递归函数（收敛，牛顿法）随每次迭代结合作家结果，我想，这一定不会是尾递归（尽管它可能看起来像它只是从递归调用判断）：

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上的绑定是否使得递归不是尾调用是正确的。第二个问题是，是否切换到要么单子：

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 
//... 

由于无论哪种的绑定的逻辑是短路？或者这个adjustment >>=能够保持在堆叠位置？

编辑：

因此，在明确的答案的光，我可以澄清和回答我的问题 - 现在相当于像尾调用位置是否是“传递”。 （1）nextStep的递归调用是nextStep的尾部调用。 （2）对nextStep的（初始）呼叫是bind（我的Either/Result单子）的尾呼。 （3）bind是外部（递归）solve函数中的尾部调用。

尾部调用分析和优化是否进行嵌套？是。

Answer 1

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

你是正确的，因为bind功能Writer不能调用在尾递归的方式其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函数所做的最后一件事（即它不在的尾部位置），所以我知道那个调用不是尾递归的并且会用完一个栈帧。

现在让我们来看看bind实施Result：

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。所以你有一个正确的尾递归算法，不管你需要经过多少次调整，你都不会吹堆栈。