(* 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