Queues, revisited

Let us implement the abstract data type of queues using modules and signatures. We first specify the type of queues together with its operators in a signature:

module type QUEUE =
  sig
    type 'a queue
    val empty : 'a queue
    val is_empty : 'a queue -> bool
    val enqueue : 'a -> 'a queue -> 'a queue
    val dequeue : 'a queue -> ('a * 'a queue) option
    val show : ('a -> string) -> 'a queue -> string
  end;;

All we need to do now is to implement modules that satisfy this signature and the same unit tests as before (see the lecture note on Queues):

let test_lifo_queue_int empty is_empty enqueue dequeue =
  ...

let test_fifo_queue_int empty is_empty enqueue dequeue =
  ...

Remark:

• The signature of queues is extended with a new operator, show, to unparse the representation of a queue into a string. As usual, this unparsing capability is useful to trace functions that use queues.

Representing a LIFO queue with a list, revisited

In this representation, a queue is a list of elements where the first element in this list shall be the first to be dequeued.

Let us relocate the implementation of LIFO queues as lists in a module:

module Lifo : QUEUE =
  struct
    type 'a queue = 'a list

    let empty = []

    let is_empty q =
      match q with
      | [] ->
         true
      | _ :: _ ->
         false

    let is_empty' q =
      q = []

    let enqueue v q =
      v :: q

    let dequeue q =
      match q with
      | [] ->
         None
      | v :: q' ->
         Some (v, q')

    let show show_yourself q =
      show_list show_yourself q
  end;;

This implementation passes the unit test:

# test_lifo_queue_int Lifo.empty Lifo.is_empty Lifo.enqueue Lifo.dequeue;;
- : bool = true
#

Analysis:

• Lifo.empty is equivalent to lifo_empty_v1 the lecture note on Queues;
• Lifo.is_empty is equivalent to lifo_is_empty_v1 the lecture note on Queues;
• Lifo.enqueue is equivalent to lifo_enqueue_v1 the lecture note on Queues; and
• Lifo.dequeue is equivalent to lifo_dequeue_v1 the lecture note on Queues.

Representing a FIFO queue with a list, Version 1, revisited

In this representation, a queue is a list of elements where the last element in this list shall be the last to be dequeued. In other words, the first (to be dequeued) shall be the first (in the list).

Let us relocate Version 1 of the implementation of queues (in the lecture note on Queues) in a module:

module Fifo_v1 : QUEUE =
  struct
    type 'a queue = 'a list

    let empty = []

    let is_empty q =
      match q with
      | [] ->
         true
      | _ :: _ ->
         false

    let is_empty' q =
      q = []

    let enqueue v q_init =
      let rec prepend q =
        match q with
        | [] ->
           v :: []
        | v' :: q' ->
           v' :: prepend q'
      in prepend q_init

    let dequeue q =
      match q with
      | [] ->
         None
      | v :: q' ->
         Some (v, q')

    let show show_yourself q =
      show_list show_yourself q
  end;;

This implementation passes the unit test:

# test_fifo_queue_int Fifo_v1.empty Fifo_v1.is_empty Fifo_v1.enqueue Fifo_v1.dequeue;;
- : bool = true
#

Analysis:

• Fifo_v1.empty is equivalent to fifo_empty_v1 the lecture note on Queues;
• Fifo_v1.is_empty is equivalent to fifo_is_empty_v1 the lecture note on Queues;
• Fifo_v1.enqueue is equivalent to fifo_enqueue_v1 the lecture note on Queues; and
• Fifo_v1.dequeue is equivalent to fifo_dequeue_v1 the lecture note on Queues.

Representing a FIFO queue with a list, Version 2, revisited

In this representation, a queue is a list of elements where the first element in this list shall be the last to be dequeued. In other words, the first (to be dequeued) shall be the last (in the list).

Let us relocate Version 2 of the implementation of queues (in the lecture note on Queues) in a module:

module Fifo_v2 : QUEUE =
  struct
    type 'a queue = 'a list

    let empty = []

    let is_empty q =
      match q with
      | [] -> true
      | _ :: _ -> false

    let is_empty' q =
      q = []

    let enqueue v q =
      v :: q

    let dequeue q =
      match q with
      | [] ->
         None
      | x :: q' ->
         let rec traverse x q =
           match q with
           | [] ->
              (x, [])
           | x' :: q' ->
              let (last_element, prefix) = traverse x' q'
              in (last_element, x :: prefix)
         in Some (traverse x q')

    let show show_yourself q =
      show_list show_yourself q
  end;;

This implementation passes the unit test:

# test_fifo_queue_int Fifo_v2.empty Fifo_v2.is_empty Fifo_v2.enqueue Fifo_v2.dequeue;;
- : bool = true
#

Analysis:

• Fifo_v2.empty is equivalent to fifo_empty_v2 the lecture note on Queues;
• Fifo_v2.is_empty is equivalent to fifo_is_empty_v2 the lecture note on Queues;
• Fifo_v2.enqueue is equivalent to fifo_enqueue_v2 the lecture note on Queues; and
• Fifo_v2.dequeue is equivalent to fifo_dequeue_v2 the lecture note on Queues.

Representing a FIFO queue with a list, Version 3, revisited

In this representation, a queue is a list of elements together with a Boolean that specifies whether the last operation on this queue was enqueue or dequeue.

Let us relocate Version 3 of the implementation of queues (in the lecture note on Queues) in a module:

module Fifo_v3 : QUEUE =
  struct
    type 'a queue = bool * 'a list

    let empty =
      (true, [])

    let is_empty q =
      match q with
      | (_, []) ->
         true
      | (_, _ :: _) ->
         false

    let enqueue x (flag, xs) =
      let xs = if flag
               then xs
               else List.rev xs
      in (true, x :: xs)

    let dequeue (flag, xs) =
      let xs = if flag
               then List.rev xs
               else xs
      in match xs with
         | [] ->
            None
         | x :: xs' ->
            Some (x, (false, xs'))

    let show show_yourself (flag, xs) =
      "(" ^ show_bool flag ^ ", " ^ show_list show_yourself xs ^ ")"
  end;;

This implementation passes the unit test:

# test_fifo_queue_int Fifo_v3.empty Fifo_v3.is_empty Fifo_v3.enqueue Fifo_v3.dequeue;;
- : bool = true
#

Analysis:

• Fifo_v3.empty is equivalent to fifo_empty_v3 the lecture note on Queues;
• Fifo_v3.is_empty is equivalent to fifo_is_empty_v3 the lecture note on Queues;
• Fifo_v3.enqueue is equivalent to fifo_enqueue_v3 the lecture note on Queues; and
• Fifo_v3.dequeue is equivalent to fifo_dequeue_v3 the lecture note on Queues.

Representing a FIFO queue with a list, Version 4, revisited

In this representation, a queue is pair of lists of elements, one to dequeue in constant time, and one to enqueue in constant time.

Let us relocate Version 4 of the implementation of queues (in the lecture note on Queues) in a module:

module Fifo_v4 : QUEUE =
  struct
    type 'a queue = 'a list * 'a list

    let empty =
      ([], [])

    let is_empty q =
      q = ([], [])

    let enqueue x (pool, reversed_prefix) =
      (pool, x :: reversed_prefix)

    let dequeue (pool, reversed_prefix) =
      match pool with
      | [] ->
         (match List.rev reversed_prefix with
          | [] ->
             None
          | x :: new_pool ->
             Some (x, (new_pool, [])))
      | x :: pool' ->
         Some (x, (pool', reversed_prefix))

    let show show_yourself (pool, reversed_prefix) =
      "(" ^ show_list show_yourself pool ^ ", " ^ show_list show_yourself reversed_prefix ^ ")"
  end;;

This implementation passes the unit test:

# test_fifo_queue_int Fifo_v4.empty Fifo_v4.is_empty Fifo_v4.enqueue Fifo_v4.dequeue;;
- : bool = true
#

Analysis:

• Fifo_v4.empty is equivalent to fifo_empty_v4 the lecture note on Queues;
• Fifo_v4.is_empty is equivalent to fifo_is_empty_v4 the lecture note on Queues;
• Fifo_v4.enqueue is equivalent to fifo_enqueue_v4 the lecture note on Queues; and
• Fifo_v4.dequeue is equivalent to fifo_dequeue_v4 the lecture note on Queues.

Representing a FIFO queue with a list, Version 5, revisited

In this representation, a queue pairs a lists of elements to dequeue in constant time and a function to construct the next list of elements to dequeue in constant time.

Let us relocate Version 5 of the implementation of queues (in the lecture note on Queues) in a module:

module Fifo_v5 : QUEUE =
  struct
    type 'a queue = 'a list * ('a list -> 'a list)

    let cons x xs =
      x :: xs

    let compose f g x =
      f (g x)

    let empty =
      ([], fun es -> es)

    let is_empty (es, h) =
      es = [] && h [] = []

    let enqueue x (pool, h) =
      (pool, compose h (cons x))

    let dequeue (pool, h) =
      match pool with
      | [] ->
         (match h [] with
          | [] ->
             None
          | x :: new_pool ->
             Some (x, (new_pool, fun es -> es)))
      | x :: pool' ->
         Some (x, (pool', h))

    let show show_yourself (pool, h) =
      "(" ^ show_list show_yourself pool ^ ", <function>)"
  end;;

This implementation passes the unit test:

# test_fifo_queue_int Fifo_v5.empty Fifo_v5.is_empty Fifo_v5.enqueue Fifo_v5.dequeue;;
- : bool = true
#

Analysis:

• Fifo_v4.empty is equivalent to fifo_empty_v5 the lecture note on Queues;
• Fifo_v5.is_empty is equivalent to fifo_is_empty_v5 the lecture note on Queues;
• Fifo_v5.enqueue is equivalent to fifo_enqueue_v5 the lecture note on Queues; and
• Fifo_v5.dequeue is equivalent to fifo_dequeue_v5 the lecture note on Queues.

Exercise 7, revisited

The goal of this exercise is to revisit Exercise 7 in the lecture note about Queues.

In the resource file for the present lecture note, you are welcome to see the various FIFO queues in action by applying either of

• traced_traverse_foo_fifo_v1
• traced_traverse_foo_fifo_v2
• traced_traverse_foo_fifo_v3
• traced_traverse_foo_fifo_v4
• traced_traverse_foo_fifo_v5
• traced_traverse_bar_fifo_v1
• traced_traverse_bar_fifo_v2
• traced_traverse_bar_fifo_v3
• traced_traverse_bar_fifo_v4
• traced_traverse_bar_fifo_v5

to any given binary tree.

Resources

• The OCaml code for the present lecture note (latest version: 08 Apr 2020).

Version

Created [02 Apr 2019]