How can I define algebraic data types in Python?

Question

How can I define algebraic data types in Python (2 or 3)?

Answer 1

Python 3.10 version

Here is a Python 3.10 version of Brent's answer with pattern-matching and prettier union type syntax:

from dataclasses import dataclass

@dataclass
class Point:
    x: float
    y: float

@dataclass
class Circle:
    x: float
    y: float
    r: float

@dataclass
class Rectangle:
    x: float
    y: float
    w: float
    h: float

Shape = Point | Circle | Rectangle

def print_shape(shape: Shape):
    match shape:
        case Point(x, y):
            print(f"Point {x} {y}")
        case Circle(x, y, r):
            print(f"Circle {x} {y} {r}")
        case Rectangle(x, y, w, h):
            print(f"Rectangle {x} {y} {w} {h}")

print_shape(Point(1, 2))
print_shape(Circle(3, 5, 7))
print_shape(Rectangle(11, 13, 17, 19))
print_shape(4)  # mypy type error

You can even do recursive types:

from __future__ import annotations
from dataclasses import dataclass

@dataclass
class Branch:
    value: int
    left: Tree
    right: Tree

Tree = Branch | None

def contains(tree: Tree, value: int):
    match tree:
        case None:
            return False
        case Branch(x, left, right):
            return x == value or contains(left, value) or contains(right, value)

tree = Branch(1, Branch(2, None, None), Branch(3, None, Branch(4, None, None)))

assert contains(tree, 1)
assert contains(tree, 2)
assert contains(tree, 3)
assert contains(tree, 4)
assert not contains(tree, 5)

Note the need for from __future__ import annotations in order to annotate with a type that hasn't been defined yet.

Exhaustiveness checking for ADTs can be enforced with mypy using typing.assert_never() in Python 3.11+ or as part of the typing-extensions backport for older versions of Python.

def print_shape(shape: Shape):
    match shape:
        case Point(x, y):
            print(f"Point {x} {y}")
        case Circle(x, y, r):
            print(f"Circle {x} {y} {r}")
        case _ as unreachable:
            # mypy will throw a type checking error
            # because Rectangle is not covered in the match.
            assert_never(unreachable)

Answer 2

The typing module provides Union which, dissimilar to C, is a sum type. You'll need to use mypy to do static type checking, and there's a notable lack of pattern matching, but combined with tuples (product types), that's the two common algebraic types.

from dataclasses import dataclass
from typing import Union


@dataclass
class Point:
    x: float
    y: float


@dataclass
class Circle:
    x: float
    y: float
    r: float


@dataclass
class Rectangle:
    x: float
    y: float
    w: float
    h: float


Shape = Union[Point, Circle, Rectangle]


def print_shape(shape: Shape):
    if isinstance(shape, Point):
        print(f"Point {shape.x} {shape.y}")
    elif isinstance(shape, Circle):
        print(f"Circle {shape.x} {shape.y} {shape.r}")
    elif isinstance(shape, Rectangle):
        print(f"Rectangle {shape.x} {shape.y} {shape.w} {shape.h}")


print_shape(Point(1, 2))
print_shape(Circle(3, 5, 7))
print_shape(Rectangle(11, 13, 17, 19))
# print_shape(4)  # mypy type error

Answer 3

Here's an implementation of sum types in relatively Pythonic way.

import attr


@attr.s(frozen=True)
class CombineMode(object):
    kind = attr.ib(type=str)
    params = attr.ib(factory=list)

    def match(self, expected_kind, f):
        if self.kind == expected_kind:
            return f(*self.params)
        else:
            return None

    @classmethod
    def join(cls):
        return cls("join")

    @classmethod
    def select(cls, column: str):
        return cls("select", params=[column])

Crack open an interpreter and you'll see familiar behavior:

>>> CombineMode.join()
CombineMode(kind='join_by_entity', params=[])

>>> CombineMode.select('a') == CombineMode.select('b')
False

>>> CombineMode.select('a') == CombineMode.select('a')
True

>>> CombineMode.select('foo').match('select', print)
foo

Note: The @attr.s decorator comes from the attrs library, it implements __init__, __repr__, and __eq__, but it also freezes the object. I included it because it cuts down on the implementation size, but it's also widely available and quite stable.

Sum types are sometimes called tagged unions. Here I used the kind member to implement the tag. Additional per-variant parameters are implemented via a list. In true Pythonic fashion, this is duck-typed on the input & output sides but not strictly enforced internally.

I also included a match function that does basic pattern matching. Type safety is also implemented via duck typing, a TypeError will be raised if the passed lambda's function signature doesn't align with the actual variant you're trying to match on.

These sum types can be combined with product types (list or tuple) and still retain a lot of the critical functionality required for algebraic data types.

Problems

This doesn't strictly constrain the set of variants.