[Haskell-cafe] Red-Blue Stack

25 Sep 2008

      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] Red-Blue Stack

Matthew Eastman