Jac*_*ale 2 ocaml functional-programming
在OCaml中,我们总是这样做first::rest.从列表中获取第一个元素或在列表前插入元素很方便.
但为什么OCaml没有rest::last？没有List函数,我们不能轻易地获取列表的最后一个元素或将元素插入到列表的末尾.
list数据类型不是魔法内置函数,只是具有一些语法糖的常规递归数据类型.你可以自己实现它,使用Nil替代[]和Cons(first,rest)取代first::rest,以下列方式:
type 'a mylist =
| Nil
| Cons of 'a * 'a mylist
我不确定你是否会看到上面的定义作为你的问题的答案,但它确实是:当你写first::rest,你不是在调用函数,你只是使用一个构建一个新值的数据类型构造函数(在恒定的时间和空间).
这个定义很简单,并且具有明确的算法属性:列表是不可变的,访问列表的第一个元素是O(1),访问k-th元素是O(k),两个列表的连接li1和li2是O(length(li1)),等等.特别是,访问最后一个元素或添加一些东西列表的结尾li将是O(length(li)); 我们并不急于将其视为一种方便的操作,因为它很昂贵.
如果要在序列的末尾添加元素,则列表不是正确的数据结构.你可能想要使用一个队列(如果你遵循先进先出的访问规则),a deque等.Queue标准库中有一个(可变的)结构,两个第三方覆盖核心和电池有一个deque模块(在电池中持久存在,在Core中可变).
因为列表只是简单的数据类型定义为
type 'a list = Nil | Cons of 'a * 'a list
除了你拼写Nil为[]和Cons中缀::.换句话说,如果你愿意,列表是"单链接"的.除了构造函数的语法之外,没有任何魔法.显然,要获得最后一个元素,或者附加一个元素,那么你需要一些辅助函数.