6

List.fold_right不像tail-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较大的列表，但代价是较短的列表会变慢，因为您必须遍历列表两次。最初的开发人员认为，允许列表的极端用例（如果您有数千个元素，则无论如何都应该计划一个更高效的数据结构）以牺牲更丑陋的代码和使其他所有人的性能更差为代价，这不是一个好的权衡.

有很多不同的方法可以使用尾递归映射、折叠右等。您会在扩展标准库、古老的 Extlib 以及更新的电池和核心的库中找到它们。实现技术从你的，到对前一千个左右的项目乐观地使用非 tailrec 版本的技巧，然后切换到 tailrec 版本，到丑陋的不安全技巧，以 cons cell 突变为代价进行单次遍历（这也会降低性能）。

于 2013-03-12T17:27:08.320 回答
10

这个问题以前被问过，可能很多次了。您可以在此处阅读以前的一些答案：

为什么 OCaml 标准库有这么多非尾递归函数？

我的快速回答是，对于小型案例，非尾递归实现通常要快得多。实施者显然认为这是一个很好的权衡。

于 2013-03-12T17:27:30.947 回答