[Haskell-cafe] Re: Red-Blue Stack

[apfelmus]

Jamie Brandon wrote:
> Try writing
> 
> data RBStack = RBS [RBSItem] [RBSItem]
> 
> where the first list are all the same colour and the start of the second list
> is a different colour. The rest should follow naturally and you will get
> amortised O(1) push and pop (you occasionally have to juggle the lists).

I am afraid, but this does not give constant amortized time. Let me reformulate
the data type you have in mind as follows:

    data Stack2 r b = Empty | S [r] (Stack2 b r) deriving (Eq, Show)

We're using the type system to distinguish between red (r) and blue (b)
elements. The list [r] corresponds to your first list and means that the stack
has red elements on top. The rest is a stack with blue elements on top.

Using different types for red and blue is extremely cool :) because the compiler
will complain about buggy code that deletes red elements instead of blue ones
and the like. It already helped me to find a bug in my implementation below.


All stack operations like  push  and  pop  will be performed on the red
elements. We can switch between red and blue by making the list empty

    recolor :: Stack2 r b -> Stack2 b r
    recolor (S [] t) = t
    recolor t        = S [] t

In other words, a stack with blue elements on top is a red stack with an empty
list of red elements on top :). We impose the /invariant/ that only the topmost
list may be empty.

Pushing a red element onto the stack is straightforward.

    push :: r -> Stack2 r b -> Stack2 r b
    push r Empty    = S [r] Empty
    push r (S rs t) = S (r:rs) t

and so is pushing blue elements thanks to recoloring

    pushB :: b -> Stack2 r b -> Stack2 r b
    pushB b = recolor . push b . recolor

The topmost element may be either blue or red

    top :: Stack2 r b -> Maybe (Either r b)
    top Empty       = Nothing
    top (S []    t) = fmap (\(Left b) -> Right b) (top t)
    top (S (r:_) t) = Just (Left r)

Most importantly, we want to remove elements. Removing a red element is easy if
there are red elements on the top

    pop :: Stack2 r b -> Stack2 r b
    pop (S (_:rs) t       ) = S rs t

otherwise we will have to remove them from behind the blue elements while taking
care that our /invariant/ still holds.

    pop (S []     (S bs t)) = S [] . s bs . pop $ t
        where
        -- s is like S but takes care of the invariant
        s bs (S [] Empty     ) = S bs Empty
        s bs (S [] (S bs' t')) = S (bs ++ bs') t'
        s bs t                 = t
    pop _                   = Empty

Exercise: Find and correct the bug in this implementation of  pop ! Hint: let
the type checker tell you where it is.
Quiz question: How to remove blue elements?


Unfortunately, this whole implementation is not O(1) time. The problem is our
use of ++. Consider the stack

  S [R] $ S [B] $ S [R] $ S [B] $ S [R] $ S [B] $ S [R] $ S [B] $ Empty

Removing all the blue elements from this stack will give

  S ((([R] ++ [R]) ++ [R]) ++ [R]) Empty

and we see the feared left-parenthesized application of list concatenation.
Removing all red elements but one and asking for top will take quadratic time
which doesn't amortize to O(1).


In other words, while cool, the above implementation is not really what you
want, Matthew. Quite a disappointing result for such a long e-mail ;). But don't
worry, in a subsequent post, I'll turn the above ideas into a better solution
and I'll also explain why implementing this data structure seems more difficult
in Haskell than in Java.


Regards,
apfelmus