说我有一堆:

Array.make (int_of_float (2. ** 17.)) 1
    |> Array.to_list;;
- : int list
= [1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;
   1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;
   1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;
   1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;
   1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;
   1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;
   1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;
   1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;
   1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;
   1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;
   1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1;
   1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; ...]


我想在这些函数上映射一个函数:

Array.make (int_of_float (2. ** 17.)) 1
    |> Array.to_list
    |> List.map (fun x -> x * 2);;
Stack overflow during evaluation (looping recursion?).


好像太多了!研究如何在Ocaml中实现List.map,我发现了这一点
https://github.com/ocaml/ocaml/blob/trunk/stdlib/list.ml#L57-L59):

let rec map f = function
    [] -> []
  | a::l -> let r = f a in r :: map f l


我对Ocaml还是很陌生,但是看起来map的编写方式使其不尾递归。

那正确吗?

如何在很多东西上映射一个函数?

最佳答案

是的,OCaml标准库中的List.map不是尾部递归的。您在这里有几种选择:


使用Array.map
使用List.rev_map(可能是List.rev创造的)
使用其他更适合您的任务的数据结构
不要使用标准库


尽管前两个选项很明显,但后两个需要一些解释。

更好的数据结构

如果您确实有大量数据,并且此数据是数字数据,则应考虑使用Bigarrays。另外,根据您的用例,Maps和Hashtables可能更好。使用函数式编程语言的人们倾向于在各处使用列表,而不是选择适当的数据结构。不要陷入这个陷阱。

其他库及其非尾递归的原因

List.map是非尾递归的,这有充分的理由。在堆栈使用率和性能之间总是要权衡取舍。对于小列表(这是最常见的用例),非尾递归版本要快得多。因此,标准库决定提供一个快速的List.map,如果您需要处理大列表,则可以使用List.rev_map xs |> List.rev。此外,有时您可以省略List.rev部分。因此,标准库不会试图为您考虑,它为您提供了选择。

另一方面,随着时间的流逝,人们设法在此折衷中找到一些最佳值,即具有相当快的恒定堆栈版本。解决方案是在列表较小时使用非尾递归方法,然后回退到慢速版本。此类实现由Janestreet Core LibraryBatteriesContainers库提供。

因此,您可以切换到那些库,而无需考虑此问题。尽管仍然强烈建议您尽量少用List.map,因为此操作始终具有线性内存消耗(堆或堆栈内存),可以避免。因此,最好尽可能使用rev_map

关于functional-programming - 使用stdlib List.map进行“评估期间的堆栈溢出”,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/37994553/

10-08 22:05
查看更多