Re: [Caml-list] lazy lists

[Marius Nita <marius@cs.pdx.edu>]

Jonathan Roewen wrote:
> Hi,
> 
> Is the underlying implementation of the builtin lists in OCaml lazy?
> If not, is performance the reason for them not being lazy? I think
> lazy lists are a very strong point of Haskell, and am wondering if
> there's a lazy list implementation with all the standard list
> operations in the case that lists aren't lazy in OCaml.
> 
> Also, if they aren't, can someone give me some insight into the
> reasons INRIA chose not to?

It's not just a question of the "underlying implementation." OCaml and
Haskell use the same list definition:

   type 'a list = Cons of 'a * 'a list | Nil

but in Haskell it is lazy due to Haskell's lazy evaluation semantics.
OCaml has a strict evaluation semantics, so its lists, as defined above,
are strict.

If OCaml had chosen to implement lists lazily "behind the scenes," this
would be easily observable (and very counter-intuitive!) due to OCaml's
imperative features:

   let f _ = 5
   in f [print_string "calling f\n"]

would produce no output.

The good news is that you can define your own lazy data structures
pretty easily. OCaml offers the Lazy module, which makes working with
lazy suspensions easier.

	marius