stream - 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

伟大的博客特权思想有一篇关于这个主题的精彩文章：

http://enfranchismind.com/blog/posts/ocaml-lazy-lists-an-introduction/

您还可以查看http://batteries.forge.ocamlcore.org/doc.preview%3Abatteries-beta1/html/api/Lazy%5Flist.html

这是处理这个问题的标准库。

这个问题也和这个问题很相似：

有哪些 OCaml 库用于惰性列表处理？

Answer 3

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

更新：代码已重命名为“ Oni ”，现在托管在 BitBucket 上。你也可以使用GODI包。

Answer 4

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

• 使用自定义lazy_list类型，就像 ehemient 说的（除了他的解决方案有点坏）：

  type 'a lazy_list =
      | Nil
      | Cons of 'a * 'a lazy_list
  
  let head = function
      | Nil -> failwith "Cannot extract head of empty list"
      | Cons (h, _) -> h
  
  let tail = function
      | Nil -> failwith "Cannot extract tail of empty list"
      | Cons (_, t) -> t
  

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

  let make_lazy_list initial next =
      let lazy_list current () =
          let result = !current in
          current := (next !current); result
      in lazy_list (ref initial)
  
  let naturals = make_lazy_list 0 (function i -> i + 1)
  

  如果你这样做

  print_int (naturals ());
  print_int (naturals ());
  print_int (naturals ())
  

  您将获得以下输出：

  0
  1
  2