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