1.15.14.4 Persistent data

Queues are one of the fundamental data structures of computer science. In functional languages, queues are commonly implemented using two lists, with the front half of the queue in one list, where the head of the queue can be accessed easily, and the rear half of the queue in reverse order in another list, where new items can easily be added to the end of a queue. The standard form of such a queue holds that the front list can only be null if the rear list is also null:

(define queue-null (cons '() '())

(define (queue-null? obj)
  (and (pair? obj) (null? (car obj))))

(define (queue-check f r)
  (if (null? f)
      (cons (reverse r) '())
    (cons f r)))

(define (queue-snoc q x)
  (queue-check (car q) (cons x (cdr q))))

(define (queue-head q)
  (if (null? (car q))
      (error "empty queue: head")
    (car (car q))))

(define (queue-tail q)
  (if (null? (car q))
      (error "empty-head: tail")
    (queue-check (cdr (car q)) (cdr q))))

This queue operates in amortized constant time per operation, with two conses per element, one when it is added to the rear list, and another when the rear list is reversed to become the front list. queue-snoc and queue-head operate in constant time; queue-tail operates in worst–case linear time when the front list is empty.

Chris Okasaki points out that, if the queue is used persistently, its time–complexity rises from linear to quadratic since each persistent copy of the queue requires its own linear–time access. The problem can be fixed by implementing the front and rear parts of the queue as streams, rather than lists, and rotating one element from rear to front whenever the rear list is larger than the front list:

(define queue-null
  (cons stream-null stream-null))

(define (queue-null? x)
  (and (pair? x) (stream-null (car x))))

(define (queue-check f r)
  (if (< (stream-length r) (stream-length f))
      (cons f r)
    (cons (stream-append f (stream-reverse r))
          stream-null)))

(define (queue-snoc q x)
  (queue-check (car q) (stream-cons x (cdr q))))

(define (queue-head q)
  (if (stream-null? (car q))
      (error "empty queue: head")
    (stream-car (car q))))

(define (queue-tail q)
  (if (stream-null? (car q))
      (error "empty queue: tail")
    (queue-check (stream-cdr (car q)) (cdr q))))

Memoization solves the persistence problem; once a queue element has moved from rear to front, it needs never be moved again in subsequent traversals of the queue. Thus, the linear time–complexity to access all elements in the queue, persistently, is restored.