Immutable Datastructures with good Sharing

[Arne Vajhøj]

Fast forward in this thread, and you find the source of
the class Stack. Or you might lookup up a more extended
version here:

http://blogs.msdn.com/b/ericlippert...y-in-c-part-two-a-simple-immutable-stack.aspx

That is C# not Java.

The same technique may be possible in Java, but it is not Java.

Arne

 

[Jan Burse]

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

 

[Jan Burse]

That is C# not Java.

Yes, you are right.

 

[Arved Sandstrom]

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

 

[Stefan Ram]

Wikipedia defines it as "a widely-used data structure that
emulates a hierarchical tree structure with a set of linked nodes."
That's not a very good definition, since trees need not have links,

For example, here is a binary tree T, with only a right subtree S.

Tree T = new Tree( null, new Tree( null, null ));

T
|
|
|
V
.---.---.
| ø | · |
'---'-|-'
|
|
V
.---.---.
| ø | ø |
'---'---'

The entries of the tree T do not contain subtrees literally,
but /links/ to their subtrees. These links can have a special
null value »ø« to represent the absence of a subtree.

Without links, how does one represent the absence of a
subtree?

Or how does one represent the null tree N?

Tree N = null;

N
ø

 

[Eric Sosman]

Jan Burse schrieb:

Ok, I make it easy for you:

Jan Burse was writing (19:30):

public class Stack {
[...]

Stack.java:6: <identifier> expected
Stack(e, n) {
^
Stack.java:6: <identifier> expected
Stack(e, n) {
^
2 errors

 

[Jan Burse]

Jan Burse schrieb:

Ok, I make it easy for you:

Jan Burse was writing (19:30):

public class Stack {
[...]

Stack.java:6: <identifier> expected
Stack(e, n) {
^
Stack.java:6: <identifier> expected
Stack(e, n) {
^
2 errors

Ok, here comes the revision:

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

Stack(Object e, Stack 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;
}
}

// No license attached

 

[Eric Sosman]

Wikipedia defines it as "a widely-used data structure that
emulates a hierarchical tree structure with a set of linked nodes."
That's not a very good definition, since trees need not have links,

[...]
Without links, how does one represent the absence of a
subtree?

Ever studied Heapsort, or a heap-based priority queue? There's
clearly a tree involved, but where are the links? In a heap of N
elements, element [N-1] has two empty subtrees; how is their absence
denoted?

Or consider the tree (A (B (C D) E (F (G H) I)) () J): Where are
the links? See the empty subtree?

See also Knuth "The Art of Computer Programming, Volume I:
Fundamental Algorithms." The title of section 2.3.3 is "Other
Representations of Trees" ...

 

[Jan Burse]

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

 

[Jan Burse]

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

 

[Jan Burse]

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

 

[Jan Burse]

Interesting, cool! So its possible...

There should be a book titled THE
IMMUTABLES. I would carry it everywhere.

I have one problem with the usability
of Erics blog. He always writes:

Next time: ...

But I did not yet figure out where
I can press a next time link and
directly go to the next article.

Bye

 

[Jan Burse]

Bye

Next requirement would be a fast iterator.

But he has:

public IEnumerator<T> GetEnumerator()
{
foreach (T t in forwards) yield return t;
foreach (T t in backwards.Reverse()) yield return t;
}


The above doesn't looks so efficient with the reverse.

But I didn't mention this in my initial post...

Bye

 

[Eric Sosman]

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*?

 

[Jan Burse]

Why do you want an immutable *Q*U*E*U*E*?

For speed!

And it is possible:

http://blogs.msdn.com/b/ericlippert...bility-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

 

[Jan Burse]

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

 

[markspace]

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.

 

[Arved Sandstrom]

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.

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

 

[markspace]

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.

 

[Jussi Piitulainen]

There should be a book titled THE
IMMUTABLES. I would carry it everywhere.

There is a book titled PURELY FUNCTIONAL DATA
STRUCTURES by Chris Okasaki.