Ocaml: Lazy Lists

Question

How can I make a lazy list representing a sequence of doubling numbers? Example:

1 2 4 8 16 32

Answer 1

Also, there is a lazy list module called Cf_seq in my OCaml Network Application Environment Core Foundation. In fact, I wrote a whole passle of functional data structures. It's all available under a 2-clause BSD license. Enjoy.

Update: the code has been renamed "Oni" and it's now hosted at BitBucket. You can also use the GODI package for it.

Answer 2

The great blog enfranchised mind has a great article on this topic:

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

You can also check out http://batteries.forge.ocamlcore.org/doc.preview%3Abatteries-beta1/html/api/Lazy%5Flist.html

which is the standard library for dealing with this.

This question is also very similar to this question:

What OCaml libraries are there for lazy list handling?

Answer 3

If you want to do it by hand, I'd say you have to main options:

• Use a custom lazy_list type, like ephemient said (except his solution is a bit broken):

  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
  

• Use a kind of thunk (like the thing used to implement lazy evaluation in a language that does not support it). You define your list as a function unit -> 'a that says how to get the next element from the current one (no need to use streams for that). For example, to define the list of all natural integers, you can do

  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)
  

  The if you do

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

  you will get the following output:

  0
  1
  2
  

Answer 4

Using streams:

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

or

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

Using a custom lazy_list type:

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