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

伟大的博客 enfranchied mind 有一篇关于这个主题的很棒的文章：

http://enfranchiseddemind.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

另外，在我的

OCaml 网络应用环境

Core Foundation 中有一个名为Cf_seq 的惰性列表模块。事实上，我写了一整套函数式数据结构。这一切都在 2-clause BSD 许可下可用。享受吧。

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

Answer 4

如果你想手工做，我会说你必须主要选择：

• 使用自定义

  lazy_list

  类型，就像 ephemient 说的（除了他的解决方案有点破）：

  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
  

Answer 5

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

OCaml 4.07 引入了

Seq

模块 可以促进这一点。

# let lazy_list start f =
    let rec aux start f () = 
      Seq.Cons (start, aux (f start) f) 
    in
    aux 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]