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