Union vs sum types

Union types and sum types are programming language concepts that have existed for decades, but they seem to be gaining more popularity recently. While closely related, their nuanced differences affect their relative strengths. This article will explain these concepts and compare their pros and cons.

First, let's consider algebraic data types, which may sound complicated but are quite simple. We'll start with a familiar example: a struct. In a database used by my job, there are cases identified by unique identifiers, like CaseID_V2. We can think of a struct as an AND operator. CaseID_V2 is a new type formed by combining a u16 and a u32.

In programming, types can be viewed as sets of possible values. For u16, the values range from 0 to 65535. Similarly, u32 ranges from 0 to 4294967295. Since CaseID_V2 is composed of both u16 and u32, its possible values are the Cartesian product of these two sets. This is why structs are called product types.

However, sometimes we need a new type that is composed of one field OR another. For instance, in our database, the CaseID changed in 2021, leading to the _V2 suffix. Any data type containing a case ID must be able to have a notion of either a CaseID_V1 or a CaseID_V2. This is called a union type. By combining these into a struct, we get:

struct MyType {

case_id: Union<CaseID_V1, CaseID_V2>

}

The term "union type" comes from the fact that the possible values are the union of its members. However, there's a catch: if we define MyType as either a bool or a bool, it simplifies to just bool. This allows us to express uncertainty about types using union types and perform set operations on them. For example, if we have a function returning either u16 or i16, and another returning either u16 or u32, calling either function results in a union of u16, i16, and u32.

Sometimes, we don't want this deduplication. For example, if we want to represent both the Gregorian and Hijri calendar years, we can't simply union two u16 types, as they represent different things. Instead, we create new types that wrap the u16s and serve as tags, known as tagged unions or sum types. Sum types are useful when we need to distinguish each member distinctly.

In Rust, enums represent sum types, but they wrap their variants, meaning all values belong to the same type. This can be limiting in certain cases. Julia, being a dynamic language, allows for a more flexible approach, where values have types at runtime, and union types are only used to express the compiler's uncertainty about what's happening during runtime.