Ocaml List:执行追加和映射功能
问题描述:
我正在尝试扩展朋友的OCaml程序。这是所需要的一些数据分析功能的巨大集合。由于我不是一个真正的OCaml的裂缝目前我卡上(对我来说)陌生的List实现:Ocaml List:执行追加和映射功能
type 'a cell = Nil
| Cons of ('a * 'a llist)
and 'a llist = (unit -> 'a cell);;
我已经想通了,这实现了某种“懒惰”列表,但我完全不知道它是如何工作的。我需要根据上面的类型实现一个Append和一个Map函数。有谁知道如何做到这一点?
任何帮助真的很感谢!
答
let rec append l1 l2 =
match l1() with
Nil -> l2 |
(Cons (a, l)) -> fun() -> (Cons (a, append l l2));;
let rec map f l =
fun() ->
match l() with
Nil -> Nil |
(Cons (a, r)) -> fun() -> (Cons (f a, map f r));;
此实现懒惰名单的基本思想是每个计算是在一个函数(技术术语是关闭),通过有趣的封装() - > X。 然后,只有函数应用于()(单位值,不包含任何信息)时才会评估x表达式。
答
它可以帮助需要注意的是函数闭基本上等同于懒惰值:
lazy n : 'a Lazy.t <=> (fun() -> n) : unit -> 'a
force x : 'a <=> x() : 'a
所以类型'a llist
相当于
type 'a llist = 'a cell Lazy.t
即,一个懒惰的单元格的值。
的地图实现可能更有意义上述定义
let rec map f lst =
match force lst with
| Nil -> lazy Nil
| Cons (hd,tl) -> lazy (Cons (f hd, map f tl))
翻译的术语,其放回关闭:
let rec map f lst =
match lst() with
| Nil -> (fun() -> Nil)
| Cons (hd,tl) -> (fun() -> Cons (f hd, map f tl))
与追加
同样
let rec append a b =
match force a with
| Nil -> b
| Cons (hd,tl) -> lazy (Cons (hd, append tl b))
变得
let rec append a b =
match a() with
| Nil -> b
| Cons (hd,tl) -> (fun() -> Cons (hd, append tl b))
我通常更喜欢使用lazy
语法,因为它使得它更清楚发生了什么。
请注意,还有一个懒惰悬挂和关闭不是正好等效。例如,
let x = lazy (print_endline "foo") in
force x;
force x
打印
foo
而
let x = fun() -> print_endline "foo" in
x();
x()
打印
foo
foo
的区别在于force
计算表达式的值恰好一次。
答
是的,列表可以是无限的。在其他答案中给出的代码将追加到无限列表的末尾,但没有可以编写的程序,也不能观察无限列表后面追加的内容。