Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #9560 > unrolled thread

Immutable Datastructures with good Sharing

Back to article view | Back to comp.lang.java.programmer

Contents

  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

Page 2 of 5 — ← Prev page 1 [2] 3 4 5  Next page →

#9607

Arne Vajhøj schrieb:
>
> How do you know that the clone solution use more CPU than
> the solution you are looking for now??

It has been proven for the stack. I don't know
yet already what the properties are of eventual
solutions for a queue.

But a friend of mine implemented the same application,
and he has a different solution for the queue and
is orders of magnitude faster. (*)

But he doesn't tell me his solution. :-{

Bye

(*) I guess he is using a B-tree, where cloning only
happens along the insert path/delete path, but
otherwise sharing. Hm...

[toc] | [prev] | [next] | [standalone]

#9630

On 11/5/2011 1:41 PM, Jan Burse wrote:
> Arne Vajhøj schrieb:
>>
>> How do you know that the clone solution use more CPU than
>> the solution you are looking for now??
>
> It has been proven for the stack.


I'd like to see that proof.  I think this is the fundamental disconnect 
most people are having on this thread.  What is an immutable stack 
actually good for?  There's nothing that comes to my mind.


> But a friend of mine implemented the same application,
> and he has a different solution for the queue and
> is orders of magnitude faster.


Cloning or copying has got to be slow.  I'd bet this is why your 
solution is slow, even if you don't realize it.

[toc] | [prev] | [next] | [standalone]

#9633

On 11-11-05 09:20 PM, markspace wrote:
> On 11/5/2011 1:41 PM, Jan Burse wrote:
>> Arne Vajhøj schrieb:
>>>
>>> How do you know that the clone solution use more CPU than
>>> the solution you are looking for now??
>>
>> It has been proven for the stack.
> 
> 
> I'd like to see that proof.  I think this is the fundamental disconnect
> most people are having on this thread.  What is an immutable stack
> actually good for?  There's nothing that comes to my mind.

Concurrency. Immutable data structures help in that environment -
nothing special about stacks in that regard.

>> But a friend of mine implemented the same application,
>> and he has a different solution for the queue and
>> is orders of magnitude faster.
> 
> Cloning or copying has got to be slow.  I'd bet this is why your
> solution is slow, even if you don't realize it.
> 
If you are actually really cloning, or copying everything. If you are
looking to implement efficient persistent data structures then the only
bits you copy are the modified bits. The unmodified bits are shared, and
are still immutable.

AHS
-- 
You should know the problem before you try to solve it.
Example: When my son was three he cried about a problem with his hand. I
kissed it several times and asked him about the problem. He peed on his
hand.
-- Radia Perlman, inventor of spanning tree protocol

[toc] | [prev] | [next] | [standalone]

#9636

On 11/5/2011 6:13 PM, Arved Sandstrom wrote:

> On 11-11-05 09:20 PM, markspace wrote:
>> I'd like to see that proof.  I think this is the fundamental disconnect
>> most people are having on this thread.  What is an immutable stack
>> actually good for?  There's nothing that comes to my mind.

> Concurrency. Immutable data structures help in that environment -
> nothing special about stacks in that regard.


Yes, granted, but we don't have any evidence the OP is doing any 
concurrency.  Jan (the OP) has put the cart before the horse, so to 
speak.  He's asking for programming solutions, when the problem domain 
isn't clear.

All we have is some vague assertion that his friend has used an 
immutable something or other (stack? queue? Jan seems unclear on it) and 
that it's "faster."  Why is it faster?  Who's measuring?  How?  Jan 
admits he hasn't seen the code.  I'd bet money his friend's algorithm is 
in fact doing nothing like what Jan supposes.

Jan seems educated, and often poses interesting problems, but at the 
same time he also seem blithering, and frequently confuses concepts that 
have nothing to do with each other, or leaps to irrelevant conclusions.

It's all a load of old pisswiffle if you ask me.

[toc] | [prev] | [next] | [standalone]

#9642

markspace schrieb:
> It's all a load of old pisswiffle if you ask me.
>
I guess you got a bad hairy day today.

[toc] | [prev] | [next] | [standalone]

#9640

markspace schrieb:
> Cloning or copying has got to be slow.

Yes, thats why I wrote (21:33):

"When you clone you need to go through the whole array and copy
each element, this takes time. When you share, you don't need
to spend this time."

Probably there is a problem with the newsreader
used by you guys. I see this over and over by
posts here from various people, they only use
a very small view of the thread as context.

Bye

[toc] | [prev] | [next] | [standalone]

#9579

Jan Burse wrote:
> Stefan Ram schrieb:
>>    However, in computer science, a stack is well known as a
>>    specific mutable entity with specific performance
>>    properties. So, an »immutable stack« should not be called
>>    »stack«.
> 
> If you take the subdomain of functional programming
> in computer science, the people there wouldn't
> probably agree. A stack can be viewed as an abstract
> datatype:
> 
>     push : Stack x Element -> Stack
>     pop : Stack -> Stack x Element | Fault
> 
> By the above one would loose the possibility to directly
> reference a stack by one process. And then see what
> an another process is doing on it.

Your answer does not speak to the inherent contradiction in the term "immutable stack".

-- 
Lew

[toc] | [prev] | [next] | [standalone]

#9580

On 11/5/11 10:06 AM, Lew wrote:
> Jan Burse wrote:
>> Stefan Ram schrieb:
>>>     However, in computer science, a stack is well known as a
>>>     specific mutable entity with specific performance
>>>     properties. So, an »immutable stack« should not be called
>>>     »stack«.
>>
>> If you take the subdomain of functional programming
>> in computer science, the people there wouldn't
>> probably agree. A stack can be viewed as an abstract
>> datatype:
>>
>>      push : Stack x Element ->  Stack
>>      pop : Stack ->  Stack x Element | Fault
>>
>> By the above one would loose the possibility to directly
>> reference a stack by one process. And then see what
>> an another process is doing on it.
>
> Your answer does not speak to the inherent contradiction in the term "immutable stack".

What inherent contradiction?  Please cite an authoritative reference 
that requires that the data structure known simply as a "stack" must be 
implemented using mutable instances.

Requiring mutable instances would mean one could not, for example, 
implement a stack at all in languages like Lisp or XSLT.  Yet having 
done so in both, I find that assertion obviously wrong.

The key to a "stack" is that it orders elements such that there are two 
operations, one to add an element and one to remove an element, and 
those added most recently are removed most recently.  That's all.  In a 
language like Lisp, you don't even need a specialized data structure for 
that; it comes free with the language.

There's nothing about that definition that requires a given instance of 
"stack" to be mutable, any more than having an "int" that allows 
operations such as addition or subtraction requires any given "int" 
instance to be mutable, nor any more than having a "String" that allows 
operations such as concatenation and substring requires any given 
"String" instance to be mutable.

Finally, if the above does not persuade, please let us know: what shall 
we call a data structure that works just like a stack but which uses 
immutable instances, if not a "stack"?  What word do you think is more 
appropriate than "stack" and will communicate the basic nature of the 
data structure in a more efficient, obvious way than the word "stack"?



It's funny.  I realize that in this newsgroup, so many threads devolve 
into this sort of pointless (and usually wrong) criticism of 
terminology.  But here's a relevant discussion that occurred in the 
context of a .NET-related blog, with four pages of comments, and not 
once did anyone stoop to distracting from the real point of the 
discussion to question the use of the word "stack" to describe the data 
structure:
http://blogs.msdn.com/b/ericlippert/archive/2007/12/04/immutability-in-c-part-two-a-simple-immutable-stack.aspx

Quite a contrast.


(By the way, Eric has lots of other good stuff on the topic of 
immutability. See here 
http://blogs.msdn.com/b/ericlippert/archive/tags/immutability/ if you're 
interested in productive reading on the topic, albeit in the context of 
.NET rather than Java).

Pete

[toc] | [prev] | [next] | [standalone]

#9582

Stefan Ram schrieb:
>    In the functional lanugage it is exactly the other way
>    round: It has a result specified, but no effect specified.

I admit that the question might need some out of the box
thinking, especially when somebody makes a strict divide
between Java (destructive, etc..) and functional programming
(non-destructive, etc..).

But I am looking for:

     Some stack class, where: (Easy)
         pop() creates a new immutable stack
         push() creates a new immutable stack
         With good sharing.

     Some queue class, where: (Hard?)
         enqueue() creates a new immutable queue
         dequeue() creates a new immutable queue
         With good sharing.

All of that in !Java!.

The stack is quite easy, a good indicative that
something is immutable are the keywords final
before field variables:

      public class Stack {
           final Object element;
           final Stack next;

           Stack(e, n) {
              element = e;
              next = n;
           }

           public Stack push(Object e) {
              return new Stack(e,this);
           }

           public Object top() {
              return element;
           }

           public Stack pop() {
              return next;
           }
       }

But how about the Queue?

Best Regards

P.S.: In LISP one just uses the CONS for
push, the CAR for top, and the CDR for pop.

[toc] | [prev] | [next] | [standalone]

#9625

On 11/5/2011 2:30 PM, Jan Burse wrote:
>
> But I am looking for:
>
> Some stack class, where: (Easy)
> pop() creates a new immutable stack
> push() creates a new immutable stack
> With good sharing.

     This has already been answered: Build a tree.

> Some queue class, where: (Hard?)
> enqueue() creates a new immutable queue
> dequeue() creates a new immutable queue
> With good sharing.

     We're all still wondering why you want this one.  Every time
you've been asked, you've replied by talking about stacks, writing
pseudocode for stacks, and just stacking it higher and higher.
Why do you want an immutable *Q*U*E*U*E*?

-- 
Eric Sosman
esosman@ieee-dot-org.invalid

[toc] | [prev] | [next] | [standalone]

#9626

Eric Sosman schrieb:
> Why do you want an immutable *Q*U*E*U*E*?

For speed!

And it is possible:

http://blogs.msdn.com/b/ericlippert/archive/2007/12/10/immutability-in-c-part-four-an-immutable-queue.aspx

It is in his second solution:

It looks as follows:

        ---- 1. stack --- | --- 2. stack (shown reverse) ---

       ^ pop here = dequeue              enqueue = push here ^

He argues that we have in the average O(1), although
when 1. stack gets empty, 2. stack needs to be reverse.

Interesting, cool!

Bye

[toc] | [prev] | [next] | [standalone]

#9628

Eric Sosman schrieb:
> Why do you want an immutable *Q*U*E*U*E*?

Well the correct answer would be. The reason that
my queues should be immutable, are exactly the same
as for the stacks. I want to see the history.

I wrote 19:52:

"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."

Just find+replace stack by queue, and you have
the requirements for the queue.

Bye

[toc] | [prev] | [next] | [standalone]

#9610

On 11-11-05 02:55 PM, Peter Duniho wrote:
[ SNIP ]

> It's funny.  I realize that in this newsgroup, so many threads devolve
> into this sort of pointless (and usually wrong) criticism of
> terminology.  But here's a relevant discussion that occurred in the
> context of a .NET-related blog, with four pages of comments, and not
> once did anyone stoop to distracting from the real point of the
> discussion to question the use of the word "stack" to describe the data
> structure:
> http://blogs.msdn.com/b/ericlippert/archive/2007/12/04/immutability-in-c-part-two-a-simple-immutable-stack.aspx
> 
> Quite a contrast.
[ SNIP ]

Good post.

AHS
-- 
You should know the problem before you try to solve it.
Example: When my son was three he cried about a problem with his hand. I
kissed it several times and asked him about the problem. He peed on his
hand.
-- Radia Perlman, inventor of spanning tree protocol

[toc] | [prev] | [next] | [standalone]

#9617

On 11/5/11 11:15 AM, Stefan Ram wrote:
> Peter Duniho<NpOeStPeAdM@NnOwSlPiAnMk.com>  writes:
>> What inherent contradiction?  Please cite an authoritative reference
>> that requires that the data structure known simply as a "stack" must be
>> implemented using mutable instances.
>
>    The most authoritative reference whatsoever, world-wide surely is
>    the renowned internet encyclopedia »Wikipedia«. And this says:
>
>        »The push operation adds a new item to the top of the stack«
>
> http://en.wikipedia.org/wiki/Stack_(abstract_data_type)
>
>    . »Add« is a /mutation/, it means to /change/ something by
>    /adding/ something to it.

Yes, add is a mutation.  It means to change something by adding 
something to it.  So, when you add two integers, why is that permitted, 
given that "int" is an immutable type?  When you add two strings (i.e. 
concatenate), why is that permitted, given that "String" is an immutable 
type?

Hint: you are confusing the question of changing something with the 
question of where the result of that change goes.

Certainly, there's nothing on Wikipedia (which frankly, is not "the most 
authoritative reference whatsoever" in any case) supports your claim.

I notice you also have failed to offer a more appropriate term.  Very 
telling.

>    In this context, the verb »add« has
>    the same meaning as in everyday language. The push operation
>    has no result specified, but it has an effect specified.
>
>    In the functional lanugage it is exactly the other way
>    round: It has a result specified, but no effect specified.
>
>> Requiring mutable instances would mean one could not, for example,
>> implement a stack at all in languages like Lisp or XSLT.
>
>    In Common Lisp, one /can/ implement mutable data structures.

Yes, there are variations of functional language that introduce 
mutability.  So?  That doesn't change the fact that mutability is not 
required in order to implement a stack.

Pete

[toc] | [prev] | [next] | [standalone]

#9596

On 11/5/2011 1:06 PM, Lew wrote:
> Jan Burse wrote:
>> Stefan Ram schrieb:
>>>     However, in computer science, a stack is well known as a
>>>     specific mutable entity with specific performance
>>>     properties. So, an »immutable stack« should not be called
>>>     »stack«.
>>
>> If you take the subdomain of functional programming
>> in computer science, the people there wouldn't
>> probably agree. A stack can be viewed as an abstract
>> datatype:
>>
>>      push : Stack x Element ->  Stack
>>      pop : Stack ->  Stack x Element | Fault
>>
>> By the above one would loose the possibility to directly
>> reference a stack by one process. And then see what
>> an another process is doing on it.
>
> Your answer does not speak to the inherent contradiction in the term "immutable stack".

Given the example with Integer in his first post, then it should be
rather obvious what he means with immutable stack.

Whether that thingy should be called stack or not can be relevant
but maybe a little focus on the question asked first would be
good.

Arne

[toc] | [prev] | [next] | [standalone]

#9618

On 11/4/11 8:03 PM, Jan Burse wrote:
> [...]I am looking for:
>
> Some stack class, where: (Easy)
> pop() creates a new immutable stack
> push() creates a new immutable stack
> With good sharing.
>
> Some queue class, where: (Hard?)
> enqueue() creates a new immutable queue
> dequeue() creates a new immutable queue
> With good sharing.

You have already seen the article Eric Lippert wrote on an immutable 
stack.  On the same blog are two different queue implementations. 
Here's the first:
http://blogs.msdn.com/b/ericlippert/archive/2007/12/10/immutability-in-c-part-four-an-immutable-queue.aspx

There are also implementations of a double-ended queue and a binary 
tree.  As I suggested earlier, browse through the articles under the 
"Immutability" tag for those and other good info.

All the code is C#, but other than the iterator methods it should be 
fairly trivial to port to Java (and I don't think iterator methods are a 
critical point of the data structure).

Once you have seen those examples, hopefully that will help you see some 
of the basic techniques used that can lead you to implementations of 
other complex immutable data structures you might want.

Pete

[toc] | [prev] | [next] | [standalone]

#9619

Peter Duniho schrieb:
> Once you have seen those examples, hopefully that will help you see some
> of the basic techniques used that can lead you to implementations of
> other complex immutable data structures you might want.
>
> Pete

It fullfils the requirement of immutable. But it has no sharing.

   public IQueue<T> Enqueue(T t) {
       return new Queue<T>(backwards.Push(t)); }
   public IQueue<T> Dequeue(T t) {
       return new Queue<T>(backwards.Reverse().Pop().Reverse()); }

Eric himself remarks when initially defining Reverse:

   This is an O(n) operation for a stack of size n.

So I guess we did not yet find a solution.

Bye

[toc] | [prev] | [next] | [standalone]

#9620

Jan Burse schrieb:
> So I guess we did not yet find a solution.
>
> Bye
>
>

But he has a second solution:

This looks as follows:

        ---- 1. stack --- | --- 2. stack (shown reverse) ---

       ^ pop here = dequeue              enqueue = push here ^

Then he argues that we have in the average O(1), although
when 1. stack gets empty, 2. stack needs to be reverse.

Interesting, cool!

Bye

[toc] | [prev] | [next] | [standalone]

#9621

On 11/5/11 2:42 PM, Jan Burse wrote:
> Peter Duniho schrieb:
>> Once you have seen those examples, hopefully that will help you see some
>> of the basic techniques used that can lead you to implementations of
>> other complex immutable data structures you might want.
>>
>> Pete
>
> It fullfils the requirement of immutable. But it has no sharing.
>
> public IQueue<T> Enqueue(T t) {
> return new Queue<T>(backwards.Push(t)); }
> public IQueue<T> Dequeue(T t) {
> return new Queue<T>(backwards.Reverse().Pop().Reverse()); }
>
> Eric himself remarks when initially defining Reverse:
>
> This is an O(n) operation for a stack of size n.
>
> So I guess we did not yet find a solution.

Yes, I agree…if you are looking for someone who has already done your 
work for you, then the link I offered doesn't specifically answer your 
question.

But maybe you can learn something from it anyway.  You may even find 
that it's not practical to expect an immutable queue to have "good sharing".

Pete

[toc] | [prev] | [next] | [standalone]

#9622

But he has a second solution:

This looks as follows:

        ---- 1. stack --- | --- 2. stack (shown reverse) ---

       ^ pop here = dequeue              enqueue = push here ^

Then he argues that we have in the average O(1), although
when 1. stack gets empty, 2. stack needs to be reverse.

Interesting, cool! So its possible...

Bye


Peter Duniho schrieb:
> On 11/5/11 2:42 PM, Jan Burse wrote:
>> Peter Duniho schrieb:
>>> Once you have seen those examples, hopefully that will help you see some
>>> of the basic techniques used that can lead you to implementations of
>>> other complex immutable data structures you might want.
>>>
>>> Pete
>>
>> It fullfils the requirement of immutable. But it has no sharing.
>>
>> public IQueue<T> Enqueue(T t) {
>> return new Queue<T>(backwards.Push(t)); }
>> public IQueue<T> Dequeue(T t) {
>> return new Queue<T>(backwards.Reverse().Pop().Reverse()); }
>>
>> Eric himself remarks when initially defining Reverse:
>>
>> This is an O(n) operation for a stack of size n.
>>
>> So I guess we did not yet find a solution.
>
> Yes, I agree…if you are looking for someone who has already done your
> work for you, then the link I offered doesn't specifically answer your
> question.
>
> But maybe you can learn something from it anyway. You may even find that
> it's not practical to expect an immutable queue to have "good sharing".
>
> Pete

[toc] | [prev] | [next] | [standalone]

Page 2 of 5 — ← Prev page 1 [2] 3 4 5  Next page →

Back to top | Article view | comp.lang.java.programmer

csiph-web