执行懒惰评估(OCaml)

Question

我正在尝试执行懒惰的评估.

---

我创建了一个lazy list类型和相应的map功能.

type 'a zlist = 'a node_t lazy_t
and 'a node_t = Empty | Node of 'a * 'a zlist

let rec zlist_of_list l = lazy (
  match l with
    | [] -> Empty
    | hd::tl -> Printf.printf "transforming %d\n" hd;Node (hd, zlist_of_list tl)
)

let rec list_of_zlist zl = 
  match Lazy.force zl with
    | Empty -> []
    | Node (hd, tl) -> hd::(list_of_zlist tl)

let rec map_z f zl = lazy (
  match Lazy.force zl with
    | Empty -> Empty
    | Node (hd, tl) -> Node (f hd, map_z f tl)
)

第一个问题:

根据我的理解,lazy只需将内容封装在内部() behind而不立即执行.

所以对于功能zlist_of_list,整体而言

match l with
  | [] -> Empty
  | hd::tl -> Node (hd, zlist_of_list tl)

将被延迟,在zlist_of_list应用时不执行单个位,也是如此map_z.

我对吗？

---

下面,我尝试做双 lazy map

let f1 x = Printf.printf "%d\n" x; x

let f2 x = Printf.printf " %d\n" (-x); (-x)

let zl = zlist_of_list [1;2;3]

let zl_m2 = map_z f2 (map_z f1 zl)

let _ = list_of_zlist zl_m2

结果是

transforming 1
1
 -1
transforming 2
2
 -2
transforming 3
3
 -3

我不明白.似乎执行是按列,而不是按行.我认为应该是

1. 每个元素都先变换
2. 然后f1映射到每个元素
3. f2映射到每个元素

第二个问题:

为什么通过懒惰,执行顺序变得那样？

Answer 1

对于你的第一个问题:那是正确的,map_z将返回计算列表下一部分的thunk,而不是列表本身.特别是,定义中的递归调用在map_z强制之前不会下降到列表的其余部分 - 您可以从a的结果中获取一个转换元素map_z而不计算其余部分.

这也是你的第二个问题的答案:你看到一个元素被转换,然后传递给的原因f1,那f2就是你在每个步骤中从懒惰列表中获取一个元素而其他元素保持暂停状态.

这就是懒惰列表的重点!以这种方式做事很有用,因为它提供了一种使用无限(或非常大)列表进行编程的相当自然的方法.如果在使用元素之前必须首先计算整个列表,那么它实际上不是一个惰性数据结构.