[Caml-list] more on lazy lists

[Caml-list] more on lazy lists

[Michael Vanier]

OK, I've been playing around with the lazy evaluation feature of ocaml.
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.  I'm having an odd problem,
though; consider this code:

(* Definition of lazy list type. *)

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

exception Invalid_operation

let rec stream_for_each proc s =
  match s with
    Nil -> ()
  | Cons (x, y) ->
      (proc x;
       stream_for_each proc (Lazy.force y))

(* Take the first 'n' elements from a stream. *)

let rec take n s =
  match s with
    Nil ->
      (match n with
        0 -> Nil
      | n -> raise Invalid_operation)
  | Cons (x, y) ->
      (match n with
        0 -> Nil
      | n when n < 0 -> raise Invalid_operation
      | _ ->
          let next = Lazy.force y in
          Cons (x, lazy (take (n - 1) next)))

let print_stream n s =
  stream_for_each (fun x -> Printf.printf "%i\n" x) (take n s)

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

let add_streams s1 s2 =
  stream_map2 (+) s1 s2

(* Make a constant stream. *)

let rec constant n =
  Cons (n, lazy (constant n))

let ones = constant 1


So far, so good.  Now consider this:


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

print_stream 10 integers


This generates the error message: 

"Stack overflow during evaluation (looping recursion?)."

I don't understand why this happens.  Shouldn't the recursive call to
"ints ()" be deferred until it's required?  I borrowed this example from
SICP, so it works in scheme, for what that's worth.

Mike

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

Re: [Caml-list] more on lazy lists

[Damien Doligez]

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