11

我目前正在尝试扩展朋友的 OCaml 程序。这是一些数据分析所需的大量函数。由于我不是真正的 OCaml 破解者，因此我目前陷入（对我而言）奇怪的 List 实现：

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

我发现这实现了某种“惰性”列表，但我完全不知道它是如何工作的。我需要基于上述类型实现一个 Append 和一个 Map 函数。有没有人知道如何做到这一点？

任何帮助将不胜感激！

4

3 回答 3

7 
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));;

这种惰性列表实现的基本思想是，每个计算都通过 fun () -> x 封装在一个函数中（技术术语是闭包）。只有当函数应用于 () （单位值，不包含任何信息）时，才会评估表达式 x。

于 2009-01-10T12:03:43.123 回答
7

注意到函数闭包本质上等同于惰性值可能会有所帮助：

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-10T14:56:51.743 回答
1

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

于 2009-01-10T19:21:01.147 回答