Protected Semantics, Part Five: More on immutability

I asked a second follow-up question back in Part Two:

Suppose you wanted to make this hierarchy an immutable collection, where "Add" and "Remove" returned new collections rather than mutating the existing collection. How would you represent the parenting relationship?

The short answer is "I wouldn't". First off, it sounds an awful lot like what is intended to be represented here is some sort of highly mutable system, where objects are being added and removed from containers. It might be more sensible to represent that thing using mutable data structures rather than immutable data structures.

If you did want to represent the thing with immutable data structures, then I would think twice before attempting to represent parenting at all. Here's why: when you have an immutable tree structure without parents, and you want to make a new tree structure that is based on an old one, typically the only stuff you have to change is from the edited node on up to the root node; usually hierarchies are shallow, so this is not very many nodes.

But this logically implies that the root node changes on every edit. If the root node changes, then all of its children have a new parent, and all of their children then have a new parent... and you've just rewritten the entire tree structure, not just a few nodes.

Now, it is often highly convenient to know what the parent of a given node is. To achieve that, what I'd probably do is try to not need to query the parent of any node until I was at a point where I wanted to ask about a lot of parents, and the tree was likely to remain unedited while I was asking. A quick visitor pass that builds up a hash table mapping every node to its parent would be easy enough to write, and then the parent table could be discarded and its memory reclaimed once I was done.

Comments

• Anonymous
  May 06, 2008
  PingBack from http://www.alvinashcraft.com/2008/05/06/dew-drop-may-6-2008/

• Anonymous
  May 08, 2008
  Eric, Could you post an example of how to actually use such immutable collections? As I understood it, you would need a mutable reference, to the current collection. If you want to share it with other classes - allowing them to have "write access" - it would have to be a dedicated container object I also seem to have missed a point on thread safety. If used in a multithreaded environment, then every modification of the reference would also have to be locked either. Given an example with a producer, a consumer, and a buffering queue, it could be easy to get unwanted results when there is no locking involved: class Example { Queue<int> queue = Queue<int>.Empty; void Producer(object dummy) { const int count=100; Random r = new Random(); for (int i=0; i<count; i++) { int val = r.Next(1000); queue = queue.Enqueue(val); } } void Consumer(object dummy) { while (!queue.IsEmpty) { Queue<int>curr = queue; queue = curr.Dequeue(); Thread.Sleep(curr.Peek()); } } void RunExample() { ThreadPool.QueueUserWorkItem(new WaitCallBack(Producer)); Thread.Sleep(0); ThreadPool.QueueUserWorkItem(new WaitCallBack(Consumer)); } If the consumer finishes Queue.Dequeue() and updates the queue reference while producer is running Queue.Enqueue(), the dequeued element will be in the queue again once the producer updates the reference. And if the producer finishes Queue.Enqueue() and updates the queue ref while the consumer is running Queue.Dequeue(), the last Enqueued item is lost. So, it seems to me that using immutable objects is as thread(un)safe (requires same locking) as using mutables.

• Anonymous
  May 09, 2008
  The comment has been removed

• Anonymous
  May 12, 2008
  The comment has been removed

• Anonymous
  May 22, 2008
  Rather than place the links to the most recent C# team content directly in Community Convergence , I