Niche Software

Immutable types provide a way to build applications out of a solid foundation of reusable building blocks that are easy to understand and reason about. In some cases, immutable types can also improve memory use (by aggressive sharing) and increase performance (by eliminating time consuming copying and locks).

The design of immutable types means that their externally visible state doesn’t change over their lifetime, making them implicitly safe to share - no need to take a private copy of information to ensure it isn’t changed behind your back. (In some implementations, the internal state of an immutable object might change over time - perhaps caching the result of a time consuming calculation, for example.)

Stacks

Saturday, November 19 2016 immutable-types csharp

One of the stumbling blocks that gets in the way of people adopting immutable types is a belief that only trivial data structures can be created immutable; that mutability is a prerequisite for doing any real work. It turns out that this isn’t true - in this series of posts, I’ll explore “doing real work” with immutable data structures.

Stack Diagrams

Saturday, November 26 2016 immutable-types

One reader suggested that the immutable stacks from my previous post would be easier to understand with some accompanying diagrams to illustrate what is going on. Considering the future posts I have in mind for this series, starting with some clear diagrams is a good idea.

Enumerating Stacks

Saturday, December 03 2016 immutable-types csharp

The immutable stack implementation we wrote in Immutable Stacks doesn’t provide consumers with an easy way to iterate through everything on the stack. We can (and should) remedy this by implementing IEnumerable<T>.

Stack Equality

Friday, December 09 2016 immutable-types csharp

As previously discussed, it is important to implement an appropriate definition of Equality for most .NET classes. Let’s extend our immutable stack implementation appropriately.

Stacks Miscellany

Thursday, December 22 2016 immutable-types csharp

Before we move on to other kinds of immutable data structures, some miscellany about how we might improve on the ImmutableStack<T> we already have - or perhaps just do things differently. All of these observations were submitted by blog readers - thanks everyone for the feedback.

Queues

Friday, December 30 2016 immutable-types csharp

Moving on from our discussion of immutable stacks, let us look at how to effectively implement an ImmutableQueue<T>. What can the exercise teach us?

Simple Queues

Saturday, January 07 2017 immutable-types csharp

Thinking about the functionality we need from a simple immutable queue, we need to easily add a new item onto the end of the queue, and to easily remove an existing item from the front of the queue.

Reversing Stacks

Saturday, January 14 2017 immutable-types csharp

It turns out that I omitted the implementation of .Reverse() from my recent post Immutable Stacks Miscellany. Given that a friend has identified an alternative way to implement this, we’ll take a minor detour.

Enumeration of Queues

Saturday, January 21 2017 immutable-types csharp

We previously enabled enumeration of our immutable stacks - we should do the same for our immutable queues. Unfortunately, it’s a bit more complicated this time around. (For those looking to the solution to the puzzle posed at the end of my earlier post, you’ll need to wait until next time - but read to the end of this post for a clue.)

The Problem with the Simple Queue

Saturday, January 28 2017 immutable-types csharp

In my posts Simple Immutable Queues and Enumeration of Immutable Queues I’ve alluded to a nasty flaw that’s waiting to bite. What is that flaw, and why do we need to worry?

Complex Queues

Saturday, February 04 2017 immutable-types csharp

As discussed last time, the solution to our performance problem is to ensure our _inbound stack doesn’t get too large before we reverse it. This means we need to reverse it early; we can’t leave reversal until it’s needed to replace _outbound.

Queue Concatenation

Saturday, February 11 2017 immutable-types csharp

If you have a whole sequence of items you want to add to an existing IImmutableQueue<T>, it’s pretty simple to write a loop to add them all. We can make this even easier by writing a simple extension method that handles the looping on our behalf.

Factory Methods

Saturday, February 18 2017 immutable-types csharp

Our stacks and queues don’t exist in isolation - they have to interoperate with standard framework classes and other domain constructs to be useful. For example, it is extremely useful to have some factory methods to make it easier to construct stacks and queues from existing lists and sequences.

An Obscure FxCop feature 16 Feb 2010

Immutability Matters