[Caml-list] more on lazy lists

[Michael Vanier <mvanier@cs.caltech.edu>]

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