Re: [Caml-list] more on lazy lists

[Damien Doligez <damien.doligez@inria.fr>]

From: Michael Vanier <mvanier@cs.caltech.edu>


>Now I understand why references are used internally for lazily evaluated
>values; it's for memoization i.e. so that a particular value doesn't have
>to be recomputed after it's been computed once.

This is the essence of lazy evaluation.


>  I'm having an odd problem, though; consider this code:

[...]


Your "stream_map2" function is not lazy enough: it will unnecessarily
force the tail of the stream.  You need to write it as follows:


  let rec stream_map2 proc s1 s2 =
    match (s1, s2) with
      (Cons (x1, y1), Cons (x2, y2)) ->
        Cons ((proc x1 x2), lazy (stream_map2 proc (Lazy.force y1)
                                                   (Lazy.force y2)))
    | _ -> raise Invalid_operation

Note that the calls to Lazy.force are inside the argument of lazy.
There is the same problem in your "take" function.


>let integers = 
>  let rec ints () =
>    Cons (1, lazy (add_streams ones (ints ())))
>  in
>  ints ()

Now it works, but it is very inefficient (quadratic complexity)
because you rebuild a new "ints" stream at each call to add_streams.
Better to do it this way:

  let rec integers =  Cons (1, lazy (add_streams ones integers));;


-- Damien
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners