Source code in the ocaml programming language

module FIFO : sig
  type 'a fifo
  val empty: 'a fifo
  val push: fifo:'a fifo -> item:'a -> 'a fifo
  val pop: fifo:'a fifo -> 'a * 'a fifo
  val is_empty: fifo:'a fifo -> bool
end = struct
  type 'a fifo = 'a list * 'a list
  let empty = [], []
  let push ~fifo:(input,output) ~item = (item::input,output)
  let is_empty ~fifo =
    match fifo with
    | [], [] -> true
    | _ -> false
  let rec pop ~fifo =
    match fifo with
    | input, item :: output -> item, (input,output)
    | [], [] -> failwith "empty fifo"
    | input, [] -> pop ([], List.rev input)
end


# open FIFO;;
# let q = empty ;;
val q : '_a FIFO.fifo = <abstr>
# is_empty q ;;
- : bool = true
# let q = push q 1 ;;
val q : int FIFO.fifo = <abstr>
# is_empty q ;;
- : bool = false

# let q =
    List.fold_left push q [2;3;4] ;;
val q : int FIFO.fifo = <abstr>

# let v, q = pop q ;;
val v : int = 1
val q : int FIFO.fifo = <abstr>
# let v, q = pop q ;;
val v : int = 2
val q : int FIFO.fifo = <abstr>
# let v, q = pop q ;;
val v : int = 3
val q : int FIFO.fifo = <abstr>
# let v, q = pop q ;;
val v : int = 4
val q : int FIFO.fifo = <abstr>
# let v, q = pop q ;;
Exception: Failure "empty fifo".