Re: Immutable Datastructures with good Sharing
On 11/5/2011 2:52 PM, Jan Burse wrote:
Eric Sosman schrieb:
Out of curiosity, why do you want an immutable queue? What
problem are you trying to solve?
Well it has to be seen in the context of garbage collection.
For example the immutable stack can have a good performance.
For push you just grab a new stack cell from the heap.
First, "stack" and "queue" are not usually thought of as
synonyms. Second, I don't see what immutability has to do with
the queue's or stack's internal memory management -- especially
if the claimed performance benefits are only seen when mutations
occur! Third, have you looked at LinkedList?
In the current situation at hand, you can imagine that
some pointers to the datastructure will nevertheless
still remain, so that I can kind of have a historical
view of what happened with the stack.
The obvious way to represent the history of a stack is to
build a tree. For queues (which is what you asked about), the
situation is less obvious -- One can, of course, implement a
queue as a pair of stacks and keep histories of the stacks, but
it's not clear that such a history would be useful.
This historical view is easiest implemented by an immutable
data structure,[...]
Why? How is this superior to a tree? What advantage does
immutability grant? And what happened to queues?
--
Eric Sosman
esosman@ieee-dot-org.invalid