Ocaml：惰性列表

Question

如何制作一个表示加倍数字序列的惰性列表？例子：

1 2 4 8 16 32

Answer 1

使用流：

let f x = Stream.from (fun n -> Some (x * int_of_float (2.0 ** float_of_int n)))

或

let f x =
  let next = ref x in
    Stream.from (fun _ -> let y = !next in next := 2 * y ; Some y)

使用自定义 lazy_list 类型：

type 'a lazy_list =
  | Nil
  | Cons of 'a * 'a lazy_list lazy_t
let rec f x = lazy (Cons (x, f (2*x)))

Answer 2

另外，我的 OCaml 网络应用程序环境 中有一个名为 Cf_seq 的惰性列表模块核心基础。事实上，我写了一整套函数式数据结构。这一切都可以在 2 条款 BSD 许可证下使用。享受。

更新：代码已重命名为“Oni”，现在托管在位桶。您还可以使用 GODI 包。

Answer 3

如果你想手动完成，我想说你必须主要选项：

• 使用自定义的lazy_list类型，就像ephemient所说的那样（除了他的解决方案有点破损）：

  输入 'lazy_list =
      |零
      | 'a * 'lazy_list 的缺点
  
  让头=函数
      |无 ->失败“无法提取空列表的头部”
      |缺点 (h, _) ->小时
  
  让尾=函数
      |无 ->失败“无法提取空列表的尾部”
      |缺点（_，t）-> t
  

• 使用一种 thunk （就像用来实现惰性的东西 ）以不支持它的语言进行评估）。您将列表定义为函数 unit -> 'a 说明如何从当前元素获取下一个元素（无需为此使用流）。例如，要定义所有自然整数的列表，您可以这样做

  让 make_lazy_list 初始 next =
      让lazy_list当前（）=
          让结果 = !当前在
          当前：=（下一个！当前）；结果
      在lazy_list中（参考初始值）
  
  让naturals = make_lazy_list 0（函数i -> i + 1）
  

  如果你这样做

  print_int(naturals());
  print_int(自然数());
  print_int（自然数（））
  

  您将得到以下输出：

  <前><代码>0
  1
  2

Answer 4

来自遥远未来的答案...

OCaml 4.07 引入了 Seq 模块< /a> 这可以促进这一点。

# let rec lazy_list start f () =
    Seq.Cons (start, lazy_list (f start) f);;
val lazy_list : 'a -> ('a -> 'a) -> 'a Seq.t = <fun>
# lazy_list 1 @@ ( * ) 2
  |> Seq.take 5 
  |> List.of_seq;;
- : int list = [1; 2; 4; 8; 16]