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).
By the way, for this kind of question you'll get help much faster if
you ask on #haskell.
Jamie
On Thu, Sep 25, 2008 at 5:11 AM, Matthew Eastman
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]
All push and pop operations on the stack have to be done in O(1) time.
It was easy to do in Java since you can just keep track of everything with a few pointers, but it took a while to get the Haskell version working. Maybe I'm just not used to the functional way of doing things.
I originally had this:
data RBSItem a = Red a | Blue a
data RedBlueStack a = RBS { red :: [RBSItem a], blue :: [RBSItem a], overall :: [RBSItem a] }
But there was no way to keep popping in O(1) time because I would have to walk through the overall list when removing items.
I eventually came up with:
data ShowColour = PlusRed | MinusRed | PlusBlue | MinusBlue
data RedBlueStack a = RBS { red :: [a], blue :: [a], order :: [ShowColour] }
popRed :: RedBlueStack a -> RedBlueStack a popRed (RBS (r:rs) b o) = RBS rs b (MinusRed : o) popRed rbs@(RBS [] _ _) = rbs
-- As an aside here, would it be better to put "popRed = id" for the catch-all in popRed instead of what I have? -- I don't know proper Haskell coding style yet.
remUseless :: [ShowColour] -> [ShowColour] remUseless order@(x:xs) | x == MinusRed = remShowColour PlusRed xs | x == MinusBlue = remShowColour PlusBlue xs | otherwise = order where remShowColour r (c:cs) | c == r = cs | otherwise = c : remShowColour r cs remShowColour _ [] = error "Incorrect Stack Order"
So instead of walking through the overall list, I just have to add a MinusRed or MinusBlue to the order list. This makes the pop and push functions operate in O(1) time, but it seems a bit excessive, because whenever the overall order of the stack is needed (e.g. printing the stack) I need to clean up the order list.
I was just wondering whether this is the best way to implement something like this, keeping track of changes made instead of making the changes. If anyone has any ideas for other ways of implementing this I'd love to see them.
I didn't take into account that Haskell is lazy. Will that have any effect on the running time? Probably not for a simple program like this, but for larger ones and more complex data structures and algorithms, I'm guessing it would?
Thanks, Matt _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe