[Haskell-cafe] Red-Blue Stack

Thomas Davie tom.davie at gmail.com
Sat Sep 27 09:44:18 EDT 2008


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


More information about the Haskell-Cafe mailing list