Discriminated Unions vs Subtyping

Overview

Subtyping is a form of type polymorphism that is very popular in Object-Oriented Programming. If you’re familiar with OOP languages such as Java or C#, then you very likely know it already.

Subtyping offers an alternative to Algebraic Data Types (discriminated unions). In this lesson, I’d like to compare these two approaches.

Defining types

Let’s go back to the example of a discriminated union representing a binary tree. It could, for example, be a tree of product categories in an e-commerce web application.

type Tree = 
      | { type: 'empty' }
      | { type: 'leaf', value: number }
      | { type: 'node', left: Tree, right: Tree };

A tree can either be:

• a node with references to left and right subtrees
• a leaf containing a numerical value
• empty

We can represent the same data structure using the OOP approach. We define an abstract class Tree and three concrete classes extending from Tree.

abstract class Tree {}

class Empty extends Tree { }

class Leaf extends Tree {
  constructor(private value: number) {
    super();
  }
}

class Node extends Tree {
  constructor(
    private left: Tree,
    private right: Tree,
  ) {
    super();
  }
}

Adding an operation

Now, let’s say that we want to create a textual representation of the tree. Let’s see how the implementation would look in both approaches.