Re: [Caml-list] Streams

[Martin Jambon <martin1977@laposte.net>]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 975 bytes --]

On Thu, 10 Aug 2006, Error404 wrote:

> Hi,
>
> I'm looking for some streams related tutorial or any other info.
> By stream i mean something like this (I don't know exact definition):
>
> open Lazy;;
> type 'a stream = Nil | Cons of 'a Lazy.t * 'a stream Lazy.t;;
>
> (* For example stream of 'integers from x' would look like this: *)
>
> let rec intsfrom x =
>  Cons(lazy x,lazy (intsfrom (x+1)));;
>
> If you know any www/book or anything on this kind of streams please mail me (error92@tlen.pl).
> Many thanks.

I call this a lazy list. Anyway, I use the following definition:

   type 'a l = Empty | Cons of 'a * 'a t
   and 'a t = 'a l lazy_t   (* only one lazy object per cell *)

See attachment for the full implementation.

You can manipulate such lists like real lists, only the syntax is less 
comfortable. They are different from streams in the sense of the standard 
Stream module, which are mutable.


Martin

--
Martin Jambon, PhD
http://martin.jambon.free.fr

[-- Attachment #2: Type: TEXT/PLAIN, Size: 2295 bytes --]

(* lazy lists *)

type 'a l = Empty | Cons of 'a * 'a t
and 'a t = 'a l lazy_t

let empty = lazy Empty
let is_empty l = Lazy.force l = Empty

let rec force l =
  match Lazy.force l with
      Empty -> ()
    | Cons (hd, tl) -> force tl

let hd l =
  match Lazy.force l with
      Empty -> invalid_arg "Lizt.hd"
    | Cons (x, _) -> x

let tl l =
  match Lazy.force l with
      Empty -> invalid_arg "Lizt.tl"
    | Cons (_, x) -> x

let peek1 l = 
  match Lazy.force l with
      Empty -> None
    | Cons (x, _) -> Some x

let peek2 l =
  match Lazy.force l with
      Empty -> None
    | Cons (x1, l) -> 
	match Lazy.force l with
	    Empty -> None
	  | Cons (x2, l) -> Some (x1, x2)

let peek3 l =
  match Lazy.force l with
      Empty -> None
    | Cons (x1, l) -> 
	match Lazy.force l with
	    Empty -> None
	  | Cons (x2, l) -> 
	      match Lazy.force l with
		  Empty -> None
		| Cons (x3, l) -> Some (x1, x2, x3)


let rec of_list l =
  lazy (match l with
	    [] -> Empty
	  | hd :: tl -> (Cons (hd, of_list tl)))

let rec to_list l =
  match Lazy.force l with
      Empty -> []
    | Cons (hd, tl) -> hd :: to_list tl

let from f =
  let rec make f i =
    lazy (match f i with
	      None -> Empty
	    | Some x -> Cons (x, make f (i+1))) in
  make f 0

let rec append l1 l2 =
  lazy (match Lazy.force l1 with
	    Cons (hd, tl) -> Cons (hd, (append tl l2))
	  | Empty -> Lazy.force l2)

let rec iter f l =
  match Lazy.force l with
      Empty -> ()
    | Cons (hd, tl) -> f hd; iter f tl

let rec map f l =
  lazy (match Lazy.force l with
	    Empty -> Empty
	  | Cons (hd, tl) -> Cons (f hd, map f tl))

let filter f l =
  let rec loop f l =
    match Lazy.force l with
	Empty -> lazy Empty
      | Cons (hd, tl) -> 
	  if f hd then lazy (Cons (hd, loop f tl))
	  else loop f tl in
  lazy (Lazy.force (loop f l))

let optmap f l =
  let rec loop f l =
    match Lazy.force l with
	Empty -> lazy Empty
      | Cons (hd, tl) -> 
	  match f hd with
	      Some y -> lazy (Cons (y, loop f tl))
	    | None -> loop f tl in
  lazy (Lazy.force (loop f l))

let rec fold_left f accu l =
  match Lazy.force l with
      Empty -> accu
    | Cons (hd, tl) -> fold_left f (f accu hd) tl