40

私は F# が初めてで、末尾再帰関数について読んでいて、誰かが関数 foo の 2 つの異なる実装を教えてくれることを望んでいました。

4

5 に答える 5

61

リスト内のアイテムを 'a から 'b にマッピングするなど、単純なタスクから始めます。署名を持つ関数を書きたい

val map: ('a -> 'b) -> 'a list -> 'b list

どこ

map (fun x -> x * 2) [1;2;3;4;5] == [2;4;6;8;10]

非末尾再帰バージョンから始めます。

let rec map f = function
    | [] -> []
    | x::xs -> f x::map f xs

これは末尾再帰ではありません。これは、関数が再帰呼び出しを行った後もまだやるべきことがあるからです。::のシンタックス シュガーですList.Cons(f x, map f xs)。

関数の非再帰的な性質は、最後の行を次のように書き直した場合、もう少し明白になる可能性があります| x::xs -> let temp = map f xs; f x::temp。明らかに、再帰呼び出しの後に機能します。

アキュムレータ変数を使用して末尾再帰にします。

let map f l =
    let rec loop acc = function
        | [] -> List.rev acc
        | x::xs -> loop (f x::acc) xs
    loop [] l

ここでは、 variable で新しいリストを作成していますacc。リストは逆順に作成されるため、ユーザーに返す前に出力リストを逆にする必要があります。

少し頭がおかしい場合は、継続渡しを使用してコードをより簡潔に書くことができます。

let map f l =
    let rec loop cont = function
        | [] -> cont []
        | x::xs -> loop ( fun acc -> cont (f x::acc) ) xs
    loop id l

loopandの呼び出しcontは、追加作業なしで呼び出される最後の関数であるため、末尾再帰です。

これが機能するのは、継続contが新しい継続によってキャプチャされ、それが別の継続によってキャプチャされ、次のようなツリーのようなデータ構造になるためです。

(fun acc -> (f 1)::acc)
    ((fun acc -> (f 2)::acc)
        ((fun acc -> (f 3)::acc)
            ((fun acc -> (f 4)::acc)
                ((fun acc -> (f 5)::acc)
                    (id [])))))

これにより、順序を逆にすることなくリストが作成されます。

価値があるのは、非末尾再帰的な方法で関数を書き始めることです。読みやすく、操作しやすくなります。

大きなリストがある場合は、アキュムレータ変数を使用してください。

アキュムレータを便利な方法で使用する方法が見つからず、他に自由に使えるオプションがない場合は、継続を使用してください。私は個人的に、継続の重要な多用は読みにくいと考えています。

于 2010-07-14T16:46:45.320 に答える
30

他の例よりも短い説明の試み:

let rec foo n =
    match n with
    | 0 -> 0
    | _ -> 2 + foo (n-1)

let rec bar acc n =
    match n with
    | 0 -> acc
    | _ -> bar (acc+2) (n-1)

ここでは、fooを評価して返すために再帰的fooに呼び出す必要があるため、末尾再帰ではありません。foo2+foo(n-1)

ただし、値を返すために再帰呼び出しの戻り値を使用する必要がないbarため、末尾再帰です。bar再帰的に呼び出されbarたものにその値をすぐに返させることができます (呼び出し元のスタックをずっと上に戻す必要はありません)。コンパイラはこれを見て、再帰をループに書き直すことでこれを最適化しました。

最後の行barを次のように変更すると、再帰呼び出しが終了した後に実行する必要があるアクションにつながるため| _ -> 2 + (bar (acc+2) (n-1))、末尾再帰である関数が再び破棄されます。2 +

于 2010-07-14T16:36:31.923 に答える
10

これはより明白な例です。階乗に対して通常行うことと比較してください。

let factorial n =
    let rec fact n acc =
        match n with
        | 0 -> acc
        | _ -> fact (n-1) (acc*n)
    fact n 1

これは少し複雑ですが、戻り値を変更するのではなく、実行中の集計を保持するアキュムレータがあるという考え方です。

さらに、このスタイルのラッピングは通常は良い考えです。そのため、呼び出し元はアキュムレータのシードについて心配する必要がありません (事実は関数に対してローカルであることに注意してください)。

于 2010-07-14T20:55:51.290 に答える
4

F#も勉強中です。以下は、フィボナッチ数を計算する非末尾再帰関数と末尾再帰関数です。

非末尾再帰バージョン

let rec fib = function
    | n when n < 2 -> 1
    | n -> fib(n-1) + fib(n-2);;

末尾再帰バージョン

let fib n =
    let rec tfib n1 n2 = function
    | 0 -> n1
    | n -> tfib n2 (n2 + n1) (n - 1)
    tfib 0 1 n;;

注: フィバナッチ数は非常に急速に増加する可能性があるため、最後の行tfib 0 1 nを置き換え
tfib 0I 1I nて、F# の Numerics.BigInteger 構造を利用できます。

于 2015-12-16T00:38:13.237 に答える
2

また、テストするときは、デバッグ モードでコンパイルするときに、間接末尾再帰 (tailcall) がデフォルトでオフになっていることを忘れないでください。これにより、テールコール再帰がデバッグ モードではスタックをオーバーフローする可能性がありますが、リリース モードではオーバーフローしません。

于 2010-07-14T19:08:51.407 に答える