Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!aioe.org!eternal-september.org!feeder.eternal-september.org!.POSTED!not-for-mail From: Eric Sosman Newsgroups: comp.lang.java.programmer Subject: Re: Immutable Datastructures with good Sharing Date: Sat, 05 Nov 2011 15:31:24 -0400 Organization: A noiseless patient Spider Lines: 35 Message-ID: References: Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Injection-Date: Sat, 5 Nov 2011 19:32:50 +0000 (UTC) Injection-Info: mx04.eternal-september.org; posting-host="HSlJAUb3pGXi3i7ZL/HoAw"; logging-data="26389"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19USFSseJJoKFftfRe8Ui3s" User-Agent: Mozilla/5.0 (Windows NT 5.1; rv:7.0.1) Gecko/20110929 Thunderbird/7.0.1 In-Reply-To: Cancel-Lock: sha1:49mniejqg4dxoCiCeTJ2Mjyx1Wg= Xref: x330-a1.tempe.blueboxinc.net comp.lang.java.programmer:9591 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