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。所以你有一個正確的尾遞歸算法，不管你需要經過多少次調整，你都不會吹堆棧。