"Stack overflow during evaluation" 与标准库 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 不是尾递归，使用 List.rev_map 代替它是尾递归。 ... List.rev 应该是尾递归的。

List记录了List模块的所有功能，说明是否不是尾递归

Answer 2

是的，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 and Containers 库提供。

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

Answer 3

您要做的是在计算结束时构建列表：

let construct_value _ =
 1 |> (fun x -> x * 2)

let rec construct_list f n =
 let rec aux acc n =
  if n < 0
  then acc
  else aux (f n) (n-1)
 in
 aux [] (n-1)

let result = construct_list construct_value (int_of_float (2. ** 17.))

在这里您最终得到与计算中相同的列表，但时间和内存使用量更少。请注意，列表的元素是从列表的底部构造的（你必须为尾递归这样做），我添加了一个 "index" 参数，它对应于你数组中的确切位置（我没有构建，另一个时间和记忆增益）

另外，如果你想对这么大的数据结构进行计算，列表可能不是最好的选择，但这取决于你打算用它做什么。

"Stack overflow during evaluation" 与标准库 List.map

"Stack overflow during evaluation" with stdlib List.map

functional-programming

ocaml

tail-recursion

更好的数据结构

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