Python ADTs

adts.py

# tested with mypy 1.7.1, python 3.12

# Recursive ADT with exhaustive pattern matching
# Adapted from http://blog.ezyang.com/2020/10/idiomatic-algebraic-data-types-in-python-with-dataclasses-and-union/
#
# No generic/param polymorphic trees :(
# In many cases generic builtins (list, dict) + non-generic recursive ADTs (dataclasses) is  enough
# How about optional/either. In go NIL us used, in mypy there is optional and either can be encoded (though there are bugs):
#    https://github.com/python/mypy/issues/6748
#
# E.g. golang pre-generics (using type switches for ADTs https://eli.thegreenplace.net/2018/go-and-algebraic-data-types/)
#
# Or recursive non-generic ADTs as in this file
# For both, see https://github.com/python/mypy/issues/13693
#
# At least we have strict null checks by default
# https://mypy.readthedocs.io/en/stable/kinds_of_types.html#no-strict-optional


from __future__ import annotations
from dataclasses import dataclass
import enum
from typing import assert_never
from typing import Mapping
from typing import Sequence

print("RUNTIME!!!!!!!!!!!!!!!!")

@dataclass(frozen=True)
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)
        case _ as unreachable:
            # mypy will throw a type checking error
            # because Rectangle is not covered in the match.
            assert_never(unreachable)

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: Tree):
    match shape:
        case None:
            print("none")
        case Branch(x,l,r):
            print("Branch")
        case _ as unreachable:
            # mypy will throw a type checking error
            # because Rectangle is not covered in the match.
            assert_never(unreachable)
print_shape(tree)
print(Branch(value=1, left=Branch(value=2, left=None, right=None), right=Branch(value=3, left=None, right=Branch(value=4, left=None, right=None))))

x: Mapping[int,str] = {2: "hi"} # immutable using this trick: https://justincaustin.com/blog/mimicking-immutability-python-type-hints/
y: Sequence[int] = [2,3,4]     # immutable using this trick

# x[2] = "ho" # doesn't typecheck as expected
# y[0] = 1    # doesn't typecheck as expected

def f() -> list[Tree]:
    return []