source: http://www.msu.edu/~shawjef3/lazylist.ml

Today I'm working on making caml work with lazy lists. Lazy evaluation is the default in haskell and its lists are lazy. However, in Caml, laziness has to be "turned on" with the lazy keyword or the use of the Lazy module. http://caml.inria.fr/pub/docs/manual-ocaml/libref/Lazy.html
My initial goal is to make something like the following work in Caml. It is intended to be a list containing the entire Fibonacci sequence.

let fib = let rec aux a b = a::(aux b (a+b)) in (aux 0 1)

Ocaml attempts to create the entire list at once, but this causes a stack overflow. If we can properly use the lazy keyword and Lazy module, something like the following should work:

#List.hd fib;;
- : int = 0
#List.hd fib;;
- : int = 0
#List.hd (List.tl fib);;
- : int = 1

I repeated "List.hd fib" to show that, unlike streams, lazy list functions are not destructive.

You cannot use the built-in caml list type. The reason is that you need the list to be constructed in a lazy way, something like:

# let lazycons a b = lazy (a::b);;
val lazycons : 'a -> 'a list -> 'a list lazy_t = <fun>

Notice that the second argument requires that the list be *fully constructed*. To use :: on a lazy list you have to do ::(Lazy.force b), which defeats the purpose of using lazy lists in the first place. Therefore we have to make a custom list type.

type 'a t = Cons of 'a * ('a t) Lazy.t | Nil

let cons a b = Cons (a,b)

The type of cons for lazy lists is
- : 'a -> 'a t Lazy.t -> 'a t = <fun>

Now for hd and tl and nth:

# let hd l =
match l with
   Nil -> failwith "Lazylist.hd"
 | Cons (a,b) -> a;;
   val hd : 'a t -> 'a = <fun>
# let tl l =
match l with
   Nil -> failwith "Lazylist.tl"
 | Cons (a,b) -> Lazy.force b;;
   val tl : 'a t -> 'a t = <fun>
# let rec nth l n =
match l with
   Nil -> failwith "Lazylist.nth"
 | Cons (a,b) ->
if n=0 then a else
  if n>0 then nth (Lazy.force b) (n-1) else
    invalid_arg "Lazylist.nth";;
         val nth : 'a t -> int -> 'a = <fun>

Now for a proper handling of the fibonacci sequence!

# let fib =
let ( >> ) = cons in
let rec aux a b =
 a >> lazy (aux b (a+b))
in
 (aux 0 1);;
       val fib : int t = Cons (0, <lazy>)
# hd fib;;
- : int = 0
# hd fib;;
- : int = 0
# tl fib;;
- : int t = Cons (1, <lazy>)
# hd (tl fib);;
- : int = 1
# nth fib 10;;
- : int = 55

YAY!

Now for some warnings. Some functions over lazy lists might not ever return a result! For instance,

Lazylist.iter (Printf.printf "%i\n") fib

will output to stdout ALL of the numbers in the Fibonacci sequence, until the int type overflows and the list becomes meaningless. At that point it will simply output thousands and thousands of integers for ever and ever.

Likewise, Lazylist.mem or Lazylist.exists might search forever without ever finding an end of the list or an appropriate member.

Another thing to keep in mind is that functions over lazy lists don't need to be tail-recursive to remain small in memory. This makes the code for certain functions more clear.

By the way, if anyone could help make the "partition" function lazy, please let me know. Perhaps other functions could be made lazy that I missed.

Enjoy!

Jeff