[Haskell-cafe] Re: Red-Blue Stack

[apfelmus]

Thomas Davie wrote:
>
> Matthew Eastman wrote:
>>
>> 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]
> 
> I wanted to add my own 2p to this discussion.  I'm not dead certain I
> understand what is meant by the statement above, so I'm going to make a
> guess that when we pop an item, the top item on the stack should end up
> being the next item of the same colour as we popped.
> 
> In this interpretation, here's what I think is an O(1) implementation:
> 
> data RBStack a = Empty
>                | More RBColour a (RBStack a) (RBStack a)
> 
> data RBColour = Red | Blue
> 
> rbPush :: Colour -> a -> RBStack a -> RBStack a
> rbPush c x Empty = More c x Empty Empty
> rbPush c x e@(More c' v asCs nextNonC)
>   | c == c'   = More c x e nextNonC
>   | otherwise = More c x nextNonC e
> 
> rbPop :: Colour -> RBStack a -> RBStack a
> rbPop c Empty = error "Empty Stack, can't pop"
> rbPop c (More c' v asCs nextNonC)
>   | c == c'   = asCs
>   | otherwise = rbPop c nextNonC
> 
> The idea is that an RBStack contains its colour, an element, and two
> other stacks -- the first one is the substack we should get by popping
> an element of the same colour.  The second substack is the substack we
> get by looking for the next item of the other colour.
> 
> When we push, we compare colours with the top element of the stack, and
> we swap around the same coloured/differently coloured stacks appropriately.
> 
> When we pop, we jump to the first element of the right colour, and then
> we jump to the next element of the same colour.
> 
> I hope I haven't missed something.

This looks O(1) but I don't understand your proposal enough to say that
it matches what Matthew had in mind.

Fortunately, understanding can be replaced with equational laws :) So, I
think Matthew wants the following specification: A red-blue stack is a
data structure

  data RBStack a

with three operations

  data Color = Red | Blue

  empty :: RBStack a
  push  :: Color -> a -> RBStack a -> RBStack a
  pop   :: Color -> RBStack a -> RBStack a
  top   :: RBStack a -> Maybe (Color, a)

subject to the following laws

     -- pop removes elements of the same color
  pop Red  . push Red  x = id
  pop Blue . push Blue x = id

     -- pop doesn't interfere with elements of the other color
  pop Blue . push Blue x = push Blue x . pop Red
  pop Red  . push Red  x = push Red  x . pop Blue

     -- top returns the last color pushed or nothing otherwise
  (top . push c x) stack = Just (c,x)
               top empty = Nothing

     -- pop on the empty stack does nothing
             pop c empty = empty

These laws uniquely determine the behavior of a red-blue stack.

Unfortunately, your proposal does not seem to match the second group of
laws:

   (pop Blue . push Red r . push Blue b) Empty
  = pop Blue (push Red r (More Blue b Empty Empty))
  = pop Blue (More Red r Empty (More Blue b Empty Empty))
  = pop Blue (More Blue b Empty Empty)
  = Empty

but

  = (push Red r . pop Blue . push Blue b) Empty
  = push Red r (pop Blue (More Blue b Empty Empty))
  = push Red r Empty
  = More Red r Empty Empty

The red element got lost in the first case.


Regards,
apfelmus