This is the story of how I was no-hired by Microsoft; surprisingly, it is germane to our discussion of unusual list structures. Continue reading →

At long last, let’s get to that double-ended queue. Sorry for leaving you in suspense!

Based on the comments, the implementation of a single-ended queue as two stacks was somewhat mind-blowing for a number of readers. People, you ain’t seen nothing yet.

Good Monday morning all. I have received a lot of good comments on this series so far that I thought I would speak to a bit.

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.

Lots of good comments on my previous post. To briefly follow up:

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:

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.

An immutable queue is a bit trickier than an immutable stack, but we’re tough, we can handle it.

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.