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