Re: Lazy lists?

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




-------------------------------------------------------
This SF.Net email is sponsored by:
Sybase ASE Linux Express Edition - download now for FREE
LinuxWorld Reader's Choice Award Winner for best database on Linux.
http://ads.osdn.com/?ad_id=5588&alloc_id=12065&op=click