[Haskell-cafe] Red-Blue Stack
mg.eastman at gmail.com
Sat Sep 27 09:36:42 EDT 2008
Matthew Brecknell wrote:
> Matthew Eastman said:
>> i.e. popping Blue in [Red, Red, Blue, Red, Blue] would give [Red,
> 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!
> 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 +
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)
> 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,
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Haskell-Cafe