Ocaml: Lazy Lists

Question

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

1 2 4 8 16 32

Guardhouse

Do you mean some particular implementation of lazy lists, or just the general concept? Also, do you actually need lazy lists (where values, once computed, are memoized), or do you really just want a stream (where values aren't memoized, and which can therefore only be read once)? – Murdoch

Answer 1

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

Shandy

Answer 2

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.

Algorithm

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
  

Lorie

What part of my lazy_list is broken? I didn't test it when I was writing it, and I'm definitely more familiar with Haskell and SML than OCaml, but I tested it just now and it works, on OCaml 3.11.1. Streams is mostly because OP added a comment to the question asking for streams. – Shandy

Woops, you're right, I really really misread that... Plus I didn't see the comment about using streams. Next time I'll put my glasses on :s. – Lorie

Answer 4

Answer from the distant future...

OCaml 4.07 introduced the Seq module which can facilitate this.

# 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]

Subaxillary