Emulating ADTs in C# 9+

The most upvoted language request for C# is discriminated unions. As of 2023, the proposal is now 6 years old. There are many reasons for that -- the feature has many different design variants, it interacts heavily with with other language features, it can have performance implications, and, most significantly, it represents a new program design pattern in C#. All of these impacts mean the feature takes a lot of time and effort to get right. Most importantly, it means that the language design team has to be confident they've picked the right variant of the feature before shipping it.

All well and good, but it means that we need an alternative in the meantime. And I have one to offer.

My solution uses C# 9 records, an attribute called [Closed], and an analyzer -- all of which are available in my StaticCS NuGet package.

The basic idea is to declare an abstract base record to represent the union, then nest derived records underneath the base record. For example, consider the discriminated union representing a binary tree of ints. It would be commonly represented in an ML-like language as

datatype btree = Leaf
               | Node of (btree * int * btree)

With Closed records you would write this as

abstract record BTree
    public sealed record Leaf : BTree;
    public sealed record Node(BTree left, int Value, BTree Right) : BTree;

    private BTree() { }

The private constructor is to make sure that no other records can inherit from BTree. If they could, we couldn't have completeness checking when switching, as we could never be sure that we saw all the cases.

To create new ADTs in ML we would write something like

(* Create a new tree *)
fun newTree n = Node (Leaf, n, Leaf)

In C# it would be

BTree NewTree(int n) => new BTree.Node(new BTree.Leaf(), n, new BTree.Leaf());

You could also use a using static directive to bring the BTree members into scope:

using static BTree;
BTree NewTree(int n) => new Node(new Leaf(), n, new Leaf());

Lastly, you might want to deconstruct the binary tree to write functions. You would do this in ML like

(* Find 'n' in the tree *)
fun contains _ Leaf = false
  | contains n (Node (left, m, right)) = (n = m) orelse (contains n left) orelse (contains n right)

and in C#:

bool Contains(BTree tree, int n) => tree switch {
    BTree.Leaf => false,
    BTree.Node(var left, int m, var right) =>
        (m == n) || Contains(left, n) || Contains(right, n)

Note that we won't get a warning from the switch statement because the BTree is marked Closed.

This solution isn't quite as streamlined as I hope the eventual language feature will be, but I find it workable in practice.