[Haskell-cafe] Re: Red-Blue Stack

[Thomas Davie]

On 27 Sep 2008, at 20:16, apfelmus wrote:

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

I don't think my proposal even meets the first set of laws -- I  
interpretted the question differently.

pop Red . push Red 1 (More Blue 2 Empty (More Red 3 Empty Empty)) ==  
More Red 3 Empty Empty

Bob