Re: [Camllist] Iterators and lazy lists
 Willem Duminy
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:  20010711 (11:09) 
From:  Willem Duminy <wduminy@w...> 
Subject:  Re: [Camllist] Iterators and lazy lists 
Hi, 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. CODE STARTS HERE 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(n1,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 produce 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 ())) else 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 *) takeq(10,primes);; (* 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 (n1) (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);; CODE ENDS HERE 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 this, >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 >one. > >Thank you in advance > >Alexander > >Bug reports: http://caml.inria.fr/bin/camlbugs FAQ: http://caml.inria.fr/FAQ/ >To unsubscribe, mail camllistrequest@inria.fr Archives: http://caml.inria.fr ________________________________________________________________ Midyear intake! Enrol NOW & stand a chance to win 25% discount http://www.milpark.co.za  Bug reports: http://caml.inria.fr/bin/camlbugs FAQ: http://caml.inria.fr/FAQ/ To unsubscribe, mail camllistrequest@inria.fr Archives: http://caml.inria.fr