Queues

The Queue abstraction employs a First-In-First-Out (FIFO) policy for removing ("dequeing") elements.

empty   : Queue a
isEmpty : Queue a -> Bool
enqueue : a -> Queue a -> Queue a
dequeue : Queue a -> Maybe (Queue a)
peek    : Queue a -> Maybe a

NOTE: Another reasonable alternative for dequeue would be to also return the dequeued element.

Without having O(1) time access to the last element in a List, special care must be taken to provide efficient Queue operations in a purely functional language.

First Attempt — SlowQueue.elm

type Queue a =
  Q (List a)

empty : Queue a
empty =
  Q []

isEmpty : Queue a -> Bool
isEmpty q =
  q == empty

enqueue : a -> Queue a -> Queue a
enqueue x (Q xs) =
  Q (xs ++ [x])

dequeue : Queue a -> Maybe (Queue a)
dequeue (Q xs) =
  case xs of
    _::xs_ -> Just (Q xs_)
    []     -> Nothing

peek : Queue a -> Maybe a
peek (Q xs) =
  case xs of
    x::_   -> Just x
    []     -> Nothing

Running times:

• enqueue : Θ(n)
• dequeue : O(1)
• peek : O(1)

Second Attempt — AnotherSlowQueue.elm

type Queue a
  = Front (List a)
  | Back (List a)

empty : Queue a
empty =
  Front []

isEmpty : Queue a -> Bool
isEmpty q =
  case q of
    Front [] -> True
    Back []  -> True
    _        -> False

enqueue : a -> Queue a -> Queue a
enqueue x q =
  case q of
    Front xs -> Back (x :: List.reverse xs)
    Back xs  -> Back (x :: xs)

dequeue : Queue a -> Maybe (Queue a)
dequeue q =
  case q of
    Back []      -> Nothing
    Back (x::xs) -> Just (Back xs)
    Front xs     -> dequeue (Back (List.reverse xs))

peek : Queue a -> Maybe a
peek q =
  case q of
    Back []      -> Nothing
    Back (x::_)  -> Just x
    Front xs     -> peek (Back (List.reverse xs))

Running times:

• enqueue : O(n)
• dequeue : O(n)
• peek : O(n)

Third Attempt — MediumQueue.elm

type Queue a =
  Q { front: List a, back: List a }

empty : Queue a
empty =
  Q {front = [], back = []}

isEmpty : Queue a -> Bool
isEmpty q =
  q == empty

enqueue : a -> Queue a -> Queue a
enqueue x (Q {front, back}) =
  Q {front = front, back = x::back }

dequeue : Queue a -> Maybe (Queue a)
dequeue (Q {front, back}) =
  case (front, back) of
    (_::f, _) -> Just (Q {front = f, back = back})
    ([], [])  -> Nothing
    ([], _)   -> dequeue (Q {front = List.reverse back, back = []})

peek : Queue a -> Maybe a
peek (Q {front, back}) =
  case (front, back) of
    (x::_, _) -> Just x
    ([], [])  -> Nothing
    ([], _)   -> peek (Q {front = List.reverse back, back = []})

Running times:

• enqueue : O(1)
• dequeue : O(n)
• peek : O(n)

Final Version — FastQueue.elm

Same representation Q {front, back} as previous version, but with the invariant front == [] implies back == [].

enqueue : a -> Queue a -> Queue a
enqueue x (Q {front, back}) =
  case front of
    [] -> Q {front = [x], back = []}
    _  -> Q {front = front, back = x::back }

dequeue : Queue a -> Maybe (Queue a)
dequeue (Q {front, back}) =
  case front of
    []    -> Nothing
    _::[] -> Just (Q {front = List.reverse back, back = []})
    _::f_ -> Just (Q {front = f_, back = back})

peek : Queue a -> Maybe a
peek (Q {front, back}) =
  List.head front

We can factor out a common pattern from enqueue and dequeue. Notice that arguments f and b to checkFront do not necessarily satisfy the invariant, but the output Queue does.

checkFront : List a -> List a -> Queue a
checkFront f b =
  case f of
    [] -> Q {front = List.reverse b, back = []}
    _  -> Q {front = f, back = b}

enqueue_ : a -> Queue a -> Queue a
enqueue_ x (Q {front, back}) =
  checkFront front (x::back)

dequeue_ : Queue a -> Maybe (Queue a)
dequeue_ (Q {front, back}) =
  case front of
    []    -> Nothing
    _::f_ -> Just (checkFront f_ back)

Running times:

• enqueue : O(1)
• dequeue : O(n)
• peek : O(1)

The worst-case bound for dequeue does not tell the whole story, however, since it often runs in O(1) time and only occasionally runs in O(n) time. Using amortized asymptotic analysis, we will be able to argue that dequeue runs in O(1) on average.

Reading

Required

• Okasaki, Chapter 5.2