Easy Discriminated Unions in C#

2023/06/11

Categories: programming Tags: csharp functional

The lack of discriminated unions (DUs) in C# really hurts when doing domain modeling. The standard way to hack around this is using abstract classes, but class definitions require tons of boiler plate and put you on the object oriented side of the Expression Problem (with classes, it’s easy to add nouns but hard to add verbs; with DUs, it’s easy to add verbs but hard to add nouns).

In my opinion a DU solution should have the following:

  1. A Match function that enforces at compile time that every case in the union is covered.
  2. Immutability by default.
  3. Concise type definitions (one line per case).

With contemporary C#’s switch expressions and record types, you can hack together discriminated unions (DUs) that are decent to use. You can get rough parity with what you’d have in a language like F#, although it requires more ceremony in C#. I’ve used the following technique for a couple years:

using System;

public abstract record DiscriminatedUnion<T, A, B, C> 
	where A: T where B: T where C: T
{
	public X Match<X>(Func<A, X> fa, Func<B, X> fb, Func<C, X> fc) =>
		this switch
		{
			A a => fa(a),
			B b => fb(b),
			C c => fc(c),
			_ => throw new Exception("Impossible")
		};
}
	
public abstract record Tree<T>
	: DiscriminatedUnion<Tree<T>, Tree<T>.Branch, Tree<T>.Leaf, Tree<T>.Empty>
{
	public record Branch(Tree<T> Left, Tree<T> Right): Tree<T>;
	public record Leaf(T Value): Tree<T>;
	public record Empty: Tree<T>;
}
					
public class Program
{
	static Tree<int> tree = new Tree<int>.Branch(
		new Tree<int>.Branch(
			new Tree<int>.Leaf(1),
			new Tree<int>.Leaf(2)
		),
		new Tree<int>.Leaf(3)
	);
	
	static int SumTree(Tree<int> t) =>
		t.Match(
			branch => SumTree(branch.Left) + SumTree(branch.Right),
			leaf => leaf.Value,
			empty => 0
		);
	
	public static void Main() =>
		Console.WriteLine(SumTree(tree)); // => 6
}

You’d extend this by making multiple DiscriminatedUnion base types, one for each number of cases between 2 and 16 (or something).

The DiscriminatedUnion base record gives us a free Match function on every custom DU we define and the type parameters let us get type safety on Match. If you try to write a Match that skips a case, you’ll get a compile time error.

DUs are defined as nested records, which gives us immutability by default and concise definitions. Nesting the cases inside the base type makes it more readable in my opinion.

If you’re using Newtonsoft, you can write a custom JSON serializer that represents the tree above as follows:

{
    "@type": "Branch",
    "left": {
        "@type": "Branch",
        "left": {
            "@type": "Leaf",
            "value": 1
        },
        "right": {
            "@type": "Leaf",
            "value": 2
        }
    },
    "right": {
        "@type": "Leaf",
        "value": 3
    }
}

It’s moderately annoying to write this, but not too bad, and it means you can use DUs in your apis, which gives you a lot of power.

Overall, I’ve gotten a lot of mileage out of this approach and would recommend it.