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
