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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
