[Haskell-cafe] Red-Blue Stack

[Thomas Davie]

>
> Thomas Davie wrote:
>
>> In this interprettation, here's what I think is an O(1)  
>> implementation:
>>
>> ...
>>
>> 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
>> ...
>>
>
> Your pop doesn't seem to be in O(1) since you have to walk through  
> the nextNonC stack if the colours don't match.

Yep, this is still O(1) though, as you can guarentee that nextNonC  
will start with something of the correct colour.  Thus the worst case  
here is that we walk once to the nextNonC element, and then do a  
different O(1) operation.

Bob