[Haskell-cafe] Red-Blue Stack

[Thomas Davie]

On 25 Sep 2008, at 06:11, Matthew Eastman wrote:

> Hey guys,
>
> This is probably more of a question about functional programming  
> than it is about Haskell, but hopefully you can help me out. I'm new  
> to thinking about things in a functional way so I'm not sure what  
> the best way to do some things are.
>
> I'm in a data structures course right now, and the assignments for  
> the course are done in Java. I figured it'd be fun to try and  
> implement them in Haskell as well.
>
> The part of the assignment I'm working on is to implement a  
> RedBlueStack, a stack where you can push items in as either Red or  
> Blue. You can pop Red and Blue items individually, but the stack has  
> to keep track of the overall order of items.
>
> i.e. popping Blue in [Red, Red, Blue, Red, Blue] would give [Red,  
> Red, Blue]

I wanted to add my own 2p to this discussion.  I'm not dead certain I  
understand what is meant by the statement above, so I'm going to make  
a guess that when we pop an item, the top item on the stack should end  
up being the next item of the same colour as we popped.

In this interprettation, here's what I think is an O(1) implementation:

data RBStack a = Empty
                | More RBColour a (RBStack a) (RBStack a)

data RBColour = Red | Blue

rbPush :: Colour -> a -> RBStack a -> RBStack a
rbPush c x Empty = Elem c x Empty Empty
rbPush c x e@(More c' v asCs nextNonC)
   | c == c'   = More c x e nextNonC
   | otherwise = More c x nextNonC e

rbPop :: Colour -> RBStack a -> RBStack a
rbPop c Empty = error "Empty Stack, can't pop"
rbPop c (More c' v asCs nextNonC)
   | c == c'   = asCs
   | otherwise = rbPop c nextNonC

The idea is that an RBStack contains its colour, an element, and two  
other stacks -- the first one is the substack we should get by popping  
an element of the same colour.  The second substack is the substack we  
get by looking for the next item of the other colour.

When we push, we compare colours with the top element of the stack,  
and we swap around the same coloured/differently coloured stacks  
appropriately.

When we pop, we jump to the first element of the right colour, and  
then we jump to the next element of the same colour.

I hope I haven't missed something.

Bob