module type QUEUE = sig
  type +`a queue : `a
  exception Empty

  val emptyA   : unit → `a queue
  val isEmptyA : `a queue → bool * `a queue
  val sizeA    : `a queue → int * `a queue
  val dequeueA : `a queue → (`a * `a queue) option

  val enqueue  : `a → `a queue → `a queue

  val empty    : 'a queue
  val isEmpty  : 'a queue → bool
  val size     : 'a queue → int
  val first    : 'a queue → 'a
  val dequeue  : 'a queue → 'a queue
end

module Queue : QUEUE = struct
  type `a queue = `a list * `a list

  exception Empty

  let emptyA () = ([], [])

  let isEmptyA q =
    match q with
    | ([], []) → (true, ([], []))
    | q        → (false, q)

  let sizeA (front, back) =
    let (lenf, front) = lengthA front in
    let (lenb, back)  = lengthA back in
    (lenf + lenb, (front, back))

  let dequeueA (front, back) =
    match front with
    | x ∷ xs → Some (x, (xs, back))
    | []     →
      match rev back with
      | x ∷ xs → Some (x, (xs, []))
      | []     → None

  let empty = ([], [])

  let isEmpty q =
    match q with
    | ([], []) → true
    | _        → false

  let enqueue x (front, back) =
    (front, x ∷ back)

  let first q =
    match dequeueA q with
    | Some (x, _) → x
    | None        → raise Empty

  let dequeue q =
    match dequeueA q with
    | Some (_, q') → q'
    | None         → raise Empty

  let size (front, back) =
    length front + length back
end