Queue

A queue is data structure that stores a sequence of elements, while supporting two basic operations: enqueue and dequeue

Let's visualize how it works:

 [0; 1; 2]
= { enqueue 42 }
 [0; 1; 2; 42]

 [0; 1; 2]
= { dequeue }
 0, [1; 2]

First restriction: rely on inmutable data structures

• Using a list we can rely on the operator :: for dequeueing, since pattern matching x::xs O(1)
• However this means for enqueuing we need to do xs @ [x] which is O(n), where n = xs.Length

Solution:

• rely on :: for both enqueue and dequeue, since the operation x::xs is O(1)
• We can use two lists one enqueueing and one for dequeueing, front and rear respectively
• For dequeueing elements we do the pattern match x::xs on front getting in x the expected element, while in xs the new value for front.
• For enqueueing we repleace rear by x::rear, however this list ends up reversed according the expected order when dequeueing, since x is its first element and should be the last dequeued.
• At some point the dequeue operation will leave empty the front list. When that happens we can take rear, reverse it and use it as the new front while the new rear is an empty list.

type Queue<'a> = { front: 'a list; rear: 'a list }

let enqueue (q: Queue<'a>) (x: 'a) = { q with rear = x :: q.rear }

let dequeue (q: Queue<'a>) =
  match q.front, List.rev q.rear with
  | [], [] -> None
  | [], x :: xs -> Some(x, { front = xs; rear = [] })
  | x :: xs, _ -> Some(x, { q with front = xs })

let rec queueToSeq (q: Queue<'a>) =
  seq {
    match dequeue q with
    | None -> ()
    | Some(x, nq) ->
      yield x
      yield! queueToSeq nq
  }

Let's make a simple test for our algorithm:

let xs = Seq.init 10 id |> Seq.toList
let q = xs |> Seq.fold (fun q x -> enqueue q x) {front = []; rear = []}
let ys = queueToSeq q |> Seq.toList
List.zip xs ys |> List.forall (fun (x, y) -> x = y)

True

Notice that in the current implementation of Microsoft's F# compiler, the following pattern match

match q.front, List.rev q.rear with
| [], [] -> ...
| [], x :: xs -> ...
| x :: xs, _ -> ...

evaluates List.rev q.rear always before matching any branch. This means that the code could easily be made more efficient. However, I think it makes no sense to evaluate such an expression until after q.front has been matched, since in some situations this would be sufficient to decide which branch to take. For this reason, I prefer to present the algorithm as it is, and leave it to the reader to optimise it if they think it is necessary.