[Haskell-cafe] Queues and Rings (Re: Doubly-linked zipper list w/insert implementation)

[apfelmus]

(Btw, this ring stuff could be relevant for Xmonad, I don't know whether 
the workspace/window-ring implementation there is O(1). Not that it 
matters for <1000 windows, of course :)

Justin Bailey wrote:
> apfelmus wrote:
> 
>> Do you really need to realize the cycle by sharing? I mean, sharing
>> doesn't go well with insertion / updates / deletion since each of these
>> operations breaks it and needs to restore it everywhere. In other words,
>> your  insert  takes O(n) time. I'd simply drop the sharing and use two
>> double ended queues (or something like that) instead
> 
> Very good point, and much easier to implement with Data.Sequence to
> boot. All that circular programming made my brain hurt.

There's also a direct and rather lightweight possibility to implement 
rings in the spirit of the classic O(1) lazy amortized functional queue 
implementation. This post will try to explain it.

Here's the basic idea for implementing queues in Haskell: we have a 
front  list to fetch items (head, tail) and a  rear  list to insert 
items (snoc) into the queue.

   data Queue a = Queue [a] [a]

   empty                = Queue [] []
   head (Queue (x:f) r) = x
   tail (Queue (x:f) r) = Queue f r
   snoc (Queue f r) x   = Queue f (x:r)

Of course, this doesn't quite work yet, at some point we have to feed 
the items from the rear list into the front list. For example, the last 
possibility to do so is when the front list becomes empty.

   balance (Queue [] r) = Queue (reverse r) []
   balance q            = q

   tail (Queue (x:f) r) = balance $ Queue f r
   snoc (Queue f r) x   = balance $ Queue f (x:r)

(Calling  balance  maintains the invariant that the front list is never 
empty except when the whole queue is empty, too.) Now, how much time 
will a single  snoc  or  tail  operation take? In the worst case, tail 
triggers a  reverse  and takes O(n) time whereas  snoc  always takes 
constant time. That's a big blow to our goal of O(1) time for both.

But luckily, queues don't come out of "thin air", they all have to be 
constructed from the empty queue by a sequence of applications of snoc 
and  tail . Can the heavy O(n) cost of a worst case  tail  be spread 
over  the many good cases of  tail  and  snoc  in that sequence? Yes, it 
can. To that end, we increase the price of each  snoc  by 1 time "coin". 
So, each item of the rear list gets inserted with one extra coin as 
"credit". With these credits, we can pay the whole  length (rear list) 
cost of a reverse operation when it occurs, making  tail  O(1) again. 
This is also called _amortization_  and O(1) the _amortized_ cost of  tail .

The above works fine if the queue is used in a single-threaded way i.e. 
as _ephemeral_ data structure. But it doesn't work anymore when a queue 
is used multiple times in a _persistent_ setting. Assuming that  tail q 
  triggers a  reverse , the first evaluation of  q1  in

   let
      q1 = tail q
      q2 = tail q
      q3 = tail q
      ...
   in ... q1 .. q2 .. q3

will use up all credits and  q2, q3,...  don't have any to spend and are 
back to worst-case behavior.

In the persistent setting, lazy evaluation comes to the rescue. The idea 
is to create the (yet unevaluated) call to  reverse  earlier, namely 
when the rear list has more elements than the front list.

   balance (Queue f r)
      | length r >= length f = Queue (f ++ reverse r) []
   balance q = q

(We assume that  length  has been made O(1) by storing the lengths 
explicitly.) Now, the O(length r)  reverse  will not be evaluated before 
having "tailed" through the previous front list with  length f == length 
r  items. Thus, we can spread the cost of  reverse  as "debits" over 
these elements. When finally executing  reverse , its debits have 
already been paid off and  tail  is O(1) again. And once executed, lazy 
evaluation memoizes the result, so that sharing doesn't duplicate the work.
(Note that strict languages without side effects are doomed to be slower 
when persistence matters. Ha! ;)

So much for a too short introduction to the classic purely functional 
queue implementation. For a detailed exposition and much more, see also

   Chris Okasaki. Purely Functional Data Structures. (Thesis)
   http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf

or his book with the same title which arose from this thesis.


Now, rings can be implemented in a similar style.

   data Ring a = Ring [a] a [a]

   rotL (Ring ls x (r:rs)) = balance $ Ring (x:ls) r rs
   rotR (Ring (l:ls) x rs) = balance $ Ring ls l (x:rs)

(For simplicity, we only deal with the case where the left and right 
list are non-empty.)
How to balance? In contrast to queues, doing a full  reverse  when one 
list is empty doesn't even work in the ephemeral case since a  rotR 
following a  rotL  will undo the  reverse  with yet another expensive 
reverse . But we can apply the same idea as for persistent queues and 
balance as soon as one list becomes like 2 times (or 3 or whatever) as 
large as the other one

   balance (Ring ls x rs)
     | length ls > 2*length rs = r'
     | length rs > 2*length ls = r'
     where
     n  = length ls + length rs
     k  = n `div` 2
     r' = Ring
            (take k     $ ls ++ reverse (drop (n-k) rs))
            x
            (take (n-k) $ rs ++ reverse (drop k     ls))

   balance r = r

This will make  rotL  and  rotR  run in O(1) amortized time.


Exercises:
1) Complete the implementation of  rotL  and rotR . Besides dealing with 
possibly empty  ls  and  rs , it's also possible to assume them 
non-empty and use special constructors for rings with <= 2 elements.
2) Use the balancing scheme for rings to implement double-ended queues, 
i.e. queues with both  cons  and  snoc .
3) Read Okasaki's book and prove my O(1) claims :)


Regards,
apfelmus