Matthew Brecknell wrote:
Matthew Eastman said:
i.e. popping Blue in [Red, Red, Blue, Red, Blue] would give [Red, Red, Blue]
Hmm, did you mean [Red,Blue] or [Red,Red,Red,Blue]? Judging by your implementation of remUseless, I'm guessing the latter.
Yes, I meant the latter. Popping Blue in [Red, Red, Blue, Red, Blue] should give [Red, Red, Red, Blue]. Sorry for the confusion, I shouldn't be writing emails at midnight I guess! apfelmus wrote:
...
Our lists won't store any elements at all!
newtype List a = Length Int deriving (Eq,Show,Num)
Instead, we're only storing the length of the list, so that
empty list corresponds to 0 tail corresponds to n-1 ++ corresponds to +
...
Regards, apfelmus
Wow! That's a really clever way to think about a list. The way that you push blue elements is pretty interesting too, switching the positions of the lists and doing a regular push. Very insightful posts. I'm slowly reading through Okasaki's thesis now, I'm not sure how much of it I'm understanding but it seems pretty interesting. I had no idea that functional (I suppose "persistent" is the correct word) data structures were so different from ephemeral ones. 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. Thanks for the help everyone, Matt