On 27 Sep 2008, at 20:16, apfelmus wrote:
Thomas Davie wrote:
Matthew Eastman wrote:
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 interpretation, 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 = More 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.
This looks O(1) but I don't understand your proposal enough to say that it matches what Matthew had in mind.
Fortunately, understanding can be replaced with equational laws :) So, I think Matthew wants the following specification: A red-blue stack is a data structure
data RBStack a
with three operations
data Color = Red | Blue
empty :: RBStack a push :: Color -> a -> RBStack a -> RBStack a pop :: Color -> RBStack a -> RBStack a top :: RBStack a -> Maybe (Color, a)
subject to the following laws
-- pop removes elements of the same color pop Red . push Red x = id pop Blue . push Blue x = id
-- pop doesn't interfere with elements of the other color pop Blue . push Blue x = push Blue x . pop Red pop Red . push Red x = push Red x . pop Blue
-- top returns the last color pushed or nothing otherwise (top . push c x) stack = Just (c,x) top empty = Nothing
-- pop on the empty stack does nothing pop c empty = empty
These laws uniquely determine the behavior of a red-blue stack.
Unfortunately, your proposal does not seem to match the second group of laws:
(pop Blue . push Red r . push Blue b) Empty = pop Blue (push Red r (More Blue b Empty Empty)) = pop Blue (More Red r Empty (More Blue b Empty Empty)) = pop Blue (More Blue b Empty Empty) = Empty
but
= (push Red r . pop Blue . push Blue b) Empty = push Red r (pop Blue (More Blue b Empty Empty)) = push Red r Empty = More Red r Empty Empty
The red element got lost in the first case.
I don't think my proposal even meets the first set of laws -- I interpretted the question differently. pop Red . push Red 1 (More Blue 2 Empty (More Red 3 Empty Empty)) == More Red 3 Empty Empty Bob