But, from a practical point of view,
is a very comfortable experience.
I like to use F# for most of my functional programming. For what its worth, you can write functional code in C#, its just really really nasty and ugly to read. Additionally, I find GUI development resists a functional programming style.
Fortunately, business code seems to adapt really well to functional style :) That, and web development too -- think about, each HTTP request is stateless. Each time you "modify" state, you pass the server some state, and it returns back an entirely new page.
I would appreciate how to think about
writing programs when you are forced
to use immutable objects.
Immutable objects should be small
For the most part, I find immutable data structures easiest to work with when the objects have fewer than 3 or 4 intrinsic properties. For example, each node in a red-black tree has 4 properties: a color, a value, a left child, and right-child. A stack has two properties, a value and a pointer to the next stack node.
Consider your company's database, you might have tables with 20, 30, 50 properties. If you need to modify those objects throughout your application, then I'd definitely resist the urge to make those immutable.
C# / Java / C++ aren't good functional languages. Use Haskell, OCaml, or F# instead
In my own experience, immutable objects are 1000x easier to read and write in ML-like languages than C-like languages. I'm sorry, but once you have pattern matching and union types, you can't give them up :) Additionally, some data structures can take advantage of tail-call optimization, a feature you just don't get in some C-like languages.
But just for fun, here's an unbalanced binary tree in C#:
class Tree<T> where T : IComparable<T>
{
public static readonly ITree Empty = new Nil();
public interface ITree
{
ITree Insert(T value);
bool Exists(T value);
T Value { get; }
ITree Left { get; }
ITree Right { get; }
}
public sealed class Node : ITree
{
public Node(T value, ITree left, ITree right)
{
this.Value = value;
this.Left = left;
this.Right = right;
}
public ITree Insert(T value)
{
switch(value.CompareTo(this.Value))
{
case 0 : return this;
case -1: return new Node(this.Value, this.Left.Insert(value), this.Right);
case 1: return new Node(this.Value, this.Left, this.Right.Insert(value));
default: throw new Exception("Invalid comparison");
}
}
public bool Exists(T value)
{
switch (value.CompareTo(this.Value))
{
case 0: return true;
case -1: return this.Left.Exists(value);
case 1: return this.Right.Exists(value);
default: throw new Exception("Invalid comparison");
}
}
public T Value { get; private set; }
public ITree Left { get; private set; }
public ITree Right { get; private set; }
}
public sealed class Nil : ITree
{
public ITree Insert(T value)
{
return new Node(value, new Nil(), new Nil());
}
public bool Exists(T value) { return false; }
public T Value { get { throw new Exception("Empty tree"); } }
public ITree Left { get { throw new Exception("Empty tree"); } }
public ITree Right { get { throw new Exception("Empty tree"); } }
}
}
The Nil class represents an empty tree. I prefer this representation over the null representation because null checks are the devil incarnate :)
Whenever we add a node, we create a brand new tree with the node inserted. This is more efficient than it sounds, because we don't need to copy all the nodes in the tree; we only need to copy nodes "on the way down" and reuse any nodes which haven't changed.
Let's say we have a tree like this:
e
/ \
c s
/ \ / \
a b f y
Alright, now we want to insert w into the list. We're going to start at the root e, move to s, then to y, then replace y's left child with a w. We need to create copy of the nodes on the way down:
e e[1]
/ \ / \
c s ---> c s[1]
/ \ / \ / \ /\
a b f y a b f y[1]
/
w
Alright, now we insert a g:
e e[1] e[2]
/ \ / \ / \
c s ---> c s[1] --> c s[2]
/ \ / \ / \ /\ / \ / \
a b f y a b f y[1] a b f[1] y[1]
/ \ /
w g w
We reuse all of the old nodes in the tree, so there's no reason to rebuild the entire tree from scratch. This tree has the same computational complexity as its mutable counterpart.
Its also pretty easy to write immutable versions of red-black trees, AVL trees, tree-based heaps, and many other data structures.