[Haskell-cafe] Red-Blue Stack

[Matthew Eastman]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20080927/2a4179c4/attachment.htm