Ocaml List：执行追加和映射功能

我正在尝试扩展朋友的OCaml程序。这是所需要的一些数据分析功能的巨大集合。由于我不是一个真正的OCaml的裂缝目前我卡上（对我来说）陌生的List实现：Ocaml List：执行追加和映射功能

type 'a cell = Nil 
    | Cons of ('a * 'a llist) 
and 'a llist = (unit -> 'a cell);;

我已经想通了，这实现了某种“懒惰”列表，但我完全不知道它是如何工作的。我需要根据上面的类型实现一个Append和一个Map函数。有谁知道如何做到这一点？

任何帮助真的很感谢！

来源

2009-01-10 Chris

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表达式。

来源

2009-01-10 12:03:43 starblue

它可以帮助需要注意的是函数闭基本上等同于懒惰值：

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计算表达式的值恰好一次。

来源

2009-01-10 14:56:51

是的，列表可以是无限的。在其他答案中给出的代码将追加到无限列表的末尾，但没有可以编写的程序，也不能观察无限列表后面追加的内容。

来源

2009-01-10 19:21:01

Ocaml List：执行追加和映射功能

回答

相关问题