Immutability in C# Part Eight: Even More On Binary Trees

Last year we declared a relatively simple interface to represent an immutable binary tree. We noticed that it was different from every other interface that we’ve declared so far, in that it really said nothing at all about the immutability of the tree. One normally thinks of immutable data types not in terms of their shape, but rather in terms of what operations may be performed on the data type. Operations are usually either to query the object somehow, or to “modify” it by producing new modified versions of the old immutable object.

Continue reading

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!

Commentary from 2022: When I wrote this post 14 years ago Cyrus was about to leave Microsoft and go work for… Google? maybe? I don’t recall. Anyway, after some time we were very fortunate to get him back at Microsoft and last I checked he was once again on the C# compiler team.

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 C# today. If you cast a Giraffe[] to Mammal[] then you can try to put a Tiger into the Mammal[] and it will fail at run time. It seems like the same should be true of stacks — if you cast an IStack<Giraffe> to IStack<Mammal> then you can push a Tiger onto the stack of Giraffes, which should fail, right?

Maybe. Maybe not.

Continue reading

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. How can it be immutable?

Continue reading

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 have different pros and cons. I’d like to spend some time over the next few weeks talking about possible directions that C# could go to improve the developer experience when writing programs that use immutable objects, as well as giving some practical examples of the sort of immutable object programming you can do today.

Continue reading