[Haskell-cafe] Red-Blue Stack

Jamie Brandon jamiiecb at googlemail.com
Thu Sep 25 00:53:48 EDT 2008


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 <mg.eastman at gmail.com> 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]
>
> 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 at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>


More information about the Haskell-Cafe mailing list