functional-programming - Ocaml - Lazy.force

Question

我的地图功能是否在：

type 'a stream = Cons of 'a * 'a stream Lazy.t

let rec ones = Cons(1, lazy(ones));;

let rec map (f:'a -> 'b) (s:'a stream) : 'b stream =
  match s with
  |Cons(h,t) -> Cons(f h, lazy (map f (Lazy.force t)));;
;;

正确的？Lazy.forcing 会不会已经让它被记住了？

Answer 1

是的，这是正确的。

但是请注意，将其应用于常规/循环而不是无限数据结构（如此ones处）时，将不会共享计算。强制的 N 个第一个元素map succ ones仍将应用succN 次。（实际上有一些关于语言的研究工作可以检测这种形式的规律性/循环并对其进行严格的映射终止，参见例如CoCaml项目。）

Answer 2

ocaml Lazy 类型有一些魔力。我认为当你自己实现它时更容易理解惰性，虽然在语法上不方便但很容易。诀窍是

• 使用闭包延迟评估
• 使用参考单元来记忆计算

这里很清楚在 Lazy'.force 期间记忆是如何以及何时发生的。

module Lazy' : sig
  type 'a t
  val delay: (unit -> 'a) -> 'a t
  val force: 'a t -> 'a
end = struct
  type 'a susp =
  | NotYet of (unit -> 'a)
  | Done of 'a

  type 'a t = 'a susp ref

  let delay f = ref (NotYet f)

  let force f =
    match !f with
    | Done x -> x
    | NotYet f' ->
      let a = f'() in
      f := Done a;
      a
end

type 'a stream = Cons of 'a * 'a stream Lazy'.t;;

let one = let rec one' () = Cons(1, Lazy'.delay one') in one' () ;;

让 rec 映射 fs = 匹配 s 与 | Cons(h, t) -> Cons(fh, Lazy'.delay (fun () -> map f(Lazy'.force t))) ;;