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) 

を、私はこれが尾を再帰的にしてはいけないと考えています（再帰呼び出しから判断されたように見えるかもしれませんが）。

再帰が終了するまで（そして結合されるまで）、すべてのログをキューに保持する必要があるためです。

したがって、Writerのバインドが末尾呼び出しではなく再帰を行うのが正しいかどうかという質問が1つあります。 2番目の質問は、いずれかのモナドにするかどうかを切り替えている：どちらか一方のバインドの論理があるので

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

：

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

はこの今も末尾再帰を行います：バインドと

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

短絡？または、adjustment >>=がスタック位置を保持できますか？

EDIT：

だから、明確な答えの光の中で、私は明確にし、私の質問に答えることができます - 今末尾呼び出し位置は「推移的」であるか否かのようなものになります。 （1）nextStepへの再帰呼び出しは、nextStepの末尾の呼び出しです。 （2）nextStepへの（初期）コールはbind（私のEither/Resultモナド）の末尾コールです。 （3）bindは、外側（再帰的）solve関数のテールコールです。

テールコール解析と最適化はこのネストを実行しますか？はい。

Answer 1

関数呼び出しがtail-recursiveであるかどうかは、実際は非常に簡単です。呼び出し後に他の作業を行う必要があるかどうか、呼び出しが末尾にあるかどうかを確認してくださいその呼び出しの結果も呼び出し関数によって返された結果です）。これは、コードが何を行うのかを理解していない単純な静的コード解析で行うことができます。なぜなら、コンパイラはそれを実行でき、生成する.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への呼び出しを適切な末尾呼び出しに変換し、スタックフレームを使用しません。

次にレベル1を見てみましょう。ここで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を呼び出します。だから、適切なテール再帰アルゴリズムがあり、何回の調整が必要であってもスタックを吹き飛ばすことはありません。