6

List.fold_righttail-recursiveここに示されているとおりではありませんhttp://caml.inria.fr/pub/docs/manual-ocaml/libref/List.html

私の質問は、なぜList.fold_right実装されなかったのtail-recursiveですか？

そうするのは難しいことではないと思います

let rev l = 
  let rec revr acc = function
    | [] -> acc
    | hd::tl -> revr (hd::acc) tl
  in 
  revr [] l;;

let fold_right f l b =
  let rev_l = rev l 
  in 
  let rec folder_rr acc = function
    | [] -> acc
    | hd::tl -> folder_rr (f hd acc) tl
  in 
  folder_rr b rev_l;;

tail-recursive私もライブラリで見つけました、それらがとして実装されることができる間、多くの関数はそうではありませんtail-recursive。メーカーはどのようにしてそのような決定を下しましたか？

4

2 に答える 2

10

この末尾再帰の実装は、より大きなリストに適用できますfold_rightが、リストを 2 回トラバースする必要があるため、短いリストの場合は遅くなります。元の開発者は、リストの極端な使用例 (何千もの要素がある場合は、とにかくより効率的なデータ構造を計画する必要があります) を許可することは、醜いコードと他のすべてのパフォーマンスの悪化の両方を犠牲にして、良いトレードオフではないと判断しました。 .

末尾再帰マップ、fold_right などを使用するには、さまざまな方法があります。それらは、標準ライブラリを拡張するライブラリ、由緒ある Extlib、および新しい Batteries と Core にあります。実装のテクニックは、あなたのものから、最初の 1000 個ほどの項目に対して楽観的に非 tailrec バージョンを使用するトリック、そして tailrec バージョンに切り替えるトリック、そしてコンス セルの突然変異 (パフォーマンスも低下します)。

于 2013-03-12T17:27:08.320 に答える
10

この質問は以前に、おそらく何度も尋ねられました。ここで以前の回答を読むことができます：

OCaml std lib に非末尾再帰関数がたくさんあるのはなぜですか?

私の簡単な答えは、小規模なケースでは、非末尾再帰の実装の方がはるかに高速であることが多いということです。実装者は明らかに、これは良いトレードオフだと考えていました。

于 2013-03-12T17:27:30.947 に答える