08 Functional Queues

Let's implement functional queues as lists!

module ListQueue = struct
	type 'a queue = 'a list
	
	let empty = []
	
	(* use the append operator to put it at the end of the list *)
	(* linear time :'( *)
	let enqueue x q = q @ [x]
	
	let dequeue = function
		| [] -> None
		| _ :: t -> Some t
	
	let peek = function
		| [] -> None
		| h :: _ -> Some h
end

module ListQueue :
  sig
    type 'a queue = 'a list
    val empty : 'a list
    val enqueue : 'a -> 'a list -> 'a list
    val dequeue : 'a list -> 'a list option
    val peek : 'a list -> 'a option
  end

Let's fix this! We can use a "Two List Queue," invented by Prof. Gries's Ph.D. student in 1981 (Robert Melville)

module TwoListQueue = struct
	
	(*
		[{front = [a; b;]; back = [e; d; c;]}] represents the queue [a; b; c; d; e]
		If [front] is empty, then back is empty too.
	*)
	type 'a queue = {
		front : 'a list;
		back : 'a list;
	}
	
	let empty = {front = []; back = [];}
	
	(* Precondition: If the front is empty, the back is also empty *)
	let peek = function
		| {front = []} -> None
		| {front = x :: _} -> Some x
	
	let enqueue x = function
		| {front = []} -> {front = [x]; back = []}
		| q -> {q with back = x :: q.back}
	
	
	(* This dequeue operation is constant time, unless the front becomes empty. *)
	let dequeue = function
		| {front = []} -> None
		| {front = h :: []; back} -> Some {front = (List.rev back); back = []}
		| {front = _ :: t; back} -> Some {front = t ; back}
end

module TwoListQueue :
  sig
    type 'a queue = { front : 'a list; back : 'a list; }
    val empty : 'a queue
    val peek : 'a queue -> 'a option
    val enqueue : 'a -> 'a queue -> 'a queue
    val dequeue : 'a queue -> 'a queue option
  end