2009-04-30 20 views
15

私はfollwing機能を書いている場合、私は知っていますか:は、どのように関数がF#で末尾再帰は

let str2lst str = 
    let rec f s acc = 
     match s with 
     | "" -> acc 
     | _ -> f (s.Substring 1) (s.[0]::acc) 
    f str [] 

F#コンパイラはループにそれを回した場合、私が知ることができますどのように?リフレクターを使わずに見つけ出す方法はありますか(私はリフレクターとの経験がなく、私はC#を知らないのですか?)

編集:また、内部関数を使用せずにテール再帰関数を書くことは可能ですか?またはループが存在する必要がありますか?

また、F#std libには、指定された関数を何度も実行する関数がありますか?そのたびに最後の出力を入力として渡しますか?私は文字列を持っていると言う、私は文字列の上に関数を実行し、その後、結果の文字列の上で実行したい...

+0

また、http://stackoverflow.com/questions/5809683/is-my-rec-function-tail-recursive – Brian

答えて

22

残念ながら些細なことはありません。

ソースコードを読んで型を使用して検査でテールコール(「最後のもの」で、「試行」ブロックではない)があるかどうかを判断するのは難しくありませんが、自分自身を推測し、間違いを犯す。単純な自動化された方法はありません(例えば、生成されたコードの検査以外)。

もちろん、大量のテストデータで機能を試してみて、爆発するかどうかを確認できます。

F#コンパイラは、すべてのテールコールに対して.tail IL命令を生成します(ただし、コンパイラのフラグをオフにしない限り、スタックフレームをデバッグするために使用します)。ただし、直接テール再帰的関数はループに最適化されます。 (編集:私は最近、F#コンパイラもこの呼び出しサイトを介して再帰的なループがないことを証明できるケースでは.tailを生成できないと考えています;これは.tailオペコードが多くのプラットフォームでは少し遅くなるという最適化です)

'tailcall'は予約済みのキーワードで、将来のバージョンのF#では、たとえば

tailcall func args 

その後、テールコールでない場合は警告/エラーが表示されます。

自然にテール再帰的ではない(したがって余分なアキュムレータパラメータを必要とする)関数だけが、あなたを「内部関数」イディオムに「強制」します。

ここであなたが求めて何のコードサンプルです:

let rec nTimes n f x = 
    if n = 0 then 
     x 
    else 
     nTimes (n-1) f (f x) 

let r = nTimes 3 (fun s -> s^" is a rose") "A rose" 
printfn "%s" r 
+0

「tailcall」は興味深いものです。コールのサイトを関数全体のより有用な "tailrec"宣言。あなたは「部分的に末尾再帰的」関数を持つことができますか? –

+3

@StephenSwensenあなたは絶対にできます。コントロールフローブランチは、テールコールとテールコールではないコールの間の代替手段につながり、コンパイル時に実際にテールコールであるコールのみをチェックしたい場合があります。 'let rec f x = if x> 0ならば、f(1 + x)else 0 + f(1 + x)'は概念を説明しますが、明らかに終了しません。 –

2

私は親指ポール・グレアムのルールはLispのでに策定好き:仕事はを行うには、左がある場合、例えばは再帰呼び出し出力を操作すると、呼び出しは末尾再帰ではありません。

関連する問題