list - Ocaml列表: Implement append and map functions

Question

我目前正在尝试扩展 friend 的 OCaml 程序。这是一些数据分析所需的函数的巨大集合。由于我并不是真正的 OCaml 破解者，所以我目前陷入了(对我来说)奇怪的 List 实现:

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

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

任何帮助将不胜感激!

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

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