Groups > comp.lang.java.programmer > #9591

Re: Immutable Datastructures with good Sharing

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 <esosman@ieee-dot-org.invalid>
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	<j94312$pol$1@dont-email.me> (permalink)
References	<j9292v$f69$1@news.albasani.net> <stack-20111105042359@ram.dialup.fu-berlin.de> <j937eq$7k4$1@news.albasani.net> <j93oju$h78$1@dont-email.me> <j93vh6$sra$2@news.albasani.net> <j94032$61p$1@dont-email.me> <j940m9$9k$1@news.albasani.net>
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	<j940m9$9k$1@news.albasani.net>
Cancel-Lock	sha1:49mniejqg4dxoCiCeTJ2Mjyx1Wg=
Xref	x330-a1.tempe.blueboxinc.net comp.lang.java.programmer:9591

Show key headers only | View raw

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

Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-05 04:03 +0100
  Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-05 12:42 +0100
    Re: Immutable Datastructures with good Sharing markspace <-@.> - 2011-11-05 09:35 -0700
      Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-05 19:33 +0100
        Re: Immutable Datastructures with good Sharing Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-11-05 14:42 -0400
          Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-05 19:52 +0100
            Re: Immutable Datastructures with good Sharing Andreas Leitgeb <avl@gamma.logic.tuwien.ac.at> - 2011-11-05 19:32 +0000
            Re: Immutable Datastructures with good Sharing Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-11-05 15:31 -0400
              Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-05 20:50 +0100
                Re: Immutable Datastructures with good Sharing Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-11-05 16:26 -0400
                Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-05 21:35 +0100
                Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-05 21:38 +0100
                Re: Immutable Datastructures with good Sharing Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-11-05 16:59 -0400
                Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-05 22:06 +0100
                Re: Immutable Datastructures with good Sharing Arne Vajhøj <arne@vajhoej.dk> - 2011-11-05 16:41 -0400
                Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-05 21:42 +0100
                Re: Immutable Datastructures with good Sharing Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-11-05 17:11 -0400
            Re: Immutable Datastructures with good Sharing Arne Vajhøj <arne@vajhoej.dk> - 2011-11-05 16:20 -0400
              Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-05 21:33 +0100
                Re: Immutable Datastructures with good Sharing Arne Vajhøj <arne@vajhoej.dk> - 2011-11-05 16:38 -0400
                Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-05 21:41 +0100
                Re: Immutable Datastructures with good Sharing markspace <-@.> - 2011-11-05 17:20 -0700
                Re: Immutable Datastructures with good Sharing Arved Sandstrom <asandstrom3minus1@eastlink.ca> - 2011-11-05 22:13 -0300
                Re: Immutable Datastructures with good Sharing markspace <-@.> - 2011-11-05 20:05 -0700
                Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-06 10:27 +0100
                Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-06 10:14 +0100
    Re: Immutable Datastructures with good Sharing Lew <lewbloch@gmail.com> - 2011-11-05 10:06 -0700
      Re: Immutable Datastructures with good Sharing Peter Duniho <NpOeStPeAdM@NnOwSlPiAnMk.com> - 2011-11-05 10:55 -0700
        Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-05 19:30 +0100
          Re: Immutable Datastructures with good Sharing Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-11-05 18:16 -0400
            Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-05 23:20 +0100
            Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-05 23:38 +0100
        Re: Immutable Datastructures with good Sharing Arved Sandstrom <asandstrom3minus1@eastlink.ca> - 2011-11-05 17:47 -0300
        Re: Immutable Datastructures with good Sharing Peter Duniho <NpOeStPeAdM@NnOwSlPiAnMk.com> - 2011-11-05 14:26 -0700
      Re: Immutable Datastructures with good Sharing Arne Vajhøj <arne@vajhoej.dk> - 2011-11-05 16:14 -0400
  Re: Immutable Datastructures with good Sharing Peter Duniho <NpOeStPeAdM@NnOwSlPiAnMk.com> - 2011-11-05 14:35 -0700
    Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-05 22:42 +0100
      Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-05 22:50 +0100
      Re: Immutable Datastructures with good Sharing Peter Duniho <NpOeStPeAdM@NnOwSlPiAnMk.com> - 2011-11-05 14:51 -0700
        Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-05 22:58 +0100
          Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-05 23:03 +0100
            Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-05 23:07 +0100
            Re: Immutable Datastructures with good Sharing Jussi Piitulainen <jpiitula@ling.helsinki.fi> - 2011-11-06 09:44 +0200
              Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-06 10:22 +0100
                Re: Immutable Datastructures with good Sharing Arved Sandstrom <asandstrom3minus1@eastlink.ca> - 2011-11-06 09:05 -0400
                Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-06 14:16 +0100
                Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-06 14:22 +0100
                Re: Immutable Datastructures with good Sharing Andreas Leitgeb <avl@gamma.logic.tuwien.ac.at> - 2011-11-06 14:30 +0000
                Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-06 16:02 +0100
                Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-06 16:08 +0100
                Re: Immutable Datastructures with good Sharing Giovanni Azua <bravegag@hotmail.com> - 2011-11-06 16:18 +0100
                Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-06 16:54 +0100
                Re: Immutable Datastructures with good Sharing Giovanni Azua <bravegag@hotmail.com> - 2011-11-06 17:31 +0100
                Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-06 22:33 +0100
                Re: Immutable Datastructures with good Sharing Arne Vajhøj <arne@vajhoej.dk> - 2011-11-06 16:47 -0500
                Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-06 16:58 +0100
                Re: Immutable Datastructures with good Sharing Tom Anderson <twic@urchin.earth.li> - 2011-11-07 01:01 +0000
                Re: Immutable Datastructures with good Sharing Lew <lewbloch@gmail.com> - 2011-11-06 17:26 -0800
                Re: Immutable Datastructures with good Sharing Tom Anderson <twic@urchin.earth.li> - 2011-11-07 23:45 +0000
                Re: Immutable Datastructures with good Sharing Lew <lewbloch@gmail.com> - 2011-11-06 14:44 -0800
                Re: Immutable Datastructures with good Sharing Arne Vajhøj <arne@vajhoej.dk> - 2011-11-06 17:51 -0500
                Re: Immutable Datastructures with good Sharing Giovanni Azua <bravegag@hotmail.com> - 2011-11-07 01:28 +0100
                Re: Immutable Datastructures with good Sharing Arne Vajhøj <arne@vajhoej.dk> - 2011-11-06 19:50 -0500
                Re: Immutable Datastructures with good Sharing Giovanni Azua <bravegag@hotmail.com> - 2011-11-07 02:13 +0100
                Re: Immutable Datastructures with good Sharing Arne Vajhøj <arne@vajhoej.dk> - 2011-11-06 20:20 -0500
                Re: Immutable Datastructures with good Sharing Lew <lewbloch@gmail.com> - 2011-11-06 17:29 -0800
                Re: Immutable Datastructures with good Sharing Giovanni Azua <bravegag@hotmail.com> - 2011-11-07 11:22 +0100
                Re: Immutable Datastructures with good Sharing Tom Anderson <twic@urchin.earth.li> - 2011-11-06 23:02 +0000
                Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-07 00:32 +0100
                Re: Immutable Datastructures with good Sharing Giovanni Azua <bravegag@hotmail.com> - 2011-11-07 01:10 +0100
                Re: Immutable Datastructures with good Sharing Andreas Leitgeb <avl@gamma.logic.tuwien.ac.at> - 2011-11-07 10:24 +0000
                Re: Immutable Datastructures with good Sharing Giovanni Azua <bravegag@hotmail.com> - 2011-11-07 11:52 +0100
                Re: Immutable Datastructures with good Sharing Andreas Leitgeb <avl@gamma.logic.tuwien.ac.at> - 2011-11-07 11:12 +0000
                Re: Immutable Datastructures with good Sharing Arne Vajhøj <arne@vajhoej.dk> - 2011-11-07 17:24 -0500
                Re: Immutable Datastructures with good Sharing Giovanni Azua <bravegag@hotmail.com> - 2011-11-07 02:08 +0100
                Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-07 05:03 +0100
                Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-07 05:13 +0100
                Re: Immutable Datastructures with good Sharing Tom Anderson <twic@urchin.earth.li> - 2011-11-07 23:38 +0000
                Re: Immutable Datastructures with good Sharing Tom Anderson <twic@urchin.earth.li> - 2011-11-09 22:06 +0000
                Re: Immutable Datastructures with good Sharing Gene Wirchenko <genew@ocis.net> - 2011-11-09 18:02 -0800
  Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-07 00:28 +0100
    Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-07 00:39 +0100
      Re: Immutable Datastructures with good Sharing Arved Sandstrom <asandstrom3minus1@eastlink.ca> - 2011-11-06 20:57 -0400
        Re: Immutable Datastructures with good Sharing Jan Burse <janburse@fastmail.fm> - 2011-11-07 04:58 +0100
          Re: Immutable Datastructures with good Sharing Silvio Bierman <silvio@moc.com> - 2011-11-07 15:13 +0100
            Re: Immutable Datastructures with good Sharing Cthun <cthun_202@qmail.net.au> - 2011-11-07 12:54 -0500
              Re: Immutable Datastructures with good Sharing "B1ll Gat3s" <wm.g4t3s@m1cr0s0f7.c0m> - 2011-11-07 18:07 -0500
                Re: Immutable Datastructures with good Sharing B1ll Gat3s <wm.g4t3s@m1cr0s0f7.c0m> - 2011-11-07 22:07 -0500
                Re: Immutable Datastructures with good Sharing "B1ll Gat3s" <wm.g4t3s@m1cr0s0f7.c0m> - 2011-11-08 00:17 -0500
                Re: Immutable Datastructures with good Sharing thoolen <th00len@th0lenbot.thorium> - 2011-11-08 16:03 -0500
                Re: Immutable Datastructures with good Sharing Cthun <cthun_202@qmail.net.au> - 2011-11-08 15:49 -0500
                Re: Immutable Datastructures with good Sharing "B1ll Gat3s" <wm.g4t3s@m1cr0s0f7.c0m> - 2011-11-08 18:01 -0500
                Re: Immutable Datastructures with good Sharing thoolen <th00len@th0lenbot.thorium> - 2011-11-08 20:46 -0500
                Re: Immutable Datastructures with good Sharing "Cthun" <cthun_202@qmail.net.au> - 2011-11-08 22:43 -0500
                Re: Immutable Datastructures with good Sharing thoolen <th00len@th0lenbot.thorium> - 2011-11-09 08:28 -0500
                Re: Immutable Datastructures with good Sharing thoolen <th00len@th0lenbot.thorium> - 2011-11-08 16:00 -0500
  Re: Immutable Datastructures with good Sharing Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2011-11-07 08:46 -0800

csiph-web