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