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 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….


Immutability in C# Part One: Kinds of Immutability

I said in an earlier post that I believe that immutable objects are the way of the future in C#. I stand by that statement while at the same time noting that it is at this point sufficiently vague as to be practically meaningless! “Immutable” means different things to different people; different kinds of immutability…


Covariance and Contravariance in C#, Part Ten: Dealing With Ambiguity

OK, I wasn’t quite done. One more variance post! Smart people: suppose we made IEnumerable<T> covariant in T. What should this program fragment do? class C : IEnumerable<Giraffe>, IEnumerable<Turtle> {    IEnumerator<Giraffe> IEnumerable<Giraffe>.GetEnumerator() {         yield return new Giraffe();    }    IEnumerator<Turtle> IEnumerable<Turtle>.GetEnumerator() {         yield return new Turtle();    }// [etc.]} class Program {    static void Main()  {       …


A Couple Links

Just two unrelated links today. First, Raymond’s post today reminded me of one of my favourite lines from the L.A. Story screenplay: “Look, rather than do an interview with me, which would be fascinating, by the way, because of my interesting word usements I structure, what if I showed you around town a little?” Pre-envisioning? What…