2

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

但是为什么OCaml没有rest::last呢？如果没有List's 函数，我们将无法轻松获取列表的最后一个元素或将元素插入列表的末尾。

4

2 回答 2

8

list 数据类型不是内置的魔法，只是带有一些语法糖的常规递归数据类型。您可以通过以下方式自己实现它，使用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)); 我们并不急于将其公开为一种方便的操作，因为它的成本很高。

如果要在序列末尾添加元素，列表不是正确的数据结构。您可能想要使用队列（如果您遵循先进先出的访问规则）、adeque等。标准库中有一个（可变）结构， Core和Batteries有Queue两个第三方覆盖一个双端队列模块（在电池中持久，在核心中可变）。

于 2013-02-02T11:53:56.870 回答
5

因为列表只是简单的数据类型，定义为

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

除了你拼写Nilas[]和Consas infix ::。换句话说，如果您愿意，列表是“单链接的”。除了构造函数的语法之外，没有任何魔法。显然，要到达最后一个元素或追加一个元素，您需要一些辅助函数。

于 2013-02-02T11:58:27.660 回答