Re: Immutable Datastructures with good Sharing
On 11/5/2011 3:50 PM, Jan Burse wrote:
Eric Sosman schrieb:
Why? How is this superior to a tree?
I don't know what you mean by tree.
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,
but it's close enough for jazz.
Via the immutable stack
also a tree arises.
If you don't know what I mean by tree, I don't know what you
mean by tree, either.
Known as spaghetti stack:
http://en.wikipedia.org/wiki/Spaghetti_stack
Never heard the term before. It looks like a tree to me, of
the kind that arises when processing equivalence relations, for example.
Lets write [a,b,c] for new Stack("a",new Stack("b",new Stack("c",null))).
Sorry; you've lost me again. You're clearly not talking about
java.util.Stack (because it has no such constructor), so you must
mean some other kind of Stack -- but you haven't explained what this
Stack is like, so the meaning of your example remains private to you.
> What advantage does immutability grant?
Immutability grants that the tree does not change, but only
grow. And only the variable pointers might change. And via
GC the tree might also shrink in memory.
I seem to be having trouble with reading comprehension today.
First, in what sense can the tree grow without changing? Second,
what can be garbage-collected from a tree that only grows and
never shrinks?
--
Eric Sosman
esosman@ieee-dot-org.invalid