Version française
Home     About     Download     Resources     Contact us    
Browse thread
Generators/iterators and lazy evaluation?
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Jon Harrop <jon@f...>
Subject: Re: [Caml-list] Generators/iterators and lazy evaluation?
On Wednesday 04 April 2007 17:33, Raj B wrote:
> A generator in Python can be thought of as an arbitrarily generated
> 'lazy list'. As an example
> the following is a generator capable of generating powers of 2 upto a
> max value.
>
> def pow2(max):
>     start = 0
>     while (start .lt. max):
>        yield 2^start
>        start += 1
>
> The 'yield' statement is the point where the function returns the
> next value and suspends itself until the next time it is 'forced'. At
> that time it resumes execution where it left off.
>
> OCaml makes this particularly hard to implement this due to lack of
> 'control flow' features

Might I suggest deferring judgement until you have seen some OCaml solutions.

$ ocaml -rectypes camlp4o.cma
        Objective Caml version 3.10.0+beta

        Camlp4 Parsing version 3.10.0+beta

#

Use a lazy list sum type:

# type 'a llist = Nil | Cons of 'a * 'a llist lazy_t;;
type 'a llist = Nil | Cons of 'a * 'a llist lazy_t

# let rec pow2 ?(i=1) n =
    if n>0 then Cons(i, lazy(pow2 ~i:(2*i) (n-1))) else Nil;;
val pow2 : ?i:int -> int -> int llist = <fun>

For example:

# let rec list_of = function
    | Nil -> []
    | Cons(h, t) -> h :: list_of(Lazy.force t);;
val list_of : 'a llist -> 'a list = <fun>

# list_of(pow2 10);;
- : int list = [1; 2; 4; 8; 16; 32; 64; 128; 256; 512]

Use an inferred lazy list type (polymorphic variant):

# let rec pow2 ?(i=1) n =
    if n>0 then `Cons(i, lazy(pow2 ~i:(2*i) (n-1))) else `Nil;;
val pow2 : ?i:int -> int -> ([> `Cons of int * 'a lazy_t | `Nil ] as 'a) =
  <fun>

Return a lazy tail (using -rectypes):

# let rec pow2 ?(i=1) n =
    if n>0 then Some(i, lazy(pow2 ~i:(2*i) (n-1))) else None;;
val pow2 : ?i:int -> int -> ((int * 'a lazy_t) option as 'a) = <fun>

Return a functional tail (using -rectypes):

# let rec pow2 ?(i=1) j n () =
    if n>0 then Some(i, pow2 ~i:(2*i) (n-1)) else None;;
val pow2 : ?i:int -> int -> (int -> unit -> (int * 'a) option as 'a) = <fun>

Return a lazy stream (using camlp4 stream parsing syntax extension):

# let rec pow2 ?(i=1) n =
    if i<n then [<'i; pow2 ~i:(2*i) (n-1)>] else [<>];;
val pow2 : ?i:int -> int -> int Stream.t = <fun>

The moral is: don't try to write idiomatic Python in OCaml.

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
OCaml for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists