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