Introduction
Fundamental to the concept of a variable in functional languages is referential transparency, where same function with same arguments will always give same results. Referential transparency means that there is no difference between a value, and a reference to that value. In functional code, the output value of a function depends only on the arguments that are input to the function, so calling a function f twice with the same value for an argument x will produce the same result f(x) each time. Eliminating side effects, i.e. changes in state that do not depend on the function inputs, can make it much easier to understand and predict the behavior of a program, which is one of the key motivations for the development of functional programming.
An immutable object is an object whose state cannot be modified after it is created. In multi-threaded or multi processor applications that is a great thing. It allows for a thread or process to act on data represented by immutable objects without worrying what other threads or processors are up to. A function which is passed or used mutable objects (either as parameters or in the global environment) may or may not produce side effects. This is up to the implementation. However, it is impossible to produce side effects for a function which passes or uses only immutable objects. Therefore, exclusive use of immutable objects will guaranty the possibility of no side effects.
If no side effects in functions are gurrented, it's much easier to use a theorem prover to reduce a function composition to a mathematically equivalent optimized version. However, the main practical 'optimization' advantages to get from immutability or referential transparency are things like the ability to do 'common sub-expression elimination’ because immutability can guarantee that contents of certain memory cells are not changed.
In summary, following advantages are available if only immutable objects are used in programming:
- It is simpler to read when the reader doesn't have to look out for surprising side effects of program (no defensive copies).
- In multiple threads or multiple processors, locking is not required because shared objects can never change.
- IDE can refractor or compiler can optimize some code better if it uses only immutable types.
- Immutable objects are simpler to construct, test, use, debug, get corrected, parallelize, profile, and decide which the most important bottlenecks are.
- Immutable object helps to avoid temporal coupling.
- Identity mutability problem can be avoided using Immutable object.
- Immutable objects always have failure atomicity.
- Immutable objects are much easier to cache.
During Change of Immutable Object
A new object is required to create for any change of an immutable object, which may contains both mutable and immutable children. But, without creating deep copy, such newly created objects will mostly refer to the children except where the changes are required. If immutable children have reference of their parents (immutable bidirectional reference through laziness), respective children need to be recreated with the reference of newly created parent.
In C# ReadOnlyCollection makes an array or List read-only. With this type from System.Collections.ObjectModel, a collection of elements can be created that cannot be changed. But it may be possible to change some elements themselves. In the ReadOnlyCollection constructor, no elements are copied. Instead it adds a level of indirection that reduces possible changes. So, the constructor is fast. With ReadOnlyCollection, the collection itself is read-only. This means that if a ReadOnlyCollection of “int” is created, nothing can be changed. Ints are value types. Changing an “int” in the collection would require changing the collection itself. On the other hand, for a ReadOnlyCollection of any mutable object, individual object can be changed by accessing their methods. The object references themselves are read-only, but the memory pointed to by the references is still mutable.
Similarly, The ReadOnlyDictionary class behaves in a similar manner to the generic ReadOnlyCollection class. The key difference is that the class is a wrapper for a dictionary containing key / value pairs, rather than for a simple list of values.
Unlike Collection and Dictionary, C# doesn’t have any such ReadOnly collection for hierarchical data type like Tree. Trees are a data structure consisting of one or more data nodes. The first node is called the "root", and each node has zero or more "child nodes" called children, where children are represented with some Collection or Dictionary of other Nodes. A node is a structure which may contain a value, a condition, or represent a separate data structure, which could be a tree of its own. A node that has a child is called the child's parent node or ancestor node, or superior. A node has at most one parent. Nodes that do not have any children are called leaf nodes. They are also referred to as terminal nodes. Design of immutable tree should be such that each immutable tree refers to its own immutable children trees. However, it is difficult to get complete immutable tree route with bidirectional reference especially for multi-parents condition.
Background
Understanding the real usefulness of ReadOnly type data structure, C#/.NET framework is gradually filling the requirement of immutable data type, which shows a promise for next generation computation specially, where multi-core processors are used. C# has provided referentially transparent Data structure for IList<T> and IDictionary<T> as IReadOnlyCollection<T> and IReadOnlyDictionary<K, T> respectively. But no such data structure is available for tree type data. Immutable data structure for CollectionTree and DictionaryTree is developed here as ReadonlyCollectionTree<U, T> and ReadonlyDictionaryTree<U, K, T> respectively.
Using the code
Mutable Types
Two interfaces are used to represent Tree depending on the type of nodes used (IList<T> or IDictionary<K,T>).
For IList type Nodes ICollectionTree<T> interface is used:
public interface ICollectionTree<T>
{
IList<T> Leaf { get; set; }
ICollection<ICollectionTree<T>> Nodes { get; set; }
}
Similarly for IDictionary type Nodes IDictionaryTree<K, T> interface is used:
public interface IDictionaryTree<K, T>
{
IDictionary<K, T> Leaf { get; set; }
IDictionary<K, IDictionaryTree<K, T>> Nodes { get; set; }
}
ReadOnly Types
To transform above mutable data structure to respective ReadOnly data structure, two generic classes are used, with the help of ReadOnlyCollection and ReadOnlyDictionary.
For ICollectionTree<T> interface, ReadonlyCollectionTree<U, T> class is used:
public class ReadonlyCollectionTree<U, T> where U : ICollectionTree<T>
{
public IReadOnlyCollection<T> ReadonlyLeaf { get; set; }
public IReadOnlyCollection<ReadonlyCollectionTree<U, T>> ReadonlyNodes { get; set; }
public ReadonlyCollectionTree(ICollection<ICollectionTree<T>> Nodes, IList<T> Leaf)
{
List<ReadonlyCollectionTree<U, T>> ListOfReadonlyTree = new List<ReadonlyCollectionTree<U, T>>();
foreach (var s in Nodes)
{
ListOfReadonlyTree.Add(new ReadonlyCollectionTree<U, T>(s.Nodes, s.Leaf));
}
ReadonlyNodes = new ReadOnlyCollection<ReadonlyCollectionTree<U, T>>(ListOfReadonlyTree);
ReadonlyLeaf = new ReadOnlyCollection<T>(Leaf);
}
}
For IDictionaryTree<K, T> interface, ReadonlyCollectionTree<U, T> class is used:
public class ReadonlyDictionaryTree<U, K, T> where U : IDictionaryTree<K, T>
{
public IReadOnlyDictionary<K, T> ReadonlyLeaf { get; set; }
public IReadOnlyDictionary<K, ReadonlyDictionaryTree<U, K, T>> ReadonlyNodes { get; set; }
public ReadonlyDictionaryTree(IDictionary<K, IDictionaryTree<K, T>> Node, IDictionary<K, T> Leaf)
{
var ListOfReadonlyTree = new Dictionary<K, ReadonlyDictionaryTree<U, K, T>>();
Parallel.ForEach(Node.Keys, s =>
{
ListOfReadonlyTree.Add(s, new ReadonlyDictionaryTree<U, K, T>(Node[s].Nodes, Node[s].Leaf));
});
ReadonlyNodes = new ReadOnlyDictionary<K, ReadonlyDictionaryTree<U, K, T>>(ListOfReadonlyTree);
ReadonlyLeaf = new ReadOnlyDictionary<K, T>(Leaf);
}
}
<span style="font-size: 9pt;"> </span>
Usage of ReadOnly classes
Two small classes are used to show the usage of above ReadOnly Generic classes, one is to represent Key and other is for Value of Dictionary of Node.
public class MyObjectKey
{
public string Key { get; set; }
public MyObjectKey(string s)
{
Key = s;
}
public override string ToString()
{
return "Key:" + Key;
}
}
public class MyObjectValue
{
public string Value { get; set; }
public MyObjectValue(string s)
{
Value = s;
}
public override string ToString()
{
return "Value:" + Value;
}
}
ReadonlyDerivedDataCollectionTree is derived from ReadonlyCollectionTree:
public class ReadonlyDerivedDataCollectionTree : ReadonlyCollectionTree<DerivedDataCollectionTree, MyObjectValue>
{
public ReadonlyDerivedDataCollectionTree(ICollection<ICollectionTree<MyObjectValue>> s, IList<MyObjectValue> l)
: base(s, l)
{
}
}
Similarly ReadonlyDerivedDataDictionaryTree is derived from ReadonlyDictionaryTree:
public class ReadonlyDerivedDataDictionaryTree : ReadonlyDictionaryTree<DerivedDataDictionaryTree, MyObjectKey, MyObjectValue>
{
public ReadonlyDerivedDataDictionaryTree(
IDictionary<MyObjectKey, IDictionaryTree<MyObjectKey, MyObjectValue>> s,
IDictionary<MyObjectKey, MyObjectValue> l
)
: base(s, l)
{
}
}
Points of Interest
Unlike CollectionTree, here DictionaryTree is used with Parallel.ForEach as order preference is not require.
History
26 January 2015: Initial Article.
