Lazy Functional Queues in Scala

Scala has a nice functional Queue implementation as part of scala.collection.immutable. It implements the standard technique of using a pair of lists [L, R], where L is the first portion of the queue and R is the rear portion in reverse order. As a result, the head of L is the first element of the queue and head of R points to the last element of the queue. Hence both can be fetched in O(1) time. Items are enqueued from the rear end, i.e. a O(1) insert in R, while they are dequeued from the front. Again a (supposedly) O(1) removal from L.

A nice trick indeed .. Here is the snippet from the Scala library ..

class Queue[+A](elem: A*) extends Seq[A] {

  protected val in: List[A] = Nil
  protected val out: List[A] = elem.elements.toList

  //..
  //..

  def enqueue[B >: A](elem: B) = mkQueue(elem :: in, out)

  def dequeue: (A, Queue[A]) = {
    val (newOut, newIn) =
      if (out.isEmpty) (in.reverse, Nil)
      else (out, in)
    if (newOut.isEmpty) throw new NoSuchElementException("queue empty")
    else (newOut.head, mkQueue(newIn, newOut.tail))
  }
  //..
  //..
}


Now have a close look at dequeue. When we try to do a dequeue, with out being empty, in needs to be reversed, a definite O(n) operation. But, for a list of length n, this occurs only when there has been n insertions since last reversal. Hence dequeue still remains an amortized O(1) operation. The point is whether you can afford an occasional O(n) ..

In his paper "Simple and Efficient Purely Functional Queues and Deques", Okasaki discusses a technique that uses lazy lists and incremental computation to improve the above worst case complexity of dequeue to O(log n). In fact, later in the paper, he also implements an improvement of this version using full memoization and lazy languages to implement a worst case O(1) dequeue. Okasaki has written a beautiful thesis on functional data structures and their analyses techniques, which later has been published as a book. A highly recommended piece for the interested ones ..

Being Lazy

The main trick of Okasaki's O(log n) dequeue algorithm is to make L a lazy list. Instead of doing the above reverse in a single step as a strict operation, we can have [L, R] incrementally changed to [L ++ reverse(R), []], so that when the actual need for the reverse comes, we already have R reversed and appended to L. The meat lies in the reverse operation being done incrementally and the ++ operation being done lazily. Okasaki's paper describes the algorithm and it's analysis in great detail.

Using Scala Streams

Scala offers lazy lists in the form of Stream[A], where Stream.cons is defined as ..

object Stream {
  object cons {
    def apply[A](hd: A, tl: => Stream[A]) = new Stream[A] {
      //..
    }
    //..
  }
  //..
}


and offers a lazy concatenation ..

How about using Stream[A] for the list L and try out Okasaki's algorithm to get a faster functional persistent Queue in Scala ? Name it OQueue[+A] ..

class OQueue[+A] {
  protected val front: Stream[A] = Stream.empty
  protected val sizef: Int = 0
  protected val sizer: Int = 0
  protected val rear: List[A] = Nil
  //..
  //..
}


Okasaki calls the incremental adjustment of [L, R] operation as a rotate. Here is the implementation of rotate in OQueue, which gets called during construction of the OQueue. Note that OQueue (and Scala's Queue), being functional, is also persistent - hence every mutating operation returns a new version of the data structure. This is unlike imperative data structures that implement destructive updates and maintain only the latest version. Hence rotate gets called as part of OQueue construction. However, rotate is not called for every call of the constructor - it is called only when |R| = |L| + 1 and we need to start the process of incremental reversal. And the trick is to start the process of reversing R just at the moment R gets longer than L and interleave the append to L with reverse of R. The details are too gory for a blog post and can be found with all it's complexities in the original paper.

class OQueue[+A] {
  //..
  //..
  protected def rotate[A](xs: Stream[A], ys: List[A], rys: Stream[A]): Stream[A] = ys match {
    case y :: ys1 =>
      if (xs isEmpty) Stream.cons(y, rys)
      else
        Stream.cons(xs.head, rotate(xs.tail, ys.tail, Stream.cons(y, rys)))
    case Nil =>
      //..
  }
  //..
}


and now the constructor / factory method for constructing an OQueue[A] ..

class OQueue[+A] {
  //..
  //..
  protected def makeQ[A](f: Stream[A], sf: Int, r: List[A], sr: Int): OQueue[A] = {
    if (sr <= sf) {
      new OQueue[A]() {
        override protected val front = f
        override protected val sizef = sf
        override protected val rear = r
        override protected val sizer = sr
      }
    } else {
      new OQueue[A]() {
        override protected val front = rotate(f, r, Stream.empty)
        override protected val sizef = sf + sr
        override protected val rear = Nil
        override protected val sizer = 0
      }
    }
  }
  //..
}


The other methods are fairly trivial and nicely fall in place ..

class OQueue[+A] {
  //..
  //..
  def isEmpty: Boolean = sizef == 0

  def enqueue[B >: A](elem: B) = {
    makeQ(front, sizef, elem :: rear, sizer + 1)
  }

  def dequeue: (A, OQueue[A]) = {
    (front.head, makeQ(front.tail, sizef - 1, rear, sizer))
  }

  def elements: Iterator[A] = (front.force ::: rear.reverse).elements

  def length = (sizef + sizer)
  //..
  //..
}


Fast ?

Analyzing lazy, persistent functional data structures is hard and so is benchmarking them. I did not do an elaborate benchmarking of OQueue with scala.collection.immutable.Queue. But from whatever I did, I could not get any speedup over the Scala library implementation. Scala, unlike Haskell, is not a lazy language. And lazy languages offer memoization of function arguments i.e. arguments are evaluated only when they are needed and once evaluated, they are cached for future reuse. In the above implementation of OQueue, we need to evaluate front.tail a number of times - an effectively lazy language can make this operation O(1) through memoization. Also, Scala, being implemented on top of the JVM, is not the best platform for heavy recursion and the above implementation of rotate is also not tail recursive, that Scala could optimize. Okasaki implemented the algorithm in SML, a lazy functional language and possibly got effective speedups over the traditional paired list implementation of queues.

I am not a Scala expert, any suggestions or critiques regarding the above implementation will be most welcome. Of course, I plan to do some more micro-benchmarking. But I think there may be dominant constants that offset the asymptotic complexity figures of the above analysis. Besides, the above implementation does not take any advantage of memoization, which is yet another secret sauce behind speedups of functional implementations. Anyway, it was, I feel, a worthwhile exercise trying my hands on implementing a functional data structure.

Postscript

I just discovered that Rich Hickey addresses this problem in a different way in Clojure. He has used the traditional paired list implementation, but without R storing the rear end in a reversed manner. Instead he uses a PersistentVector as the rear - and his PersistentVector is based upon a trie based implementation that gives near constant time access to elements.