1

末尾再帰関数についていくつか質問があります。たとえば、これとこれですが、次のようなものは見つかりませんでした。

私の理解では、末尾呼び出しに最適化された関数は、それ以上の評価なしに、最後の呼び出しで累積値を返す必要があります。たとえば、ループ2に最適化される階乗関数を使用すると、非常に簡単に理解できます。しかし、他の場合、たとえば次のように、その最後の呼び出しは何であるかを伝えることは必ずしも明白ではありません。関数は体内で複数回再帰的に呼び出されるため、それらの多くがあります。

ブライアンはそれを見つける方法を提案しますが、末尾呼び出しを最適化する方法がわかりません。フラグをコンパイラに渡し--tailcallsて自動的に実行できますが、常に成功しますか？

f同じタイプをg返します。

type T = T of int * T list

let rec myfunc f (T (x,xs)) =
    if (List.isEmpty xs) then f x
    else 
        List.fold g acc (List.map (fun xxs -> myfunc f xxs) xs)

上記のコードを末尾呼び出しで最適化するためのヘルプをいただければ幸いです。

4

2 に答える 2

5

私の理解では、末尾呼び出しに最適化された関数は、最後の呼び出しで累積値を返す必要があります...

ほとんど。末尾再帰とは、再帰呼び出しがすべて末尾位置に表示される場合です。テールポジションとは、発信者が着信者から直接結果を返すことを意味します。

次では、その最後の呼び出しは何ですか？

テールポジションには2つのコールがあります。まず、への呼び出しf。第二に、への呼び出しList.fold。再帰呼び出しは、その戻り値が呼び出し元から直接返されないため、テール位置にありません。

if (List.isEmpty xs) then f x

また、andfriendsの代わりにパターンマッチングを使用しisEmptyてください。

上記のコードを末尾呼び出しで最適化するためのヘルプをいただければ幸いです。

末尾再帰バージョンの作成を誰かが支援できるようになる前に、作業コードまたは少なくとも仕様を投稿する必要があります。一般に、最も簡単な解決策は、継続渡しスタイルまたは命令スタイルで記述することです。

于 2012-05-28T22:55:19.880 に答える
5

Jon が既に言ったように、関数は末尾再帰ではありません。基本的な問題は、自分自身を再帰的に複数回呼び出す必要があることです(リスト内のすべての要素に対して 1回xs、これは に渡されるラムダ関数で行われますList.map)。

実際に複数の再帰呼び出しを行う必要がある場合は、継続渡しスタイルまたは命令スタックを使用することがおそらく唯一のオプションです。継続の背後にある考え方は、すべての関数が (最後の引数として) 別の関数を取り、結果が利用可能になったときに実行する必要があるというものです。

次の例は、通常バージョン (左側) と継続ベース (右側) を示​​しています。

let res = foo a b                          fooCont a b (fun res ->
printfn "Result: %d" res                     printfn "Result: %d" res)

fold関数を継続渡しスタイルで記述するには、継続ベースの関数も使用する必要があります。で行われた操作を のラムダ関数にmap移動することで、最初に使用を避けることができます。mapfold

List.fold g acc (List.map (fun xxs -> myfunc f xxs) xs)

なる:

List.fold (fun state xxs -> g state (myfunc f xxs)) acc xs

次に、コードを次のように書き直すことができます（質問に表示されなかった と の両方が継続ベースの関数になっているため、継続を表す追加の引数を取ることに注意してください）f：g

// The additional parameter 'cont' is the continuation to be called 
// when the final result of myfunc is computed
let rec myfunc' f (T (x,xs)) cont = 
  if (List.isEmpty xs) then 
    // Call the 'f' function to process the last element and give it the
    // current continuation (it will be called when 'f' calculates the result)
    f x cont
  else  
    // Using the continuation-based version of fold - the lambda now takes current
    // element 'xxs', the accumulated state and a continuation to call
    // when it finishes calculating 
    List.foldCont (fun xxs state cont -> 
      // Call 'myfunc' recursively - note, this is tail-call position now!
      myfunc' f xxs (fun res -> 
        // In the continuation, we perform the aggregation using 'g'
        // and the result is reported to the continuation that resumes
        // folding the remaining elements of the list.
        g state res cont)) acc xs cont

このList.foldCont関数は の継続ベースのバージョンでfoldあり、次のように記述できます。

module List = 
  let rec foldCont f (state:'TState) (list:'T list) cont =
    match list with
    | [] -> cont state
    | x::xs -> foldCont f state xs (fun state ->
        f x state cont)

完全な動作例を投稿していないため、コードを実際にテストすることはできませんでしたが、動作するはずです。

于 2012-05-29T00:00:43.217 に答える