说我有一堆:
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 Library,Batteries和Containers库提供。
因此,您可以切换到那些库,而无需考虑此问题。尽管仍然强烈建议您尽量少用List.map
,因为此操作始终具有线性内存消耗(堆或堆栈内存),可以避免。因此,最好尽可能使用rev_map
。
关于functional-programming - 使用stdlib List.map进行“评估期间的堆栈溢出”,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/37994553/