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

19 Nov 2016

immutable-types

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

26 Nov 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

3 Dec 2016

immutable-types

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

9 Dec 2016

immutable-types

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

22 Dec 2016

immutable-types

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

30 Dec 2016

immutable-types

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

7 Jan 2017

immutable-types

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

14 Jan 2017

immutable-types

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

21 Jan 2017

immutable-types

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

28 Jan 2017

immutable-types

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

4 Feb 2017

immutable-types

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

11 Feb 2017

immutable-types

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

18 Feb 2017

immutable-types

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.

Testing Immutable Types

25 Feb 2017

immutable-types

As alluded to previously, having a good suite of unit tests is critical for ensuring these immutable instances do what they should - after all, there’s no point in having a queue or stack that doesn’t behave.

Type Miscellany

5 Mar 2017

immutable-types

As we near the end of this series on immutable types (for now, anyway), here’s a grab bag of things that didn’t seem to fit elsewhere.

Why Immutable Types?

11 Mar 2017

immutable-types

This series on immutable types has turned into something of an epic - when I began, I never expected it to become a series of this length. For now, the final question I want to address is a simple one: Why are immutable types important?

Related posts

An Obscure FxCop feature 16 Feb 2010