Ocaml List:实现append和map函数

Question

我目前正在尝试扩展朋友的OCaml计划.这是一些数据分析所需的大量函数.由于我不是一个真正的OCaml破解,我现在仍然坚持(对我而言)奇怪的List实现:

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

我已经发现这实现了某种"懒惰"列表,但我完全不知道它是如何工作的.我需要基于上面的类型实现Append和Map Function.有人知道怎么做吗？

真的很感激任何帮助!

Answer 1

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

这个lazy列表实现的基本思想是每个计算都通过fun() - > x封装在一个函数中(技术术语是一个闭包).然后仅在将函数应用于()(单位值,不包含任何信息)时才计算表达式x.

Answer 2

可能有助于注意函数闭包基本上等同于惰性值:

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