It won't be O(1) but this is how I would do it. It uses alternating lists of
red and blue elements. It has to access at most three elements from this list
for any one operation so as long as we don't have huge blocks of red or blue
elements performance should be quite good.
The worst case I
There was a bug in there with popping the non-head colour off the stack.
Updated code, please test thoroughly:
module RBStack where
data RBColour = Red | Blue
deriving (Show, Eq)
data RBStack a = RBStack {
headColour :: RBColour,
stackElems :: [[a]]
}
deriving (Show, Eq)
otherCol ::
Josef Svenningsson wrote:
Stephan Friedrichs wrote:
My question is: Is there a case, where finding a persistent
solution that performs equally well is *impossible* rather than just
harder? I mean might there be a case where (forced) persistence (as we
have in pure Haskell) is a definite
Thomas Davie wrote:
Matthew Eastman wrote:
The part of the assignment I'm working on is to implement a
RedBlueStack, a stack where you can push items in as either Red or
Blue. You can pop Red and Blue items individually, but the stack has
to keep track of the overall order of items.
i.e.
On 27 Sep 2008, at 20:16, apfelmus wrote:
Thomas Davie wrote:
Matthew Eastman wrote:
The part of the assignment I'm working on is to implement a
RedBlueStack, a stack where you can push items in as either Red or
Blue. You can pop Red and Blue items individually, but the stack has
to keep
I'm a haskell beginner so the following code might not meet haskell
coding standards. I think that it is a correct O(1) implementation.
Sorry if i simply recoded an already posted solution that i did not
understand correctly.
--- code -
module Main where
data Col a
= Red a
| Blue a
apfelmus wrote:
data Stack2 r b = Empty | S [r] (Stack2 b r) deriving (Eq, Show)
In the previous post, I considered an implementation of red-blue stacks
with the data type above. Unfortunately, it failed to perform in O(1)
time because list concatenation needs linear time:
xs ++ ys takes
This is a very good post and a clever idea. Thanks!
Luke
On Fri, Sep 26, 2008 at 3:30 AM, apfelmus [EMAIL PROTECTED] wrote:
apfelmus wrote:
data Stack2 r b = Empty | S [r] (Stack2 b r) deriving (Eq, Show)
In the previous post, I considered an implementation of red-blue stacks
with the
apfelmus wrote:
[..]
Persistent data structures are harder to come up with than ephemeral
ones, [...]
Yes, in some cases it's quite hard to find a persistent solution for a
data structure that is rather trivial compared to its ephemeral
counterpart. My question is: Is there a case, where
On 26 Sep 2008, at 19:18, Stephan Friedrichs wrote:
apfelmus wrote:
[..]
Persistent data structures are harder to come up with than ephemeral
ones, [...]
Yes, in some cases it's quite hard to find a persistent solution for a
data structure that is rather trivial compared to its ephemeral
On Fri, Sep 26, 2008 at 7:18 PM, Stephan Friedrichs
[EMAIL PROTECTED] wrote:
apfelmus wrote:
[..]
Persistent data structures are harder to come up with than ephemeral
ones, [...]
Yes, in some cases it's quite hard to find a persistent solution for a
data structure that is rather trivial
Jamie Brandon wrote:
Try writing
data RBStack = RBS [RBSItem] [RBSItem]
where the first list are all the same colour and the start of the second list
is a different colour. The rest should follow naturally and you will get
amortised O(1) push and pop (you occasionally have to juggle the
I am afraid, but this does not give constant amortized time.
sendEmail :: ProperlyThoughtOut Idea - IO ()
Clearly my brain lacks a type checker.
Jamie
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
13 matches
Mail list logo
