From: Koprowski, A. <A.K<oprowski@tu...>  20041109 13:56:04
Attachments:
Message as HTML

Hello, Anybody has any idea of some lazy lists implementation in Occaml?=20 Initially I thought that ExtLib's Enums will do the work but what I don't like about them is that operations like map, filter etc. consume the enumeration. Now, for me it's crucial to have a partition function. So let's say I have list 'l' and I want to partition it into 'm' and 'n'. I want everything to be computed in a lazy fashion so forcing 'l' is out of question. Also assume that computation yielding 'l' is expensive so cloning it and using to produce 'm' and 'n' separately (thus computing twice) is also not on option. Can I do it somehow with Enums? And if not: does anybody know, hopefully positive, answer to the question posed at the beginning of this post? Thanks in advance for any help, Regards, Adam Koprowski =20   A.Koprowski@..., ICQ: 3204612   The difference between impossible and possible lies in determination   Tommy Lasorda   =20 
From: Martin Jambon <martin_jambon@em...>  20041109 18:50:09

On Tue, 9 Nov 2004, Koprowski, A. wrote: > Hello, > > Anybody has any idea of some lazy lists implementation in Occaml? > > Initially I thought that ExtLib's Enums will do the work but what I > don't like about them is that operations like map, filter etc. consume > the enumeration. Now, for me it's crucial to have a partition function. > So let's say I have list 'l' and I want to partition it into 'm' and > 'n'. I want everything to be computed in a lazy fashion so forcing 'l' > is out of question. Also assume that computation yielding 'l' is > expensive so cloning it and using to produce 'm' and 'n' separately > (thus computing twice) is also not on option. Can I do it somehow with > Enums? And if not: does anybody know, hopefully positive, answer to the > question posed at the beginning of this post? I just played a little, and here is the result, just for fun (you probably can find nicer implementations somewhere on the web, and I don't know what you can do with enums here): type 'a lazy_list = Cons of 'a Lazy.t * 'a lazy_list Lazy.t  Empty type 'a t = 'a lazy_list Lazy.t let rec force l = match Lazy.force l with Cons (x, rest) > Lazy.force x :: force rest  Empty > [] let to_list = force let rec of_list l = lazy (match l with [] > Empty  x :: rest > Cons (lazy x, of_list rest)) let rec map f l = lazy (match Lazy.force l with Cons (x, rest) > Cons (lazy (f (Lazy.force x)), map f rest)  Empty > Empty) let rec filter f l = let rec find_node l = match Lazy.force l with Cons (x, rest) > if f (Lazy.force x) then Cons (x, filter f rest) else find_node rest  Empty > Empty in lazy (find_node l) let partition f l = let l' = map (fun x > (x, f x)) l in let m = map fst (filter (fun (x, b) > b) l') in let n = map fst (filter (fun (x, b) > not b) l') in (m, n) # let (m,n) = partition (fun x > print_int x; x <= 4) (of_list [1;3;5;2;7]);; val m : int lazy_list Lazy.t = <lazy> val n : int lazy_list Lazy.t = <lazy> # to_list m;; 13527 : int list = [1; 3; 2] # to_list n;;  : int list = [5; 7] # to_list m;;  : int list = [1; 3; 2] Martin  Martin Jambon, PhD Researcher in Structural Bioinformatics since the 20th Century The Burnham Institute http://www.burnham.org San Diego, California 
From: Nicolas Cannasse <warplayer@fr...>  20041109 19:02:58

> Anybody has any idea of some lazy lists implementation in Ocaml? Well partition could be easily added to Enum Something like : val partition : ('a > bool) > 'a Enum.t > 'a Enum.t * 'a Enum.t The implementation itself is quite easy : let partition f t = let mem_true = Queue.create() in let mem_false = Queue.create() in let next b () = try Queue.pop (if b then mem_true else mem_false) with Queue.Empty > let rec loop() = let x = t.next() in if f x = b then x else begin Queue.push x (if b then mem_false else mem_true); loop(); end; in loop() in from (next true) , from (next false) But I'm not sure we should add it to Enum module because it creates a unwelcomed dependency on the Queue module. Regards, Nicolas Cannasse 