Re: [Caml-list] yet another question on lazy lists

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

> Date: Sat, 6 Jul 2002 14:22:52 -0400
> From: William Lovas <wlovas@stwing.upenn.edu>
> 
> On Sat, Jul 06, 2002 at 05:26:33PM +0200, Pierre Weis wrote:
> > >  Does this mean
> > > that my "stream_cons" function is useless?
> > >
> > > Thanks in advance,
> > > 
> > > Mike
> > 
> > No. It means you cannot always use it in place of a constructor
> > application. Note that a similar phenomenon occurs for pattern
> > matching: constructors are mandatory, you cannot subtitute them by
> > equivalent function calls!
> 
> Actually, i think stream_cons may be useless, due to OCaml's eager
> evaluation strategy.  If you try to delegate the recursion to a function
> call, the following happens:
> 
>     # let rec constant n = stream_cons n (constant n);;
>     val constant : 'a -> 'a stream = <fun>
>     # constant 1;;
>     Stack overflow during evaluation (looping recursion?).
> 
> ... but the constructor still works:
> 
>     # let rec constant n = Cons (n, lazy (constant n));;
>     val constant : 'a -> 'a stream = <fun>
>     # constant 1;;
>     - : int stream = Cons (1, {contents = Lazy.Delayed <fun>})
> 
> The second argument needs to be treated lazily (which it is, explicitly, 
> using the Cons constructor call), but stream_cons will never achieve that,
> unless i'm missing something.
> 
> William

You're right.  I realized this shortly after sending out the question.
Because of ocaml's eager evaluation, the whole point of 'stream_cons' is
thwarted by writing it as a function, because by definition all the
arguments to the function are evaluated.  I got confused because I was
trying to imitate some scheme code from SICP in ocaml, and there was (what
looked like) a 'stream-cons' function in the SICP code.  It turns out that
'stream-cons' has to be implemented as a macro in scheme (a point glossed
over in SICP).

> 
> P.S. Michael, why not call your type something like `lazy_list', instead of
> `stream'?  The latter conjures up images of stateful Stream.t's, for me at
> least.  Just a thought!

Right again.  This is SICP terminology.  I'll change it if I post any more
questions on this subject to this list.

Thanks for your input (and to Pierre Weis for his explanation of the error
message).

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