Purely functional queue in Ocaml

Queue.ml

(* Nick Heiner <[email protected]> *)
(* Adapted from https://gist.github.com/1347308 *)
(* The func_ prefix is to avoid confusion with OCaml's standard Queue. *)

(* from F# *)
let (|>) g f = f g

type 'a func_queue = Func_Queue of 'a list * 'a list

let empty = Func_Queue ([], [])

let add q elt = match q with
  | Func_Queue (front, back) -> Func_Queue (elt::front, back)

(* convenience overload for add *)
let push elt q = add q elt

let peek_tail = function
  | Func_Queue ([], []) ->
      raise (Invalid_argument "FuncQueue.peek_tail: Empty Queue")
  | Func_Queue (hd::tl, _) -> hd
  | Func_Queue ([], back) -> List.rev back |> List.hd  

(* bit of duplication between this and take *)
let peek = function
  | Func_Queue ([], []) -> raise (Invalid_argument "Empty queue!")
  | Func_Queue (front, b::bs) -> b
  | Func_Queue (front, []) -> let back = List.rev front
                              in List.hd back
let take = function
  | Func_Queue ([], []) -> raise (Invalid_argument "Empty queue!")
  | Func_Queue (front, b::bs) -> b, (Func_Queue (front, bs))
  | Func_Queue (front, []) -> let back = List.rev front
                         in (List.hd back, Func_Queue ([], List.tl back))
                        
(* Drops the elements from the head of the list while pred holds *)                        
let rec drop_if (pred : 'a -> bool) (q : 'a func_queue) : 'a func_queue =
  if q = empty then q else
  if pred (peek q) then drop_if pred (snd (take q)) else q

let rec fold f init q = 
  if q = empty then init else
  let head, rest = take q in
  fold f (f init head) rest                 

let size q = fold (fun acc _ -> acc + 1) 0 q