Commits

camlspotter committed 442df9b

added a lazy list module, Stream

Comments (0)

Files changed (3)

    monad_intf
    monad
    option
+   stream
    xlist
    xhashtbl
    xstring
+open Xlazy
+
+type 'a t = 'a desc lazy_t
+
+and 'a desc =
+  | Cons of 'a * 'a t
+  | Null
+
+let null = from_val Null
+let cons v t = from_val (Cons (v, t))
+let (^^) = cons
+let singleton v = cons v null
+
+let peek = function
+  | lazy Null -> None
+  | lazy (Cons (v, t)) -> Some (v, t)
+
+let is_null = function
+  | lazy Null -> true
+  | _ -> false
+
+let rec create f st = lazy (match f st with
+  | Some (v, st) -> Cons (v, create f st)
+  | None -> Null)
+
+let rec of_list = function
+  | [] -> null
+  | x::xs -> cons x (of_list xs)
+
+let to_list t = 
+  let rec to_list st = function
+    | lazy Null -> List.rev st
+    | lazy (Cons (v, t)) -> to_list (v :: st) t
+  in
+  to_list [] t
+  
+let rec iter f = function
+  | lazy Null -> ()
+  | lazy (Cons (v, t)) -> f v; iter f t
+
+let rec fold_right f lst st = match lst with
+  | lazy Null -> st
+  | lazy (Cons (v, lst)) -> f v (fold_right f lst st)
+
+let rec map f lst = lazy (match lst with
+  | lazy Null -> Null
+  | lazy (Cons (v, lst')) -> Cons (f v, map f lst'))
+
+let rec append xs ys = lazy (match xs with
+  | lazy Null -> !!ys
+  | lazy (Cons (x, xs)) -> Cons (x, append xs ys))
+      
+  
+
+(* [t2] must be a postfix of [t1] otherwise, it loops forever *)
+let rev_between t1 t2 =
+  let rec loop st t =
+    if t == t2 then st (* CR jfuruse: we cannot always use pointer eq *)
+    else 
+      match t with
+      | lazy (Cons (v, t')) -> loop (v::st) t'
+      | lazy Null -> st
+  in
+  loop [] t1
+
+let between t1 t2 = List.rev (rev_between t1 t2)
+
+(** This is a lazy list basically, but its elements and nil can have extra information. *)
+
+type 'a t = 'a desc lazy_t
+
+and 'a desc = 
+  | Cons of 'a * 'a t
+  | Null 
+
+(** Constructors *)
+val null : 'a t
+(** a constant null *)
+
+val cons : 'a -> 'a t -> 'a t
+val (^^) :  'a -> 'a t -> 'a t
+(** same as [cons] *)
+val singleton : 'a -> 'a t
+
+val create : ('st -> ('a * 'st) option) -> 'st -> 'a t
+(** Pure functional creator *)
+
+(** Deconstructors *)
+
+val peek : 'a t -> ('a * 'a t) option
+(** You can use match with lazy pattern instead of [peek] *)
+
+val is_null : 'a t -> bool
+(** null check *)
+
+(** Conversions *)
+
+val to_list : 'a t -> 'a list
+(** Conversion from a lazy stream to a strict list.
+    Do not use against inifinite streams. *)
+
+val of_list : 'a list -> 'a t
+(** Conversion from a strict list to a lazy stream. 
+    The conversion itself is done strictly: the result has no reference to the original list *)
+
+(** Misc functions *)
+
+val iter : ('a -> unit) -> 'a t -> unit
+val fold_right : ('a -> 'b -> 'b) -> 'a t -> 'b -> 'b
+val map : ('a -> 'b) -> 'a t -> 'b t
+val append : 'a t -> 'a t -> 'a t
+
+(** Inpure hacks *)
+
+val rev_between : 'a t -> 'a t -> 'a list
+val between : 'a t -> 'a t -> 'a list
+  (** Get elements between two points of the *same* stream.
+
+      The first argument of [rev_between] and [between] must point the former element of the stream
+      than the second argument. Otherwise, the behaviour of [rev_between] and [between] are not specified:
+      a wrong result or memory exhaustion by an infinite loop.
+  *)