Algebraic Data Types are a way of structuring data types in Statically-typed Functional Programming (SFP) as a style. 3 Things there: 1) what are ADTs? 2) what does SFP as a style mean? 3) why would I want ADTs?
// Define an ADT
enum PayloadType {
V1Payload(name: String),
V2Payload(name: String, id: u32),
V3Payload(name: String, id: i32, request_data: (SomeData, Vec<String>))
}
// Use the ADT!
fn do_with_payload(payload: PayloadType) {
match payload {
V1Payload(name) => // Do something with this name,
V2Payload(name, id) => {
println!("Got a V2 payload with id {}: {}", id, name);
// do something with this name
},
V3Payload(name, id, request_data) => {
println!("Got a V3 payload with id {}: {}", id, name);
process_request_data(request_data);
}
}
}
Algebraic data types allow you to combine multiple data types (a Product type, such as a Struct in imperative languages or a simple data class in OOP languages) and a limited form of polymorphism - an instance of PayloadType may either be a V1Payload, V2Payload, or V3Payload. While this may seem very simple (because it is! :) ) and very restrictive (I can't arbitrarily subclass PayloadType into 10 nested subclasses :( ), ADTs aim to be a simple, flexible, and trade their restrictions many times over with compile-time safety (and there are ways to get around the restrictiveness anyways). Rust's enum example shows how you can use specific code based off the enum variant you have using a match statement (a generalization of if/then which only works on True/Truthy values and False/Falsey values to give you 2 different code paths). Match statements with Sum Types can be checked at compile time for exhaustiveness, and this property opens up a world of possibilities in SFP style.
By as a style, I mean that ADTs can be used in any language. The main difference between using ADTs in SFP languages built around them (Haskell, Gleam, Rust, etc) vs in other languages such as Python, Javascript, or Java is a mix of certainty/reliability and convenience. Statically typed languages like Java essentially allow you to create full ADTs and use them to their full potential, it's just not super convenient. Sealed interfaces + record classes in Java give you everything ADTs give you, in conjunction with match expressions. They're just...a lot more boilerplate than in, say, Rust. With record classes and switch expressions in Java specifically, or matches and sum types in functional languages, you can often deconstruct the value to access its parts as in the Rust example above because on each code path, you know exactly which variant the enum instance has and thus can safely extract the parts knowing exactly what data types they have. And in these languages, the compiler can check your match expressions have a branch for every possible value of the data type, giving you strong compile time safety. Other languages like Go may have Switch expressions, but these may not be checked for exhaustiveness and these languages may not have true discriminated unions so you can't get compile-time support for casting from your sum type to its specific variants and destructuring its parts. Python recently gained match statements with some destructuring ability, and Javascript/Typescript can allow for switches with some destructuring, but it may not be as terse as in other languages and, more importantly, dynamic languages never truly guarantee what type a given variable has at runtime (what in type systems is referred to as "soundness", i.e. I gave variable A the type/type annotaiton MyType in my code, if the type system is sound then at runtime A will always be MyType, but if the type system is unsound, maybe A will be converted to OtherType which will lead to code behaving incorrectly). All the same, any language with compound datatypes (classes or structs), match/switch statement, and a good compiler/type checker/static analysis tool can give you build/compile time-exhaustive matching for sum types.
Why would you want ADTs? Especially if you have to add Mypy/Typescript to your project and start doing static typing (in a dynamic language) or potentially write a lot of boilerplate (in Go or Java, although recent Java is much better about this)? The simple answer - programs become very nice and clear and expressive. Let's have a small compare contrast with an OOP-style example. Say you have a part of your code where you need to write data to a bytes buffer, and you can't pin it down to 1 strategy for writing to the buffer and don't have just 1 type of data you want to write to the buffer. The most immediate answer which may come to people's mind would be to create a class with a method for writing to a byte buffer:
# Yes in actual Python code this would be an Abstract Base Class (or if you're extra-cool, the more apt Protocol)
class ByteWriter:
def write_to_bytes(self, buffer: bytearray) -> bytearray:
pass
However, now you'd have to create new classes which may have to wrap other data, inherit from this class, and now everything is forced to go through the object-oriented paradigm. The problem we wanted to solve is that we wanted a general interface for writing to a bytes buffer, because we needed some polymorphism (if this is application code and not library code, maybe we just wanted 2 different byte writing strategies and just for a list of numbers or strings, nothing more). OOP gives us this polymorphism, but its very coarse-grained. How many implementors of ByteWriter are there? The compiler won't really tell you and (in a dynamic language) it may change at runtime. Are there certain invariants you want to be very careful of upholding? I'm sure there's ways to do it, but with how decentralized class inheritance is as a mechanism, it may not be easy to uphold across all subclasses. Is there a simpler, safer way to do this? For different strategies which work with some payloads and not others, you could just bundle payloads as variants with a tag indicating what kind of payload you're carrying, and dispatch in a match to specific functions which do what you want:
from enum import Enum
from typing import assert_never, Literal, Any
class Stategy(Enum):
TYPE1 = 1 # This only works with ints
TYPE2 = 2 # This only works with strings
TYPE3 = 3 # This works with any type but may be less efficient
# Discriminated union at home in Python
WriterSumType = (Literal[Strategy.TYPE1], int)
| (Literal[Strategy.TYPE2], str)
| (Literal[Strategy.TYPE3], Any, Config) # Config is some type
def byte_writer(buffer: bytearay, writer_sum: WriterSumType) -> bytearray:
match writer_sum:
case (Strategy.TYPE1, int_data):
return int_writer(buffer, int_data)
case (Strategy.TYPE2, str_data):
return str_writer(buffer, str_data)
case (Strategy.TYPE3, other_data, config):
return any_writer(buffer, other_data, config)
case _:
assert_never(writer_sum) # In a dynamic language, you'd want something like this
# a function which only takes a Never/"Bottom" type which the type checker will use to yell at you if your match statement isn't exhaustive, and which will throw an error at runtime to keep your types sound.
For our problem, we may only need a handful of different byte writing strategies implemented by a couple functions and we may not want to extend that any further. A match statement can let us handle exactly that. We could match on the type of the payload, but this is just an example of how this strategy could be used and is flexible when your variants have different numbers of arguments, for example. No need to explicitly cast types which can erode compile-time safety. And discriminants allow us to go beyond what dispatching on types could do, i.e. we could add even more flexibility for strings by having a variant with a 3rd element, a customized byte writing function only on strings that the user can provide. If the user of this function makes a tuple with the new disccriminant/strategy, and wraps that with a string and their function in a tuple, you could use the same byte_writer function to serialize some strings using the default writer and some using custom writers all based off what argument you call this function with. Or you could add another variant which cleans strings before writing, which would have the same type signature as variant 2 with (Strategy, str) and thus you could not distinguish these cases in a match statement using just type checking. Optimally you should not push code to prod if the type check doesn't succeed (if you fail to make your match exhaustive), and that means every time you want to add a variant to your sum type you have to go and update each match with that sum type, but that's what we want. We want our tools to tell us that our code has a new edge case and not let us move forward until we do something about it. The point of sum types is to give us additional flexibility through limited polymorphism (my sumtype is actually variant A, B, C, etc). Then number of variants for a specific sum type is finite, versus something like a class, where the number of subclasses may be infinite. Oftentimes (especially in application code) it's better to focus on your specific (usually finite!) set of use cases and work from there. The Expression Problem is a famous problem in computer science which says that you can either easily extend the number of variants of a type or the number of behaviors of a type easily but not both. Extending a base clase with a new method may require updating who knows how many subclasses. Sum types land squarely in favor of extending behavior more easily than the number of variants. Making extending variants harder becomes a feature, not an issue, since now the compiler guarantees at compile time that if you've extended a sum type, you're addressing every "callsite" or location you use that sum type. Even still, sum types as a tool in functional programming are very old. So old in fact that there's a myriad of ways of getting around the Expression problem (restricting variants) and adding additional polymorphism when you need it. The most direct way of doing so is by adding generics into the mix, as with the venerable Option type:
enum Option<T> {
Some(T),
None
}
This is the exact definition of the Option type in Rust's standard library. Rust gains compile-time null safety, through a 4-line enum (and building a language around that). Using generic parameters, you can reuse the same enum for different concrete types, which in Rust gives you null-safe pointers like &Option which forces you at compile tim to handle whether the reference is &DataType or None/null. This is the same exact strategy for generic containers like List or Map<K, V>, this time with your enum acting as a "container".Rust's Result type
enum Result<T, E> {
Ok(T),
Err(E)
}
is just a specific use case for what in Haskell is called the Either type, which as a Rust enum would be
enum Either<T, U> {
Left(T),
Right(U)
}
We can utilize the same compile-time guaranteed tag/discriminant matching with our sum types and match statements and handle generic values in our payload. If you want something a little more structured, you could use interfaces, which are essentially unbounded Union types (potentially infinite Unions of types) that are required to implement some function or give you access to some function. For example
enum WriterVariant {
DefaultWriter(Box<dyn Writer>),
ConfiguredWriter(Box<dyn Writer>, WriterConfigOptions)
}
The first field in each variant has a lot going on because of Rust-specific, low-level implementation details, but what we care about is the Writer trait or interface. Writer is a type that implements the function fn write(&mut self, buf: &[u8]) -> Result<usize>, which writes the buffer into the Writer. Because this is an interface, that field could be a File, it could be a TcpStream, or it could be a in-memory bytes buffer Vec.
As I mentioned above, you could extend the sum type to something like:
WriterSumType = (Literal[Strategy.TYPE1], int)
| (Literal[Strategy.TYPE2], str)
| (Literal[Strategy.TYPE3], Any, Config) # Config is some type
| (Literal[Strategy.TYPE4], str, Fn(bytesarray, Str) -> bytesarray)
Sum types give you compile-time safety with delimited polymorphism, and this is their greatest strength. Due to their restriction (versus unbounded Union types like just a class or interface), sum types give you a lot of power to structure your code in return. And since sum types can contain any type, such as a generic type, an interface, a function/callback, etc, they're a highly extensible building block that can give you exactly the level of polymorphism you need and as much structure as you want.
Product Types (aka Structs) - A compound, static data type (T1, T2, ..., Tn) of n-many datatypes where Ti is any valid type. Implementation under the hood can vary (with named fields where fields are stored contiguously in memory, these are Structs in C, Go, or Rust, with index-only fields, this could be implemented with Tuples such as in Python, or as simple data classes in any OOP language). This is the most simple form of data more complex than a scalar datatype. When going the contiguous layout route, especially paired with stack-allocated immutable data (such as integers, immutable Strings, other structs composed of said types), these product types/structs gain the benefits of stack-allocation, lack of pointer indirection (as in GC/heap-heavy languages like Java), and (on 64-bit systems) very cheap/essentially free copying if the type's size is 8 bytes or less (the size of a pointer on a 64 bit system, types below 8 bytes can often end up padded for alignment reasons anyways). But that's implementation-dependent. The real benefit of product types is as part of the semantics of Algebraic Data Types as a whole. This is a logical AND of types (T1 AND T2). Why are they called Product types? Consider the following example: Booleans have 2 possible values - True, and False. u8's have 256 possible values. How many possible values does a 2-tuple (Bool, u8) have? 512, 1 for each combination of True-False and each possible value of u8. So a Product type P = (T1, T2, ..., Tn) has as many values as T1 does, times as many values as T2 does, times ... as many values as Tn does, or something like range(T1)*range(T2)*...*range(Tn)-many values, where range gives you the number of possible values for the given type.