functional-programming - 为什么 OCaml 在列表中只有 first::rest，而在列表中没有 rest::last？

Question

在 OCaml 中，对于列表，我们总是执行 first::rest。从列表中取出第一个元素或在列表前面插入一个元素都很方便。

但为什么 OCaml 没有 rest::last？没有 List 的功能，我们无法轻松地获取列表的最后一个元素或将元素插入列表的末尾。

Answer 1

列表数据类型不是神奇的内置数据类型，它只是一种带有一些语法糖的常规递归数据类型。你可以自己实现它，使用 Nil 而不是 [] 和 Cons(first,rest) 而不是 first::rest，通过以下方式:

type 'a mylist =
  | Nil
  | Cons of 'a * 'a mylist

我不确定您是否会将上面的定义视为问题的答案，但它确实是:当您编写 first::rest 时，您并不是在调用函数，您只是在使用一个数据类型构造函数来构建一个新值(在恒定的时间和空间中)。

这个定义很简单并且具有明确的算法属性:列表是不可变的，访问列表的第一个元素是O(1)，访问第k个元素是O(k)，两个列表li1和li2的串联是O(length(li1))，等等。特别是，访问最后一个元素或在列表 li 的末尾添加内容将是 O(length(li))；我们并不急于将此作为一种方便的操作公开，因为它的成本很高。

如果你想在序列的末尾添加元素，列表不是正确的数据结构。您可能想要使用队列(如果您遵循先进先出访问原则)、deque 等。有一个(可变的)Queue 结构在标准库中，以及两个第三方叠加层 Core和 Batteries有一个双端队列模块(在 Batteries 中持久，在 Core 中可变)。