Immutability in C# Part Nine: Academic? Plus my AVL tree implementation

re: Immutability in C# Part Nine: Academic? Plus my AVL tree implementation

Luca Minudel — Sun, 01 Jul 2012 15:16:49 GMT

can you tell more about how immutable objects encourage non-nullable programming more then mutable objects ?

re: Immutability in C# Part Nine: Academic? Plus my AVL tree implementation

Stefan Monov — Thu, 23 Sep 2010 09:08:36 GMT

I agree with Donnie Hale. Your immutable dictionary code looks good, but I don't see myself using it, as I wouldn't know how to make it fit into my main mutating-style code.

For example, you mention a queue, two threads that push to it and one that pops from it. You say it's difficult to write correctly (or even think about), and I agree. Then you introduce the alternative - an immutable queue. Ok, say thread1 wants to push stuff to the queue. So it calls queue.Add a couple of times and gets a larger queue back. Thread2 does the same. So far so good. Now what do those two threads do with their own, larger queues?

1. Do they merge them, (by iterating and skipping identical sequences of members)?

2. Do they just provide an externally queriable "StuffThatMustBePushed" member, and leave it to the reader thread to query that and add it to its own queue?

What would help is some sample (pseudo)code that demonstrates the entire situation you're envisioning with the three threads and the queue.

re: Immutability in C# Part Nine: Academic? Plus my AVL tree implementation

Daniel — Sat, 28 Jun 2008 21:41:48 GMT

Hi, Eric. What do you think abount immutable variable length list? Is it possible to implement it?

re: Immutability in C# Part Nine: Academic? Plus my AVL tree implementation

Ted — Thu, 28 Feb 2008 19:37:41 GMT

Consider approaching you problem as a set of static functions first and then immutable objects next. Static functions force one to write code that a) does not depend on a context being setup b) do not affect things outside of their parameters (if written properly) and c) can easily be moved around in your code.

The non-static pattern of

int functionABC()

{

X a = new object X

a.property_D = 2

a.property_E = 5

...

a.property_G = 6

int r = a.method_call()

return (r)

}

becomes a single line of code, functionABC is not needed and can be removed.

X.method_call(2, 5, 6)

This is is a common code defect since many class objects are designed for reuse in multiple parts of the application but end up being mostly made up of methods that could easily be made static.

Static methods avoid the spaghetti code of needing 3 or more calls to an object (construct, set properties, call method) when the functionality desired is a simple function call without side effects.

re: Immutability in C# Part Nine: Academic? Plus my AVL tree implementation

DRBlaise — Mon, 11 Feb 2008 07:13:26 GMT

I created an Immutible AVL Tree implementation that stores the balance information in different classes so has no need to store or calculate height. It did not lead to simpler code but I think it is more memory and speed effecient. First I created an enum and an additional interface with Balance and IsSingleLeaf properties.

private enum AVLTreeBalance

{

LeftHeavy = -1,

Balanced = 0,

RightHeavy = 1

}

private interface IAVLTree : IBinarySearchTree<K, V>

{

AVLTreeBalance Balance { get; }

bool IsSingleLeaf { get; }

new IAVLTree Add(K key, V value);

new IAVLTree Remove(K key);

new IAVLTree Left { get; }

new IAVLTree Right { get; }

}

Then I created 7 classes to represent different shapes and balance:

private sealed class EmptyAVLTree : IBinarySearchTree<K, V>

private sealed class SingleLeafAVLTree : IAVLTree

private sealed class LeftLeafAVLTree : IAVLTree

private sealed class RightLeafAVLTree : IAVLTree

private sealed class BalancedAVLTree : IAVLTree

private sealed class LeftHeavyAVLTree : IAVLTree

private sealed class RightHeavyAVLTree : IAVLTree

The code was pretty long but I thought I would share the Add for a RightHeavyAVLTree:

public IAVLTree Add(K key, V value)

{ // Add to RightHeavy Tree

int compare = key.CompareTo(Key);

if (compare > 0)

{ // greater than add to right

IAVLTree newRight = Right.Add(key, value);

if (newRight.Balance == Right.Balance || newRight.Balance == AVLTreeBalance.Balanced)

// shape stays the same if right tree keeps same shape

// or if the right tree goes from from unbalanced to balanced (same height)

return new RightHeavyAVLTree(Key, Value, Left, newRight);

else //tree has gained a level on right making it 2 levels greater on right

return RotateLeft(this, Left, newRight);

}

if (compare < 0)

{ // less than add to left

IAVLTree newLeft = Left.Add(key, value);

if (newLeft.Balance == Left.Balance || newLeft.Balance == AVLTreeBalance.Balanced)

// shape stays the same if left tree keeps same shape

// or if the left tree goes from from unbalanced to balanced (same height)

return new RightHeavyAVLTree(Key, Value, newLeft, Right);

else //tree has gained a level on left making it balanced

return new BalancedAVLTree(Key, Value, newLeft, Right);

}

throw new Exception("key already exists");

}

Here is code for RotateLeft and DoubleLeft:

private static IAVLTree RotateLeft(IAVLTree top, IAVLTree left, IAVLTree right)

{ // assumes top has key and value, right's height is 2 greater than left's

if (right.Balance == AVLTreeBalance.RightHeavy)

// Single Left Rotation and shape becomes balanced

return new BalancedAVLTree(right.Key, right.Value,

new BalancedAVLTree(top.Key, top.Value, left, right.Left),

right.Right);

else if (right.Balance == AVLTreeBalance.Balanced)

// Single Left Rotation and shape becomes Left balanced

return new LeftHeavyAVLTree(right.Key, right.Value,

new RightHeavyAVLTree(top.Key, top.Value, left, right.Left),

right.Right);

else //(right.Balance == AVLTreeBalance.LeftHeavy)

// Double Left Rotation and shape becomes balanced

return DoubleLeft(top, left, right);

}

private static IAVLTree DoubleLeft(IAVLTree top, IAVLTree left, IAVLTree right)

{ // assumes top has key and value, right's height is 2 greater than left's

// assumes right tree is left heavy

IAVLTree newTop = right.Left; // right.Left tree becomes new top and controls shape

if (newTop.Balance == AVLTreeBalance.RightHeavy)

// Left is LeftHeavy, Right is Balanced

if (newTop.Right.IsSingleLeaf)

// Left is LeftLeaf

return new BalancedAVLTree(newTop.Key, newTop.Value,

new LeftLeafAVLTree(top.Key, top.Value, left),

new BalancedAVLTree(right.Key, right.Value, newTop.Right, right.Right));

else

// Left is LeftHeavy

return new BalancedAVLTree(newTop.Key, newTop.Value,

new LeftHeavyAVLTree(top.Key, top.Value, left, newTop.Left),

new BalancedAVLTree(right.Key, right.Value, newTop.Right, right.Right));

else if (newTop.Balance == AVLTreeBalance.Balanced)

// Both children Balanced

return new BalancedAVLTree(newTop.Key, newTop.Value,

new BalancedAVLTree(top.Key, top.Value, left, newTop.Left),

new BalancedAVLTree(right.Key, right.Value, newTop.Right, right.Right));

else // (newTop.Balance == AVLTreeBalance.LeftHeavy)

// Left is Balanced, Right is RightHeavy

if (newTop.Left.IsSingleLeaf)

// Right is RightLeaf

return new BalancedAVLTree(newTop.Key, newTop.Value,

new BalancedAVLTree(top.Key, top.Value, left, newTop.Left),

new RightLeafAVLTree(right.Key, right.Value, right.Right));

else

// Right is RightHeavy

return new BalancedAVLTree(newTop.Key, newTop.Value,

new BalancedAVLTree(top.Key, top.Value, left, newTop.Left),

new RightHeavyAVLTree(right.Key, right.Value, newTop.Right, right.Right));

}

re: Immutability in C# Part Nine: Academic? Plus my AVL tree implementation

Codrus — Sun, 10 Feb 2008 09:40:08 GMT

I think there are a couple of errors in the implementation -- or at least it doesn't match the wikipedia article you linked to.

If I use the following code, it should hit the Right Left Case (in your code called a DoubleLeft).

IBinarySearchTree<int, string> tree = AVLTree<int, string>.Empty;

tree = tree.Add(5, "five");

tree = tree.Add(7, "seven");

tree = tree.Add(6, "six");

What I actually get is a single left, same as if I had run it as:

IBinarySearchTree<int, string> tree = AVLTree<int, string>.Empty;

tree = tree.Add(5, "five");

tree = tree.Add(6, "six");

tree = tree.Add(7, "seven");

The main reason for this is that the inner test shouldn't be looking for -2 or +2; -1 or +1 is sufficient.

Changing the tests in MakeBalanced to match the Wikipedia algorithm makes it go down the correct rotation paths, but there's a second bug in RotateRight that causes an exception -- it should be grabbing tree.left.right, not tree.right.left.

re: Immutability in C# Part Nine: Academic? Plus my AVL tree implementation

Donnie Hale — Wed, 06 Feb 2008 02:08:48 GMT

Eric, you said: "When I compare the practical, solving-real-problems code I write using immutable or ("mostly" immutable objects) to that which uses highly mutable objects, I find that the solutions which use immutable objects are easier to reason about."

I don't that that's the case, but so far you're only showing immutable constructs that you can use in those practical situations. I personally would find it helpful if you applied these constructs to real practical situations, perhaps compared to using mutable constructs, with explanation as to why it's easier to reason about, simpler to code, etc.

Thanks, and we appreciate the series.

re: Immutability in C# Part Nine: Academic? Plus my AVL tree implementation

Eric Lippert — Sat, 02 Feb 2008 20:28:41 GMT

That makes perfect sense! Write it up and let us see the code. I'll happily post it here, or a link.

re: Immutability in C# Part Nine: Academic? Plus my AVL tree implementation

DRBlaise — Sat, 02 Feb 2008 18:56:46 GMT

I have been fascinated by this discussion on Immutible data structures and have been doing some of my own research and investigation. It seems that this example of an Immutible AVL tree is missing a couple important optimizations that Immutible data structures lend themselves to.

First, memory can be reduced by creating more classes that represent different shapes of a tree. There is no reason to store empty trees in the left and right variables. SingleLeaf, LeftLeaf and RightLeaf classes can be created similar to the Empty class that do not allocate left and right variables.

Second, even more memory reduction can be created if even more classes are created that represent the different states of Tree Balance. 3 classes can be created that represent non-leaf trees that are Balanced, LeftHeavy, and RightHeavy. This should total get rid of the need to store Height because the class the tree is built from holds information about the balance of the tree similar to the way the IsEmpty property holds information about the shape of the tree. New properties such as IsLeaf, IsBalanced, IsLeftHeavy, and IsRightHeavy can be created for each class. This can also lead to simpler and faster code because each class of tree only needs to deal with its special shape.

Does this make sense or am I all wet?

Community Convergence XL

Noticias externas — Wed, 30 Jan 2008 02:24:15 GMT

Welcome to the fortieth issue of Community Convergence. This week we have two new releases of note: We