(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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
