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