Source

ocaml-lib / flist.ml

(**
   Functional lists for efficient appending of lists.

   Author: Sebastien Ferre
*)


type 'a flist = Cons of 'a * 'a flist | Nil | Rest of 'a flist ref

type 'a t = 'a flist * 'a flist ref

let nil () =
  let r = ref Nil in
  (Rest r, r)

let cons x (l, r) = (Cons (x, l), r)

let rec hd (l, r) =
  match l with
  | Nil -> raise (Invalid_argument "FList.hd")
  | Cons (x, _) -> x
  | Rest l_opt -> hd (!l_opt, r)

let rec tl (l, r) =
  match l with
  | Nil -> raise (Invalid_argument "FList.tl")
  | Cons (_, l) -> (l, r)
  | Rest l_opt -> tl (!l_opt, r)

let append (l1, r1) (l2, r2) =
  r1 := l2;
  (l1, r2)

let rec fold_left f e (l, r) =
  match l with
  | Nil -> e
  | Cons (x, l1) -> fold_left f (f e x) (l1, r)
  | Rest l1_opt -> fold_left f e (!l1_opt, r) end

let rec fold_right f (l, r) e =
  match l with
  | Nil -> e
  | Cons (x, l1) -> f x (fold_right f (l1, r) e)
  | Rest l1_opt -> fold_right f (!l1_opt, r) e end