Composite — Recursive Discriminated Unions
This chapter compares representing a tree with a class hierarchy against representing it with a recursive union type.
The problem this pattern set out to solve
GoF catalogs Composite as a pattern that composes several similar objects so they can be treated as a single object1.
Left alone, code that handles a tree fills up with branches asking "is this a leaf or a branch?" Composite gives leaves and branches the same shape, which erases those branches from the code that handles them. Once files and directories are both an FsNode, computing the total size takes one recursive function.
Writing it straightforwardly with classes
You create a shared parent for leaves and branches and implement the same operation on both.
abstract class FsNode {
constructor(readonly name: string) {}
abstract totalSize(): number;
}
class FileLeaf extends FsNode {
constructor(
name: string,
private readonly bytes: number,
) {
super(name);
}
totalSize(): number {
return this.bytes;
}
}
class DirectoryNode extends FsNode {
private readonly children: FsNode[] = [];
add(child: FsNode): this {
this.children.push(child);
return this;
}
totalSize(): number {
return this.children.reduce((sum, child) => sum + child.totalSize(), 0);
}
}
const tree = new DirectoryNode('docs')
.add(new FileLeaf('index.md', 1200))
.add(new DirectoryNode('guide').add(new FileLeaf('intro.md', 800)));
const size = tree.totalSize();
The caller just writes tree.totalSize(), and it reads the same whether the contents are a single file or a nested hierarchy. This part is exactly what GoF was after.
Replacing it with language features
Type aliases in TypeScript can refer to themselves. Distinguish leaves from branches with a discriminating property and you can write the tree itself as a type.
type FsNode =
| {kind: 'file'; name: string; bytes: number}
| {kind: 'directory'; name: string; children: FsNode[]};
function totalSize(node: FsNode): number {
switch (node.kind) {
case 'file':
return node.bytes;
case 'directory':
return node.children.reduce((sum, child) => sum + totalSize(child), 0);
default: {
// If you add a kind and forget to fix this, this line becomes a type error
const exhaustive: never = node;
return exhaustive;
}
}
}
const tree: FsNode = {
kind: 'directory',
name: 'docs',
children: [
{kind: 'file', name: 'index.md', bytes: 1200},
{
kind: 'directory',
name: 'guide',
children: [{kind: 'file', name: 'intro.md', bytes: 800}],
},
],
};
const size = totalSize(tree);
node.children is readable inside case 'directory' because narrowing on kind is in effect. The never in default is an exhaustiveness check, the form the Handbook presents2.
The difference between the two versions is not that the branching disappeared. In the class version the branching exists in the form of method selection; in the union version it exists visibly as a switch. The total amount of branching is unchanged.
What changed is that data and operations came apart.
FsNodeis a plain object, so the result ofJSON.parsecan be dropped straight into it. The class version needs separate code to rebuild instances from the loaded data. That said, the return value ofJSON.parseisany, so dropping it in assumes the shape matches. Data arriving from outside needs its own runtime validation.- When you add an operation, the union version takes one new function and never touches the types. The class version means adding an abstract method to
FsNodeand an implementation to every derived class. - When you add a kind, on the other hand, the positions swap. In the union version every existing function turns into a type error and gets fixed one at a time. The class version takes one new class.
How this series judges it
Verdict: conditional. It comes down to what grows.
- If operations grow, use a union type — the kinds of nodes are settled and you keep adding processing such as aggregation, search, transformation, or rendering. Adding a function touches no existing type.
- If kinds grow, use a class hierarchy — the kinds of nodes you handle will keep growing while the operations stay close to fixed. Adding a class touches no existing class.
- If you load external data, use a union type — when the tree arrives from JSON or an API response, being able to handle it as a plain object carries more weight.
In application code, operations growing while kinds stay fixed is the more common situation. Making a union type the default and considering a class hierarchy only when kinds are likely to grow often is the order that works out in practice.
What would overturn this judgment
The weak point of a union type is that the blast radius of adding a kind cannot be read in advance. If 30 functions handle FsNode, the moment you add one kind, compilation stops in every one of them that has an exhaustiveness check. You touch a wide area on each change, so at that scale a class hierarchy keeps changes more local.
What deserves attention is that only the places with an exhaustiveness check stop. A branch written deliberately non-exhaustively, such as if (node.kind === 'file') { ... } else { /* assumes directory */ }, passes quietly even after a kind is added. Erring on the safe side is limited to the places that use switch and never.
One more thing: a class fits when each node has state of its own plus an invariant protecting that state. A plain object can be rewritten by anyone, so an invariant like "a directory's children are always sorted" cannot be upheld by types alone. Adding readonly only blocks assignment; it guarantees nothing about the order of the array's contents.
How this relates to existing articles
- Conditionals covers the basics of discriminated unions and exhaustiveness checks. This chapter is an example of applying them to a recursive structure and does not repeat the fundamentals.
- Inheritance and interfaces covers choosing between abstract classes and
implements. The class version in this chapter uses that shape directly.
Note that this site has no article yet on the recursive type alias used in this chapter. How to write one is contained in this chapter's example.