Algebraic Data Types: Product and Sum Types, Discriminated Unions and Making Illegal States Unrepresentable

Version note: The code in this post was built and run with C# 14 and .NET 10 (SDK 10.0.402); the TypeScript examples with TypeScript 7.0.2 and Node.js 26. The code in the "With C# 15: union Types" section was built and run in a separate project with C# 15 and the .NET 11 SDK (11.0.100).

Guess First: When a Cancelled Order Gets Shipped

In Bookstore, the online bookstore used as the shared example across this site's series, an order's status has been kept in three flags and three nullable properties for years:

public class FlaggedOrder
{
    public bool IsPaid { get; set; }
    public bool IsShipped { get; set; }
    public bool IsCancelled { get; set; }
    public string? PaymentId { get; set; }
    public string? TrackingNo { get; set; }
    public string? CancelReason { get; set; }

    public string Describe()
    {
        if (IsCancelled)
            return $"cancelled: {CancelReason}";
        if (IsShipped)
            return $"shipped with {TrackingNo}";
        if (IsPaid)
            return $"paid with {PaymentId}";
        return "pending";
    }
}

One Friday afternoon customer support cancels a paid order at the customer's request; in the same minute the warehouse ships the same order. There's also an order created by hand in a test with only the IsShipped flag set. What gets printed?

FlaggedOrder order = new() { IsPaid = true, PaymentId = "PAY-1001" };

// Support cancels the order; the warehouse ships it in the same minute
order.IsCancelled = true;
order.CancelReason = "customer request";
order.IsShipped = true;
order.TrackingNo = "TRK-778";

Console.WriteLine(order.Describe());
Console.WriteLine($"paid: {order.IsPaid}, shipped: {order.IsShipped}, cancelled: {order.IsCancelled}");

FlaggedOrder ghost = new() { IsShipped = true };
Console.WriteLine($"ghost: {ghost.Describe()}");

Answer: Impossible States the Compiler Accepts

$ dotnet run --project src/Bookstore.Fp.Demo -- 05-flags
cancelled: customer request
paid: True, shipped: True, cancelled: True
ghost: shipped with 

The order is both cancelled and shipped. Describe says "cancelled" because of the order of its ifs; the customer is waiting for a refund while the book is on its way. The second order was shipped without being paid and has no tracking number; Describe prints an empty tracking number. Both states are impossible from a business point of view, but perfectly valid to the compiler: three bools produce eight combinations, and the type system doesn't know which of them make sense.

Three of the eight combinations are impossible, and two spell the same state (a cancelled order) in two different ways. Add the three nullable strings and the table grows: IsPaid set but PaymentId null, IsCancelled unset but CancelReason filled in... What we've done against these impossible states so far is write validation at the start of every method and hope to remember all of it. Functional programming's answer is different: make the impossible state impossible to build. In the phrase popularised by Yaron Minsky's talks on OCaml, "make illegal states unrepresentable". The tool for that is the algebraic data type, a type built by combining other types with "and" or offering them as alternatives with "or".

Product Types and Sum Types: Why "Algebraic"?

There are two basic ways of combining types. A product type brings several values together with "and": an Order has an order number and a customer and a total and a status. record, class, struct and tuples in C#, and object types in TypeScript, are product types. The name comes from the number of values it can take: a record with three bool properties can take 2 × 2 × 2 = 8 different values. The counts multiply.

A sum type, on the other hand, combines alternatives with "or": an order is either pending or paid or shipped or cancelled; only one of them at a time. Each alternative can carry its own data: a paid order has a payment number, a shipped one a tracking number, a cancelled one a reason. The counts add up: four alternatives, four states (together with the number of values of each alternative's own data). In F#, Haskell, OCaml, Rust and Swift, sum types are a core part of the language; in TypeScript they exist as discriminated unions. C# had no direct counterpart until C# 15; we imitate them with the tools we have.

The name "algebraic" comes from this multiplication and addition. Its practical meaning is simple: make the number of combinations in the model equal to the number of states in the business rule. The flagged class tries to represent the 4 states of the business rule with 8 combinations and 3 nullable properties; the sum type offers exactly 4 states.

Sum Types in C# 14: abstract record and sealed Cases

The closest thing to a sum type in C# 14 is an abstract record with sealed child records defined inside it:

[JsonPolymorphic(TypeDiscriminatorPropertyName = "kind")]
[JsonDerivedType(typeof(Pending), "pending")]
[JsonDerivedType(typeof(Paid), "paid")]
[JsonDerivedType(typeof(Shipped), "shipped")]
[JsonDerivedType(typeof(Cancelled), "cancelled")]
public abstract record OrderStatus
{
    // Only the nested cases below can derive from OrderStatus
    private OrderStatus() { }

    public sealed record Pending : OrderStatus;
    public sealed record Paid(string PaymentId) : OrderStatus;
    public sealed record Shipped(string PaymentId, string TrackingNo) : OrderStatus;
    public sealed record Cancelled(string Reason) : OrderStatus;
}

Each case carries only its own data: Pending has no properties at all, and Shipped requires both the payment and the tracking number. "Shipped but no tracking number" can no longer be written; Shipped's constructor demands both strings. The private constructor is there to stop new cases from being derived from outside; the nested cases can derive because they can access the base type's private members. We'll come back to the JSON attributes in the Pitfalls section.

Order, on the other hand, is a product type; its status is a single property:

public sealed record Order(string OrderNo, string CustomerEmail, decimal Total, OrderStatus Status);

Code that reads the status handles each case separately with a switch expression. The syntax of property and type patterns is in the C# Advanced series post "Pattern Matching in C# in Depth: Property, Positional and Tuple Patterns":

public static string Describe(OrderStatus status) => status switch
{
    Pending => "pending",
    Paid paid => $"paid with {paid.PaymentId}",
    Shipped shipped => $"shipped with {shipped.TrackingNo}",
    Cancelled cancelled => $"cancelled: {cancelled.Reason}",
    _ => throw new UnreachableException($"Unknown status {status.GetType().Name}")
};

paid.PaymentId needs no null check: if you've entered the Paid case, the payment number is definitely there. The if (IsPaid && PaymentId != null) combinations of the flagged model disappear; the type becomes the check itself.

Writing Transitions with Types: Ship Only Takes Paid

The real gain of a sum type shows in the transitions between states. Let's write the transitions as pure functions that accept only a valid starting state:

public static class OrderWorkflow
{
    public static Paid Pay(Pending pending, string paymentId) => new(paymentId);

    public static Shipped Ship(Paid paid, string trackingNo) => new(paid.PaymentId, trackingNo);

    // A shipped order can't be cancelled: only these two overloads exist
    public static Cancelled Cancel(Pending pending, string reason) => new(reason);

    public static Cancelled Cancel(Paid paid, string reason) => new(reason);
}

Pending pending = new();
Paid paid = OrderWorkflow.Pay(pending, "PAY-1001");
Shipped shipped = OrderWorkflow.Ship(paid, "TRK-778");
Cancelled cancelled = OrderWorkflow.Cancel(paid, "customer request");

OrderStatus[] history = [pending, paid, shipped, cancelled];
foreach (OrderStatus status in history)
    Console.WriteLine(OrderWorkflow.Describe(status));

Order order = new("BS-2026-0042", "ada@example.com", 259.36m, shipped);
Console.WriteLine(order);

$ dotnet run --project src/Bookstore.Fp.Demo -- 05-workflow
pending
paid with PAY-1001
shipped with TRK-778
cancelled: customer request
Order { OrderNo = BS-2026-0042, CustomerEmail = ada@example.com, Total = 259.36, Status = Shipped { PaymentId = PAY-1001, TrackingNo = TRK-778 } }

Ship's parameter isn't OrderStatus but Paid. Code that tries to ship an unpaid order or cancel a shipped one doesn't compile:

Pending pending = new();
Shipped shipped = OrderWorkflow.Ship(pending, "TRK-778");
Cancelled late = OrderWorkflow.Cancel(shipped, "too late");

Program.cs(5,38): error CS1503: Argument 1: cannot convert from 'Bookstore.Ordering.Orders.OrderStatus.Pending' to 'Bookstore.Ordering.Orders.OrderStatus.Paid'
Program.cs(6,39): error CS1503: Argument 1: cannot convert from 'Bookstore.Ordering.Orders.OrderStatus.Shipped' to 'Bookstore.Ordering.Orders.OrderStatus.Pending'

With this model, the "cancelled but shipped" order from the guess isn't a runtime error but a compile error. The problem of two operations racing each other (support and the warehouse acting in the same minute) is of course not solved by a type; that's the job of concurrency control in the database. But which transition is valid is no longer scattered across ifs all over the code; it's in the function signatures.

Note the two overloads of Cancel. There's no "Pending or Paid" type in C# 14; you either write two overloads or take OrderStatus and check inside (leaving the check to run time). C# 15 closes this gap, as we'll see shortly.

Exhaustiveness: Why Does the Compiler Still Want _?

Look at the last arm in Describe, the line _ => throw new UnreachableException(...). Why is it needed when all four cases are handled? Let's delete the line:

static string Short(OrderStatus status) => status switch
{
    Pending => "P",
    Paid => "$",
    Shipped => "S",
    Cancelled => "X"
};

Program.cs(8,51): warning CS8509: The switch expression does not handle all possible values of its input type (it is not exhaustive). For example, the pattern '_' is not covered.

The compiler sees the four cases but can't be sure that OrderStatus has no other subtype. In C# 14 there's no way to declare a class hierarchy "closed". The private constructor trick doesn't fully close it either: records have a compiler-generated copy constructor, and in a record that isn't sealed that constructor must be public or protected. Trying to make it private is rejected:

c.cs(4,13): error CS8878: A copy constructor 'OrderStatus.OrderStatus(OrderStatus)' must be public or protected because the record is not sealed.

Through the protected copy constructor, a new case can be derived in another assembly, and this code compiles:

OrderStatus refunded = new Refunded("damaged copy");
Console.WriteLine(OrderWorkflow.Describe(refunded));

record Refunded(string Reason) : OrderStatus(new Pending());

Unhandled exception. System.Diagnostics.UnreachableException: Unknown status Refunded

So the compiler is right to ask for the _ arm. You have to put something in that arm; throwing UnreachableException instead of silently returning a default (_ => "unknown") keeps an unexpected case from slipping through unnoticed. The price is this: when you add a fifth case to OrderStatus, the compiler won't tell you about the missing arm in this switch, because _ catches everything. You see the error at run time, in tests or in production. The promise of a real sum type is exactly getting this warning at compile time.

Discriminated Unions and never in TypeScript

In TypeScript, sum types are part of the language. Each case carries a common literal property (here kind); the compiler narrows the type by looking at that property:

export type OrderStatus =
  | { readonly kind: "pending" }
  | { readonly kind: "paid"; readonly paymentId: string }
  | { readonly kind: "shipped"; readonly paymentId: string; readonly trackingNo: string }
  | { readonly kind: "cancelled"; readonly reason: string };

export function assertNever(value: never): never {
  throw new Error(`Unexpected value: ${JSON.stringify(value)}`);
}

export function describe(status: OrderStatus): string {
  switch (status.kind) {
    case "pending":
      return "pending";
    case "paid":
      return `paid with ${status.paymentId}`;
    case "shipped":
      return `shipped with ${status.trackingNo}`;
    case "cancelled":
      return `cancelled: ${status.reason}`;
    default:
      return assertNever(status);
  }
}

By the time the default arm is reached, every case has been ruled out, so the type of status is never. If a new case is added to the union but not to the switch, never is no longer correct and the compiler reports an error. The same type system also rejects a property that doesn't belong to a case:

type OrderStatusV2 =
  | { kind: "pending" }
  | { kind: "paid"; paymentId: string }
  | { kind: "refunded"; paymentId: string; amount: number };

function label(status: OrderStatusV2): string {
  switch (status.kind) {
    case "pending":
      return "pending";
    case "paid":
      return "paid";
    default:
      return assertNever(status);
  }
}

const impossible: OrderStatusV2 = { kind: "paid", paymentId: "PAY-1001", trackingNo: "TRK-778" };

$ npx tsc -p tsconfig.errors.json
errors/05-order-status-errors.ts(15,26): error TS2345: Argument of type '{ kind: "refunded"; paymentId: string; amount: number; }' is not assignable to parameter of type 'never'.
errors/05-order-status-errors.ts(19,74): error TS2353: Object literal may only specify known properties, and 'trackingNo' does not exist in type '{ kind: "paid"; paymentId: string; }'.

Unlike the _ arm in C# 14, TypeScript catches the new case at compile time. The details of narrowing are in the Narrowing chapter of the TypeScript Handbook; modelling errors with discriminated unions is in the TypeScript Intermediate series post "Error Handling in TypeScript: unknown in catch, Narrowing Errors and the Result Pattern".

With C# 15: union Types

This section is a version note: the series is based on C# 14 / .NET 10; the code below was compiled with C# 15 in a separate project (csharp15/, pinned to the .NET 11 SDK with its own global.json). C# 15, released on 10 November 2026, brings a real sum type with the union keyword. According to the "What's new in C# 15" page on Microsoft Learn, the feature is available with the default language version in projects targeting net11.0, with no preview setting needed. The cases are ordinary types; the union combines them into a closed set:

public sealed record Pending;
public sealed record Paid(string PaymentId);
public sealed record Shipped(string PaymentId, string TrackingNo);
public sealed record Cancelled(string Reason);

public union OrderStatus(Pending, Paid, Shipped, Cancelled);

// Only orders that haven't shipped can be cancelled
public union Cancellable(Pending, Paid);

public static class OrderWorkflow
{
    public static Cancelled Cancel(Cancellable status, string reason) => new(reason);

    public static string Describe(OrderStatus status) => status switch
    {
        Pending => "pending",
        Paid paid => $"paid with {paid.PaymentId}",
        Shipped shipped => $"shipped with {shipped.TrackingNo}",
        Cancelled cancelled => $"cancelled: {cancelled.Reason}"
    };
}

Paid paid = new("PAY-1001");
OrderStatus[] history = [new Pending(), paid, new Shipped("PAY-1001", "TRK-778"), OrderWorkflow.Cancel(paid, "customer request")];

foreach (OrderStatus status in history)
    Console.WriteLine(OrderWorkflow.Describe(status));

$ cd csharp15
$ dotnet run --project Bookstore.Fp.CSharp15
pending
paid with PAY-1001
shipped with TRK-778
cancelled: customer request

There are three differences. Describe has no _ arm and the compiler doesn't warn. There's an implicit conversion from each case type to the union; paid can be passed directly both into the OrderStatus array and to the Cancellable parameter. And the "Pending or Paid" that we solved with two overloads in C# 14 is now a type. Delete an arm and try to cancel a shipped order:

public static class Broken
{
    public static string Short(OrderStatus status) => status switch
    {
        Pending => "P",
        Paid => "$",
        Shipped => "S"
    };

    public static Cancelled TooLate() => OrderWorkflow.Cancel(new Shipped("PAY-1001", "TRK-778"), "too late");
}

OrderStatus.cs(28,62): warning CS8509: The switch expression does not handle all possible values of its input type (it is not exhaustive). For example, the pattern 'Bookstore.Fp.CSharp15.Cancelled' is not covered.
OrderStatus.cs(35,63): error CS1503: Argument 1: cannot convert from 'Bookstore.Fp.CSharp15.Shipped' to 'Bookstore.Fp.CSharp15.Cancellable'

In C# 14 the warning said "_ is not covered"; this time the compiler names the missing case. One detail the documentation points out: the union the compiler generates is a struct, and its default value is empty inside (Value is null); wherever a default union can reach a switch, you need a null arm. C# 15 also brings the closed modifier, which solves the same problem for class hierarchies. Choosing between a union and a closed hierarchy, and the effects on serialization and the database, are the topic of the eighth post in the series.

Common Pitfalls

Forgetting serialization. When you return a sum type from an API or write it to a queue, the reading side needs to know which case it received. System.Text.Json solves this with the [JsonPolymorphic] and [JsonDerivedType] attributes; it writes a discriminator property called kind and looks at it when reading:

JsonSerializerOptions options = new(JsonSerializerDefaults.Web);
OrderStatus[] statuses = [new Pending(), new Paid("PAY-1001"), new Shipped("PAY-1001", "TRK-778"), new Cancelled("customer request")];

string json = JsonSerializer.Serialize(statuses, options);
Console.WriteLine(json);

OrderStatus[] back = JsonSerializer.Deserialize<OrderStatus[]>(json, options)!;
Console.WriteLine($"round trip: {back.SequenceEqual(statuses)}, last: {back[^1]}");

$ dotnet run --project src/Bookstore.Fp.Demo -- 05-json
[{"kind":"pending"},{"kind":"paid","paymentId":"PAY-1001"},{"kind":"shipped","paymentId":"PAY-1001","trackingNo":"TRK-778"},{"kind":"cancelled","reason":"customer request"}]
round trip: True, last: Cancelled { Reason = customer request }

Without the attributes, OrderStatus can't be deserialized because it's abstract; add a new case and forget its [JsonDerivedType], and you get an exception during serialization. Choosing the same discriminator name as the TypeScript side (here kind) lets both sides speak the same JSON; the describe function in TypeScript reads the JSON produced by C# as it is:

const statuses = JSON.parse(json) as OrderStatus[];
for (const status of statuses) {
  console.log(describe(status));
}

const shipped = statuses[2];
if (shipped.kind === "shipped") {
  console.log("narrowed:", shipped.trackingNo);
}

$ node src/05-order-status.ts
pending
paid with PAY-1001
shipped with TRK-778
cancelled: customer request
narrowed: TRK-778

The as OrderStatus[] here isn't validation but an assertion: if the server sends an unexpected kind, TypeScript won't catch it. Validating JSON coming from the outside world against a schema (with something like Zod) is a separate step.

Forgetting about storage in the database. Entity Framework Core can store a record hierarchy with TPH, keeping all subtypes in one table with a discriminator column, but then the properties of all cases sit side by side in the same table as nullable columns; in other words, the database counterpart of the flagged model comes back. The other option, TPT, keeps each subtype in its own table: fewer nullable columns but more joins. The options are in the EF Core series post "Inheritance Mapping in EF Core: TPH, TPT and When to Choose Which". A common practical solution is to keep one column for the status in the entity and the case-specific data in separate columns, building the sum type in the domain layer.

Returning a silent default in the _ arm. _ => "unknown" quiets the compiler but keeps producing wrong screen text when a new case is added. In C# 14, throw UnreachableException and test the list of cases; when you move to C# 15, remove the _ arm and get the warning back.

Leaking the flags back in. After moving to a sum type, adding properties like bool IsShipped => this is Shipped; "for convenience" looks harmless, but after a while the code starts talking in flags again and loses the narrowing that pattern matching gives (access to shipped.TrackingNo without a null check). If you need the query, writing status is Shipped is already short enough.

A Small Experiment

★☆☆ Add a Delivered(string PaymentId, string TrackingNo, DateTimeOffset DeliveredAt) case to OrderStatus. In the C# 14 project, which switches tell you about it, and which silently fall into the _ arm? What happens when you add the same case in TypeScript?

★★☆ Write a Deliver(Shipped shipped, DateTimeOffset at) transition in OrderWorkflow and read the compiler error for a line that tries to deliver an order that hasn't been shipped.

★★☆ Write a ToStatus(FlaggedOrder order) function that converts a FlaggedOrder to an OrderStatus. What should it return for the two impossible orders in the guess? This question is exactly the decision you'll face when moving legacy data to the new model.

★★★ If you have the .NET 11 SDK installed, define a Shippable union similar to Cancellable in the csharp15/ project and write Ship with it. Then rewrite OrderStatus as a closed record hierarchy and compare the compiler warnings of the two approaches.

In the next post we handle "no value" with types: Option. We'll see where the compiler-level protection of nullable reference types is enough, where Option<T> gives more, computations chained with Map and Bind, and why LINQ query syntax can work on Option too.