[Caml-list] lazy lists

[Caml-list] lazy lists

[Michael Vanier]

What's the best way to write a lazy list data type in ocaml?  I've been
playing around with this datatype (from an old mailing list posting):

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

but I can't figure out how to write a "stream_cons" function.  Also, it
appears that the Lazy.t data type uses references; why is this?

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] lazy lists

[Remi VANICAT]

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

> What's the best way to write a lazy list data type in ocaml?  I've been
> playing around with this datatype (from an old mailing list posting):
>
> type 'a stream =
>   Nil
> | Cons of 'a Lazy.t * 'a stream Lazy.t
>
> but I can't figure out how to write a "stream_cons" function.  

you mean :

let stream_cons x y =
  lazy Cons (x, y)


> Also, it
> appears that the Lazy.t data type uses references; why is this?

Because it is the standard way of doing it with a non lazy
language... 
-- 
Rémi Vanicat
vanicat@labri.u-bordeaux.fr
http://dept-info.labri.u-bordeaux.fr/~vanicat
-------------------
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] lazy lists

[Daniel de Rauglaudre]

Hi,

On Wed, May 02, 2007 at 12:03:29PM +0200, Loup Vaillant wrote:

> Regular streams are destructive. I was talking about "functional"
> ones. I didn't try them myself, but the manual says one can perform
> left recursion with them (thanks to their non destructive nature).

Use camlp4s : the library "fstream" and the syntax extension "pa_fstream"
are still there. Access and download from my home page below.

-- 
Daniel de Rauglaudre
http://pauillac.inria.fr/~ddr/index-english.html

Re: [Caml-list] lazy lists

[Loup Vaillant]

2007/5/2, Nicolas Pouillard <nicolas.pouillard@gmail.com>:
> On 5/1/07, Jon Harrop <jon@ffconsultancy.com> wrote:
> > On Tuesday 01 May 2007 16:47, Loup Vaillant wrote:
> > > The equivalent is the functionnal streams, describe briefly in the
> > > camlp4 manual.
> >
> > Aren't ocaml stream destructive?
>
> Yes they are.

Regular streams are destructive. I was talking about "functional"
ones. I didn't try them myself, but the manual says one can perform
left recursion with them (thanks to their non destructive nature).
Mind the pattern matching, though: it is quite different from the one
used with regular streams.

the syntax looks like:

let f s = match s with fparser (* and not just 'parser' *)
...

If I remember well.

Loup Vaillant

Re: [Caml-list] lazy lists

[Nicolas Pouillard]

On 5/1/07, Jon Harrop <jon@ffconsultancy.com> wrote:
> On Tuesday 01 May 2007 16:47, Loup Vaillant wrote:
> > The equivalent is the functionnal streams, describe briefly in the
> > camlp4 manual.
>
> Aren't ocaml stream destructive?

Yes they are.

-- 
Nicolas Pouillard

Re: [Caml-list] lazy lists

[Jon Harrop]

On Tuesday 01 May 2007 16:47, Loup Vaillant wrote:
> The equivalent is the functionnal streams, describe briefly in the
> camlp4 manual.

Aren't ocaml stream destructive?

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
The F#.NET Journal
http://www.ffconsultancy.com/products/fsharp_journal/?e

Re: [Caml-list] lazy lists

[Loup Vaillant]

2007/5/1, Yitzhak Mandelbaum <yitzhak@research.att.com>:
> Hi,
>
> Does anyone have/know of a lazy list module for ocaml? I couldn't find
> anything on the hump.

The equivalent is the functionnal streams, describe briefly in the
camlp4 manual.

Another possibilty is to code it yourself. I think you can imitate
most of the List module code.

Regards,
Loup

Re: [Caml-list] lazy lists

[Jun Mukai]

Hi, Rich

> What you probably want are Streams (in camlp4).  This thread is
> interesting:

It is true that Stream is lazy evaluated, but Stream is not functional
at all. We cannot use Streams as same as lists in Haskell. For example,
--
# let s = [< '1 >];;
val s : int Stream.t = <abstr>
# let f = parser
  | [< 'n >] -> n
  | [< >] -> raise Not_found;;
val f : 'a Stream.t -> 'a = <fun>
# f s;;
- : int = 1
# f s;;
Exception: Not_found.
--

This code confuses many users (such like me).


BTW, I wrote a lazy list implementation in pure OCaml. It uses lazy
mechanism of OCaml and has some useful functions like haskell.
If you are interested in, see 
http://www.jmuk.org/prog/lazyList.tar.gz

The implementation is so naive that its performance will be low. And
it has no camlp4 extentions.
Feel free to use, but without any warranty.

Best Regards,
--
Jun Mukai

Re: [Caml-list] lazy lists

[Richard Jones]

On Fri, Aug 26, 2005 at 11:56:33AM +1200, Jonathan Roewen wrote:
> 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.

What you probably want are Streams (in camlp4).  This thread is
interesting:

http://caml.inria.fr/pub/ml-archives/caml-list/2004/09/9d5e1141c4018b995480ce1630f4879c.en.html

Rich.

-- 
Richard Jones, CTO Merjis Ltd.
Merjis - web marketing and technology - http://merjis.com
Team Notepad - intranets and extranets for business - http://team-notepad.com

Re: [Caml-list] lazy lists

[Marius Nita]

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

[Caml-list] lazy lists

[Jonathan Roewen]

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?

Kindest Regards,

Jonathan