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?). 

好像太过分了！看看List.map是如何在Ocaml中实现的，我发现这个（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

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

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

虽然前两个选项是显而易见的，但后两个选项需要一些解释。

更好的数据结构

如果您确实有大量数据，并且这些数据是数值型的，那么您应该考虑使用 Bigarray。此外，根据您的使用情况，地图和哈希表可能会更好。使用函数式编程语言的人倾向于到处使用列表，而不是选择合适的数据结构。不要陷入这个陷阱。

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

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

另一方面，随着时间的推移，人们设法在这种权衡中找到一些最佳方案，即拥有一个相当快的恒定堆栈版本。解决方案是当列表较小时使用非尾递归方法，然后回退到慢速版本。Janestreet 核心库、电池和容器库提供了此类实现。

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