Matthew Eastman mg.eastman at gmail.com
Thu Sep 25 00:11:00 EDT 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

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.

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
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
```