OCaml模块实现

Question

Ocaml的标准库包含各种模块：List，Map，Nativeint等。我知道这些模块的接口已经提供（例如List模块），但我对模块函数中使用的算法及其实现感兴趣。

我在哪里可以找到相关信息？

- Peter

Answer 1

• 在你的系统上：/usr/lib/ocaml/list.ml 和其他 .ml 文件
• 在网上：https://github.com/ocaml/ocaml/blob/trunk/stdlib/list.ml 和其他位于https://github.com/ocaml/ocaml/tree/trunk/stdlib 的 .ml 文件

---

列表实现是一个有趣的学习对象。举个例子，map 函数可以像这样实现：

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

但实现方式是这样的：

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

有什么区别？执行这个：

List.map print_int [1;2;3] ;;
map print_int [1;2;3] ;;

第一个打印出123，但是第二个打印出321！由于对于f a的求值可能会产生副作用，强制正确的顺序非常重要。这正是官方map实现所做的。实际上，即使所有实现都遵循相同的顺序，OCaml中的参数求值顺序也是未指定的，详情请见OCaml文档。

另外，请参考Jane Street博客上关于优化List.map的文章来考虑性能问题（对于小列表，List.map是高效的）。

- Quentin Pradet

---

点赞！（这篇博客对于初学者来说可能有些晦涩难懂：http://ocaml.janestreet.com/?q=node/71） - gasche

有人可以澄清第一种和第二种实现的区别吗？当我在OCaml和F#中运行它们时，两者都会得到123，从未出现过321。由于这个答案已经七年了，也许OCaml和F#本质上发生了变化，但我怀疑？（我没有使用List.map，我正在测试这两个自定义的map函数） - jayphelps

@gasche 有任何想法吗？ - Quentin Pradet

我可以重现这个事实，即使用 f a :: map f li 版本的 map，在最近版本的 OCaml 中运行 ignore (map print_int [1;2;3]) 将会打印出 321。@jayphelps，你的测试设置可能有问题。 - gasche

@gasche 谢谢！jayphelps提出了自己的问题，这引发了更多关于这个问题的讨论（特别是在评论中）：https://dev59.com/ZaHia4cB1Zd3GeqPWJsX - Quentin Pradet

@gasche 是的，不一致性是由于REPL以不同的顺序对它们进行了评估 - 但我的根本问题是没有意识到OCaml（与F＃和SML不同）不保证评估顺序。它是“未指定的”。 - jayphelps

Answer 2

您可以在OCaml源代码中找到这些定义。例如，Map函数的实现在OCaml源代码分发包中的stdlib/map.ml中。

- Michael Ekstrand

Answer 3

这些应该已经安装在您的系统上了。最有可能（假设是Unix系统），它们位于/usr/lib/ocaml或/usr/local/lib/ocaml中。只需打开任何.ml文件即可。

- Niki Yoshiuchi