为什么OCaml List.fold_right没有实现为尾递归？

Question

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.制造商是如何做出这样的决定的？

Answer 1

这种尾递归实现可以应用于fold_right更大的列表,但代价是较短的列表较慢,因为您必须遍历列表两次.最初的开发人员判断允许列表的极端用例(如果你有数千个元素,你应该计划更高效的数据结构),代价是丑陋的代码并且让其他人的表现更糟,这不是一个很好的权衡.

有很多不同的方法可以使用尾递归映射,fold_right等.你可以在库中找到它们来扩展标准库,古老的Extlib和更新的Batteries and Core.实现技术从你的,到使用非tailrec版本乐观地使用前几千个项目的技巧,然后切换到tailrec版本,以丑陋的不安全技巧进行单次遍历以牺牲细胞突变为代价(这也会降低表现).

Answer 2

之前已经问过这个问题,可能很多次.你可以在这里阅读一些以前的答案:

为什么OCaml std lib有这么多非尾递归函数？

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