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
|
