Real-Time Queues

RealTimeQueue.elm

Combine reverse and append into an incremental function that performs one step of each at a time:

rotate : LazyList a -> List a -> LazyList a -> LazyList a
rotate xs ys acc =
  case (force xs, ys) of
    (Nil        , y::[])  -> lazy (\_ -> Cons y acc)
    (Cons x xs' , y::ys') ->
      lazy (\_ -> Cons x (rotate xs' ys' (lazy (\_ -> Cons y acc))))

Starting with the BankersQueue, use an ordinary List to describe the back, and track a "schedule" LazyList a that is a suffix of front that needs to be forced. The implementation enforces the invariant that the size of sched is equal to the size of front minus the size of back. This invariant obviates the need to maintain Int size information explicitly.

type Queue a = Q (LazyList a) (List a) (LazyList a)

The basic operations:

empty : Queue a
empty = Q (lazy (\_ -> Nil)) [] (lazy (\_ -> Nil))

isEmpty : Queue a -> Bool
isEmpty (Q front _ _) =
  case force front of
    Nil -> True
    _   -> False

peek : Queue a -> Maybe a
peek (Q front _ _) = maybeHead front

Because of the invariant, sched is empty when the lengths of front and back are the same. So when enqueueing an element, the rotation from back to front is initiated when sched is empty.

enqueue : a -> Queue a -> Queue a
enqueue x (Q front back sched) =
  case force sched of
    Cons _ sched' -> Q front (x::back) sched'
    Nil ->
      let front' = rotate front back (lazy (\_ -> Nil)) in
      Q front' [] front'

Similarly, dequeue initiates the rotation when the back becomes longer than the front.

dequeue : Queue a -> Maybe (Queue a)
dequeue (Q front back sched) =
  case force front of
    Nil -> Nothing
    Cons _ front' ->
      case force sched of
        Cons _ sched' -> Just (Q (tail front') back sched')
        Nil ->
          let front'' = rotate front' back (lazy (\_ -> Nil)) in
          Just (Q front'' [] front'')

The common parts of these operations can be factored out into an exec function.

enqueue : a -> Queue a -> Queue a
enqueue x (Q front back sched) = exec front (x::back) sched

dequeue : Queue a -> Maybe (Queue a)
dequeue (Q front back sched) =
  case force front of
    Nil       -> Nothing
    Cons _ f' -> Just (exec f' back sched)

exec front back sched =
  case force sched of
    Cons _ sched' -> Q front back sched'
    Nil ->
      let front' = rotate front back (lazy (\_ -> Nil)) in
      Q front' [] front'

Reading

Recommended

• Okasaki, Chapter 7.1—7.2. Although we will not cover this material in class, you are encouraged to read through this material to understand the basic ideas.