functional-programming - "Stack overflow during evaluation"与 stdlib List.map

Question

假设我有一堆:

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 的编写方式使其不是尾递归的。

是吗？

如何将一个函数映射到很多东西上？

Answer 1

是的，OCaml 标准库中的 List.map 不是尾递归的。您有多种选择:

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

虽然前两个选项很明显，但后两个需要一些解释。

更好的数据结构

如果您确实有大量数据，并且这些数据是数字的，那么您应该考虑使用 Bigarrays。此外，根据您的用例， map 和哈希表可能会更好。使用函数式编程语言的人倾向于在任何地方使用列表，而不是选择合适的数据结构。不要踏入这个陷阱。

其他库以及为什么它是非尾递归的

List.map 是非尾递归的，这是有充分理由的。在堆栈使用和性能之间总是存在权衡。对于小列表(这是最常见的用例)，非尾递归版本要快得多。所以标准库决定提供一个快速的 List.map，如果你需要处理大列表，那么你可以使用 List.rev_map xs |> List.rev .此外，有时您可以省略 List.rev 部分。所以，标准库不是替你思考，而是给你一个选择。

另一方面，随着时间的推移，人们设法在这种权衡中找到了一些最佳选择，即拥有一个非常快的恒定堆栈版本。解决方案是在列表较小时使用非尾递归方法，然后回退到慢版本。此类实现由 Janestreet Core Library 提供, Batteries和 Containers图书馆。

因此，您可以切换到这些库并忘记这个问题。尽管仍然强烈建议不要使用 List.map 并小心谨慎，因为此操作始终具有线性内存消耗(堆内存或堆栈内存)，这是可以避免的。因此，最好尽可能使用 rev_map。