English version
Accueil     À propos     Téléchargement     Ressources     Contactez-nous    

Ce site est rarement mis à jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml à l'adresse ocaml.org.

Browse thread
Re: [Caml-list] Iterators and lazy lists
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2001-07-11 (11:09)
From: Willem Duminy <wduminy@w...>
Subject: Re: [Caml-list] Iterators and lazy lists

I am new to OCAML, and I do not know Python.  I do not know what is
the "preferred" way to do lazy lists.  Maybe someone can comment on my
code and tell me a better way to handle lazy lists.

I have translated a lazy list solution (which I read in some article)
from ML to OCAML.  I think it works well, here is the code. The
function filterq may be what you are looking for.


type 'a seq = Nil | Cons of 'a * (unit->'a seq);;

let head = function
  Cons(h,t) -> h
  |  Nil -> raise (Failure "sequence is empty");;

let tail = function
  Cons(_,t) -> t()
   Nil -> raise (Failure "sequence is empty");;

(* An increasing sequence of integers starting from k: *)
let rec from k = Cons(k, fun () -> from (k+1));;

(* takeq converts a lazy list to a normal list *)
let rec takeq (n, sq) =
  if n = 0 then []
  else match sq with
    Nil -> []
  | Cons(x,xf) -> x::takeq(n-1,xf());;

(* The squares function shows how construct a lazy list using "from"
let rec squares sq = match sq with
  Nil -> Nil
  | Cons(x,xf) -> Cons(x*x,fun () -> squares(xf()));;

(* Here is a function that adds the elements of 2 lazy lists to
   a third list *)
let rec addq (sq1, sq2) = match (sq1,sq2) with
  (Nil,_) -> sq2
| (_,Nil) -> sq1
| (Cons(x1,xf1),Cons(x2,xf2)) ->
      Cons(x1+x2,fun () -> addq(xf1(),xf2()));;

(* Appendq builds a new list from a finiate list and another list *)
let rec appendq (sq1,sq2) = match (sq1,sq2) with
  (Nil,_) -> sq2
  | (Cons(x1,xf1),_) ->
    Cons(x1,fun () -> appendq (xf1(),sq2));;

(* Iterates generates a sequence [x, f(x), f(f(x)), f(f(f(x))) ...] *)
let rec iterates f x = Cons(x,fun () -> iterates f (f x));;

  filterq returns the items in the list that matched the predicate f
let rec filterq f sq  = match sq with
  Nil -> Nil
  | Cons(x,xf) ->
  if (f x) then
    Cons(x,fun () -> filterq f (xf ()))
  filterq f (xf ());;

(* Here we create the sequence of prime numbers as an example *)
let sift p = filterq (fun x -> x mod p <> 0);;
let rec sieve sq = match sq with
  Nil -> Nil
| Cons(x,xf) -> Cons(x, fun () -> sieve(sift x (xf())));;
let primes = sieve (from 2);;
(* Show the first ten primes as a normal list *)

chop n sq chops the first n elements from the sequence and returns
the rest of the sequence.  An error message is displayed when
sq has less elements than n.  It may be called with n <= 0.
In this case the sequence will remain unchanged *)
let rec chop n sq = match sq with
  Nil ->
    raise (Failure "The lazy list is too short")
  |  Cons (h, tl) ->
	if n = 0 then tl ()
	else chop (n-1) (tl ());;

(* Testing chop *)
(* 11 and higher *)
let lst_11_to_15 = takeq (5, chop 10 (from 0));;
(* The 100th and later squares *)
let square_100_plus = takeq (5, chop 99 (squares (from 0)));;
(* The 201st and later prime numbers *)
let bigger_primes = takeq (10, chop 200 primes);;


On Mon, 09 Jul 2001 22:32:31 -0700 Alexander V. Voinov
(avv@quasar.ipa.nw.ru) wrote:

>Hi All,
>I didn't fully understand from the docs, what is the preferred way to
>generate lazy (e.g., computed on demand) lists in OCaml, like what is
>achieved in Python via __getitem__. Should I generate a stream for
>or define an iterator like in C++?
>I'd like to find an analog of the following in Python:
>for item in myCustomDict.lazyItems():
>	if found(item):
>		break
>Certainly, a recursive traversal solution is preferred over a looping
>Thank you in advance
>Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ:
>To unsubscribe, mail caml-list-request@inria.fr  Archives:

Mid-year intake! Enrol NOW & stand a chance to win 25% discount
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr