Immutability in C# Part Seven: More on Binary Trees

Lots of good comments on my previous post. To briefly follow up: One of the downsides of immutable tree implementations is that usually the tree must be built from the leaves up, which is not always convenient. We’ll look at implementations which hide this fact from the user in future posts. One smartypants pointed out…


Immutability in C# Part Six: A Simple Binary Tree

OK, we’ve gotten pretty good at this by now. A straightforward implementation of an immutable generic binary tree requires little comment on the basics. A binary tree is either empty, or a value, left tree and right tree: public interface IBinaryTree<V>{    bool IsEmpty { get; }    V Value { get; }    IBinaryTree<V> Left { get;…


He’s Just Sayin’…

We interrupt our discussion of immutable data types to bring you this late-breaking news: my longtime coworker and developer lead Ed Maurer has started blogging about the C# compiler and related technologies. Check it out!


Immutability in C# Part Five: LOLZ!

My sadly soon-to-be-erstwhile coworker Cyrus made me a lolgeek shirt to go with this series of blog articles: Cyrus, needless to say, is a big goof. Thanks, dude!


Immutability in C# Part Four: An Immutable Queue

An immutable queue is a bit trickier than an immutable stack, but we’re tough, we can handle it. First off, the interface is straightforward; enqueuing or dequeuing results in a new queue:     public interface IQueue<T> : IEnumerable<T>    {        bool IsEmpty { get; }        T Peek();        IQueue<T> Enqueue(T value);        IQueue<T> Dequeue();    } But how ever…


Immutability in C# Part Three: A Covariant Immutable Stack

Now suppose we had a hypothetical future version of C# in which interface covariance worked, and we wanted a covariant immutable stack. That is, we want to be able to implicitly convert an IStack<Giraffe> to IStack<Mammal>. As we’ve already discussed, this doesn’t make much sense in an array, even though doing so is legal in…


Immutability in C# Part Two: A Simple Immutable Stack

Let’s start with something simple: an immutable stack. Now, immediately I hear the objection: a stack is by its very nature something that changes. A stack is an abstract data type with the interface void Push(T t);T Pop();bool IsEmpty { get; } You push stuff onto it, you pop stuff off of it, it changes….