An immutable priority collection by Mark Seemann

With examples in C# and F#.

This article is part of a series about encapsulation and immutability. After two attempts at an object-oriented, mutable implementation, I now turn toward immutability. As already suggested in the introductory article, immutability makes it easier to maintain invariants.

In the introductory article, I described the example problem in more details, but in short, the exercise is to develop a class that holds a collection of prioritized items, with the invariant that the priorities must always sum to 100. It should be impossible to leave the object in a state where that's not true. It's quite an illuminating exercise, so if you have the time, you should try it for yourself before reading on.

Initialization #

Once again, I begin by figuring out how to initialize the object, and how to model it. Since it's a kind of collection, and since I now plan to keep it immutable, it seems natural to implement IReadOnlyCollection<T>.

In this, the third attempt, I'll reintroduce Prioritized<T>, with one important difference. It's now an immutable record:

public sealed record Prioritized<T>(T Item, byte Priority);

If you're not on a version of C# that supports records (which is also trivially true if you're not using C# at all), you can always define an immutable class by hand. It just requires more boilerplate code.

Prioritized<T> is going to be the T in the IReadOnlyCollection<T> implementation:

public sealed class PriorityCollection<T> : IReadOnlyCollection<Prioritized<T>>

Since an invariant should always hold, it should also hold at initialization, so the PriorityCollection<T> constructor must check that all is as it should be:

private readonly Prioritized<T>[] priorities;
 
public PriorityCollection(params Prioritized<T>[] priorities)
{
    if (priorities.Sum(p => p.Priority) != 100)
        throw new ArgumentException(
            "The sum of all priorities must be 100.",
            nameof(priorities));
    this.priorities = priorities;
}

The rest of the class is just the IReadOnlyCollection<T> implementation, which just delegates to the priorities field.

That's it, really. That's the API. We're done.

Projection #

But, you may ask, how does one edit such a collection?

(Comic originally by John Muellerleile.)

Humour aside, you don't edit an immutable object, but rather make a new object from a previous one. Most modern languages now come with built-in collection-projection APIs; in .NET, it's called LINQ. Here's an example. You begin with a collection with two items:

var pc = new PriorityCollection<string>(
    new Prioritized<string>("foo", 60),
    new Prioritized<string>("bar", 40));

You'd now like to add a third item with priority 20:

var newPriority = new Prioritized<string>("baz", 20);

How should you make room for this new item? One option is to evenly reduce each of the existing priorities:

var reduction = newPriority.Priority / pc.Count;
IEnumerable<Prioritized<string>> reduced = pc
    .Select(p => p with { Priority = (byte)(p.Priority - reduction) });

Notice that while the sum of priorities in reduced no longer sum to 100, it's okay, because reduced isn't a PriorityCollection object. It's just an IEnumerable<Prioritized<string>>.

You can now Append the newPriority to the reduced sequence and repackage that in a PriorityCollection:

var adjusted = new PriorityCollection<string>(reduced.Append(newPriority).ToArray());

Like the original pc object, the adjusted object is valid upon construction, and since its immutable, it'll remain valid.

Edit #

If you think this process of unwrapping and rewrapping seems cumbersome, we can make it a bit more palatable by defining a wrapping Edit function, similar to the one in the previous article:

public PriorityCollection<T> Edit(
    Func<IReadOnlyCollection<Prioritized<T>>, IEnumerable<Prioritized<T>>> edit)
{
    return new PriorityCollection<T>(edit(this).ToArray());
}

You can now write code equivalent to the above example like this:

var adjusted = pc.Edit(col =>
{
    var reduced = col.Select(p => p with { Priority = (byte)(p.Priority - reduction) });
    return reduced.Append(newPriority);
});

I'm not sure it's much of an improvement, though.

Using the right tool for the job #

While C# over the years has gained some functional-programming features, it's originally an object-oriented language, and working with immutable values may still seem a bit cumbersome. If so, consider using a language natively designed for this style of programming. On .NET, F# is the obvious choice.

First, you define the required types:

type Prioritized<'a> = { Item: 'a; Priority: byte }
 
type PriorityList = private PriorityList of Prioritized<string> list

Notice that PriorityList has a private constructor, so that client code can't just create any value. The type should protect its invariants, since encapsulation is also relevant in functional programming. Since client code can't directly create PriorityList objects, you instead supply a function for that purpose:

module PriorityList =
    let tryCreate priorities =
        if priorities |> List.sumBy (_.Priority) = 100uy
        then Some (PriorityList priorities)
        else None

That's really it, although you also need a way to work with the data. We supply two alternatives that correspond to the above C#:

let edit f (PriorityList priorities) = f priorities |> tryCreate
 
let toList (PriorityList priorities) = priorities

These functions are also defined on the PriorityList module.

Here's the same adjustment example as shown above in C#:

let pl  =
    [ { Item = "foo"; Priority = 60uy }; { Item = "bar"; Priority = 40uy } ]
    |> PriorityList.tryCreate
let newPriority = { Item = "baz"; Priority = 20uy }
let adjusted =
    pl
    |> Option.bind (PriorityList.edit (fun l ->
        l
        |> List.map (fun p ->
            { p with Priority = p.Priority - (newPriority.Priority / byte l.Length) })
        |> List.append [ newPriority ]))

The entire F# definition is 15 lines of code, including namespace declaration and blank lines.

Conclusion #

With an immutable data structure, you only need to check the invariants upon creation. Invariants therefore become preconditions. Once a value is created in a valid state, it stays valid because it never changes state.

If you're having trouble maintaining invariants in an object-oriented design, try making the object immutable. It's likely to make it easier to attain good encapsulation.

---

Comments

• ← Previous
• Archive
• Next →