Возможно, кто-то из читателей, увидев заголовок этой статьи, подумает что-нибудь вроде:

"Что?! Алгебраические типы данных?! Это же что-то из мира функциональных языков программирования. Python?! Ну нет... Где Python со своей динамической утиной типизацией, а где типы данных, и уж тем более алгебраические..."

Что-то в таком духе. Но, на самом деле, в Python есть своя система типов, кроме того Python считается языком со строгой типизацией, а благодаря mypy и аннотациям, корректность используемых типов может быть проверена статически без непосредственного запуска программы. Помимо всех этих достаточно интересных особенностей, в Python есть возможность работать и с алгебраическими типами данных. Так что же это за типы данных, как они выглядят в Python, и какую практическую пользу приносят — попробуем разобраться в этой статье.

Содержание

Примечание. Далее в примерах я буду использовать возможности Python 3.9 и 3.10, а также mypy версии 0.910 (со следующими настройками) для статической проверки корректности типов.

Небольшое вступление

Скорее всего, если вы занимаетесь программированием в каком-то виде, то вы уже используете алгебраические типы данных, возможно, не подозревая об этом.  Под этим несколько академическим понятием скрывается очень простая идея композиции — как из одних типов данных получить другие, составные и более сложные (именно на эту идею композиции типов данных и намекает картинка на обложке этой статьи).

Итак, алгебраический тип данных — это такой тип данных, который является композицией других типов. Вот такое незатейливое определение. Алгебраические же эти типы данных из-за того факта, что новые составные типы получаются с помощью аналогов простых алгебраических операций сложения и умножения. Чтобы разобраться, что же могут представлять из себя сумма и произведение типов данных, для начала стоит понять, что такое тип данных вообще.

Самый простой способ думать о типе данных — это представить этот тип как множество всех его значений. Например, тип bool — это двухэлементное множество, которое содержит элементы True и False. Следующий перечисляемый тип Color:

from enum import Enum

class Color(Enum):
    Red = "r"
    Green = "g"
    Blue = "b"

является множеством, которое содержит 3 элемента. Тип данных int можно представить как множество всех целых чисел. А тип данных str — это множество, элементами которого являются пустая строка, строки "привет" и "hello", строка с текстом вашей любимой песни, и так далее. В общем, как несложно заметить, множество значений типа данных str содержит довольно много элементов.

1 и 0

Если мы можем думать о каком-то типе данных как о множестве значений, то что же представляет из себя одноэлементное множество, или вовсе пустое множество? В Python есть несколько типов данных, которые имеют только одно значение. Например, None является единственным значением типа NoneType. В аннотациях типов именно это значение используется для обозначения того факта, что функция ничего не возвращает (фактически, является процедурой, а не функцией):

def do_something_interesting(value: int) -> None:
    ...

Другим примером может быть пустой кортеж (tuple):

from typing import Tuple

empty: Tuple[()] = ()

Значение () является единственным элементом множества всех значений типа Tuple[()]. Есть еще несколько похожих примеров, но общий смысл, думаю, понятен. Подобные тип�� данных, которые содержат только одно значение, называются единичными типами данных. Определение собственного единичного типа данных может принести вполне практическую пользу. Рассмотрим следующий пример:

from enum import Enum
from typing import Union

class Default(Enum):
    Value = 0

def process(value: Union[int, None, Default] = Default.Value) -> int:
    if value is Default.Value:
        return 0
    elif value is None:
        return 1
    else:
        # В этой ветке mypy "понимает", что value имеет тип int, 
        # и поэтому операция умножения допустима
        return value * 2

Как видно из примера, None является допустимым значением аргумента функции. Использование типа Default и его единственного значения Default.Value позволяет отличить ситуацию, когда функция вызвана без аргументов process(), от ситуации, когда None явно передается в качестве аргумента функции process(None), и выполнить соответствующую ветку условного оператора if.

Отлично, но вернемся к типам данных и множествам. Мы рассмотрели единичные типы данных, которые представимы в виде одноэлементного множества. Осталось разобраться с пустым множеством. Так зачем же может быть нужен тип данных, значений которого вообще не существует? Подобный тип данных называют ненаселенным (uninhabited type), и обычно он используется, чтобы показать невычислимость какого-то выражения, например, брошено исключение, выход из программы, бесконечный цикл, и т.п. В Python также есть поддержка такого типа данных:

from typing import NoReturn

def stop() -> NoReturn:
    raise RuntimeError("Не получится!")

Если же мы что-то напутаем и попробуем вернуть из такой функции значение какого-то другого типа, например:

from typing import NoReturn

def stop(value: int) -> NoReturn:
    if value < 0:
        return 42
    raise RuntimeError("Не получится!")

то, запустив mypy, мы сразу увидим ошибку:

error: Return statement in function which does not return
    return 42

Кроме того, если тип какой-то переменной объявлен NoReturn, то мы не сможем присвоить этой переменной ни одно значение, так как NoReturn является ненаселенным типом, как мы выяснили, и значений такого типа не существует:

from typing import NoReturn

value: NoReturn = None
other_value: NoReturn = ()

При статической проверке типов mypy сообщит об ошибке что-то вроде:

error: Incompatible types in assignment (expression has type "None",
variable has type "NoReturn")
    value = None

error: Incompatible types in assignment (expression has type "Tuple[]",
variable has type "NoReturn")
    other_value: NoReturn = ()

Тип-произведение

Сложно представить себе язык программирования без какой-либо поддержки типов-произведений (product type). Это, скорее всего, самый простой способ получить новый тип данных на основе существующих, объединив их вместе. Рассмотрим простейший пример типа-произведения — кортеж из двух элементов, или пара:

from enum import Enum
from typing import Tuple

class ChessPieceType(Enum):
    """Тип шахматной фигуры."""
    King = "Король"
    Queen = "Ферзь"
    Rook = "Ладья"
    Bishop = "Слон"
    Knight = "Конь"
    Pawn = "Пешка"

class ChessPieceColor(Enum):
    """Цвет шахматной фигуры."""
    White = "Белый"
    Black = "Черный"

ChessPiece = Tuple[ChessPieceType, ChessPieceColor]

# Белый король
white_king: ChessPiece = (ChessPieceType.King, ChessPieceColor.White)
# Черный ферзь
black_queen: ChessPiece = (ChessPieceType.Queen, ChessPieceColor.Black)

В приведенном выше примере ChessPiece — это тип-произведение пара, который является композицией двух других типов: типа шахматной фигуры ChessPieceType и цвета ChessPieceColor. Уже можно догадаться, почему такой тип называется произведением. Тип ChessPieceType имеет 6 возможных значений, а тип ChessPieceColor имеет 2 возможных значения. Множество возможных значений типа ChessPiece является декартовым произведением множеств возможных значений двух других типов, и содержит 12 элементов:

Другими словами, шахматная фигура ChessPiece — это тип фигуры ChessPieceType И цвет фигуры ChessPieceColor. Мы могли бы добавить еще какие-нибудь свойства шахматной фигуры нашему типу-произведению, например, позицию на доске PositionOnBoard:

# продолжение предыдущего примера

# Шахматная фигура — это тип фигуры 
#   И цвет фигуры 
#   И позиция фигуры на доске
ChessPiece = Tuple[ChessPieceType, ChessPieceColor, PositionOnBoard]

В таком случае количество возможных значений типа ChessPiece увеличится до 768 (6 типов x 2 цвета x 64 возможные позиции).

Помимо кортежей, в разных языках программирования к типам-произведениям можно отнести разнообразные структуры (struct), классы образцы (case class), записи (record), и т.п. Одним из способов определить тип-произведение в Python является использование декоратора dataclass из соответствующего модуля стандартной библиотеки. Например, определим следующий тип:

from dataclasses import dataclass
from enum import Enum

class Role(Enum):
    Administrator = 0
    Editor = 1
    Reader = 2

@dataclass(frozen=True)
class User:
    name: str
    role: Role
    is_active: bool

Тип данных User является композицией типов str, Role и bool. Получается, что при таком определении, пользователь User — это имя пользователя str И роль пользователя Role И флаг активности bool.

При использование типов-произведений mypy помогает отследить корректность обращений к каждому полю:

# продолжение предыдущего примера

def get_user_info(user: User) -> str:
    # Автору этого кода почему-то захотелось прибавить число 42 
    # к имени пользователя...
    name = user.name + 42
    return f"{name}: {user.role.name} {user.is_active}"

Конечно, mypy сразу проинформирует нас об ошибке в таком коде:

error: Unsupported operand types for + ("str" and "int")
    name = user.name + 42

Наглядным примером аналогии с математическими операциями может быть использование ненаселенного типа, который мы рассматривали в предыдущем разделе статьи, при определении типа-произведения:

from dataclasses import dataclass
from typing import NoReturn

@dataclass(frozen=True)
class Ooops:
    number: int
    string: str
    nothing: NoReturn

Сколько может быть возможных значений у подобного типа данных? Количество возможных значений типа int x количество возможных значений типа str x 0 (не существует значений типа NoReturn). Получается, что у типа Ooops вообще нет возможных значений, и такой тип также будет ненаселенным. Действительно, если мы попробуем как-то создать значение этого типа:

# продолжение предыдущего примера

Ooops(42, "hello", None)

То получим ошибку от mypy:

error: Argument 3 to "Ooops" has incompatible type "None"; expected "NoReturn"
    Ooops(42, "hello", None)

В завершении этого раздела стоит отметить, что в большинстве языков программирования использование типов-произведений — это единственный способ создания новых типов данных на основе существующих.

Тип-сумма

Тип-сумма (sum type) — это такой тип данных, значения которого могут быть одним из нескольких взаимоисключающих вариантов. Поддержка типов-сумм реже встречается в различных языках программирования по сравнению с типами-произведениями. В языках, в которых такая поддержка присутствует, они могут также называться размеченными объединениями (tagged union) или просто вариантами (variant). Чаще всего тип-сумма и имеется в виду, когда говорят об алгебраическом типе данных.

Простейшим примером типа-суммы может быть тип bool. Что представляет из себя значение типа bool? Это True ИЛИ False — два взаимоисключающих варианта. Еще одним примером может быть следующий перечисляемый тип Fruit:

from enum import Enum

class Fruit(Enum):
    Apple = "яблоко"
    Banana = "банан"
    Peach = "персик"

Значение типа Fruit — это Fruit.Apple ИЛИ Fruit.Banana ИЛИ Fruit.Peach. На первый взгляд кажется, что это очень простая, очевидная идея. Но далее мы увидим, что типы-суммы являются очень мощным средством моделирования предметной области программы.

Тип-сумма — это не только простое перечисление значений. Каждый вариант типа-суммы может иметь свой собственный тип. В Python для выражения этой идеи может быть использован тип Union из модуля typing:

from enum import Enum
from typing import Union

class Fruit(Enum):
    Apple = "яблоко"
    Banana = "банан"
    Peach = "персик"

class Vegetable(Enum):
    Cabbage = "капуста"
    Carrot = "морковь"

Food = Union[Fruit, Vegetable]

apple: Food = Fruit.Apple  # OK
carrot: Food = Vegetable.Carrot  # OK

# Mypy error:  Incompatible types in assignment (expression has type "int", 
# variable has type "Union[Fruit, Vegetable]")
hmmm: Food = 42

В данном примере значение типа Food — это значение типа Fruit ИЛИ значение типа Vegetable. Количество возможных значений типа Food — это сумма количества возможных значений типов Fruit и Vegetable, всего 5 возможных фруктов и овощей.

Мы можем объявлять объединение любых произвольных типов, например, мы могли бы определить адрес следующим образом:

from dataclasses import dataclass
from typing import Union

@dataclass(frozen=True)
class AddressDetails:
    city: str
    street: str
    house_number: int

Address = Union[str, AddressDetails]

Здесь Address — это строка str ИЛИ AddressDetails. Далее мы могли бы использовать Address для аннотаций типов, причем mypy позволит статически проверить корректность обращений к каждому варианту типа-объединения:

# продолжение предыдущего примера

def do_something_with_address(address: Address) -> None:
    if isinstance(address, str):
        print("Адрес — это строка:", address)
    elif isinstance(address, AddressDetails):
        print(f"Адрес: {address.city}, {address.street}, {address.house_number}")
    else:
        assert False, "Больше вариантов нет!"

Стоит обратить внимание, что мы должны явно указать, что делать с каждым вариантом типа-объединения, иначе mypy будет сообщать об ошибках.

Примечание. Строго говоря, Union — это не совсем тип-сумма из-за того факта, что типы вариантов должны быть разными. Например, в системе типов Python Union[int, int] — это тоже самое, что и просто int, и мы не сможем понять значение какого из вариантов фактически используется. Это ограничение можно обойти, определив дополнительные типы-"обёртки" для каждого варианта. Но оставим это различие в стороне для простоты изложения.

Optional или отсутствие значения

Еще одним примером типа-суммы может быть тип Optional из модуля typing стандартной библиотеки Python, который выражает простую идею, что значение может отсутствовать. Тип Optional[T] эквивалентен типу Union[T, None], значением этого типа является значение произвольного типа T ИЛИ значение None. Если мы работаем со значениями типа Optional, то мы должны явно обрабатывать случай, когда значение отсутствует:

from dataclasses import dataclass
from typing import Optional

@dataclass(frozen=True)
class Article:
    id: int
    title: str

def fetch_article(article_id: int) -> Optional[Article]:
    """Получаем статью по её ID каким-то образом."""

def show_article() -> None:
    article = fetch_article(42)
    print("Заголовок статьи:", article.title)

При проверке типов mypy найдёт следующую ошибку:

error: Item "None" of "Optional[Article]" has no attribute "title"
    print("Заголовок статьи:", article.title)

Действительно, если мы определили, что значение может отсутствовать, то мы должны явно обработать такой случай:

# продолжение предыдущего примера

def show_article() -> None:
    article = fetch_article(42)
    
    if article is None:
        print("Статьи не существует.")
    else:
        # Здесь mypy "понимает", что article точно не None, 
        # т.к. выше в коде этот случай обработан
        print("Заголовок статьи:", article.title)

Использование типа Optional позволяет mypy предупредить нас, если мы вдруг забудем обработать случай None, что очень часто позволяет избежать досадных ошибок в программе (см. Ошибка на миллиард долларов).

Собираем конструктор из типов

Использование типов-сумм и типов-произведений при проектирование собственных типов данных выглядит как конструктор (ещё раз вернемся к картинке на обложке статьи). Мы объединяем и комбинируем одни типы данных, и получаем другие, более сложные типы данных. Рассмотрим ещё один, более приближенный к реальности, пример. Допустим, мы разрабатываем систему аутентификации пользователей на сайте. Мы можем определить следующие типы данных:

from dataclasses import dataclass
from typing import Union

@dataclass(frozen=True)
class SignInWithEmail:
    email: str
    password: str

@dataclass(frozen=True)
class SignInWithSms:
    phone_number: str
    code: str

@dataclass(frozen=True)
class SignInWithSecretToken:
    token: str

SignInMethod = Union[
    SignInWithEmail, 
    SignInWithSms, 
    SignInWithSecretToken,
]

Пользователи могут попасть на наш сайт, зная адрес электронной почты и пароль ИЛИ получив код в SMS на номер телефона ИЛИ используя секретный токен. Далее мы можем использовать тип данных SignInMethod следующим образом:

# продолжение предыдущего примера
from typing import NoReturn

def assert_never(value: NoReturn) -> NoReturn:
    raise AssertionError(f"Необработанный вариант: {value}")

def sign_in(method: SignInMethod) -> None:
    if isinstance(method, SignInWithEmail):
        print("Вход на сайт по email и паролю:", method.email, method.password)
    elif isinstance(method, SignInWithSms):
        print("Вход на сайт через SMS-код:", method.phone_number, method.code)
    elif isinstance(method, SignInWithSecretToken):
        print("Вход на сайт с секретным токеном:", method.token)
    else:
        assert_never(method)

В каждой ветке условного оператора if mypy проверит корректность обращения к атрибутам. Например, мы не сможем обратиться к номеру телефона phone_number из ветки, в которой используется метод входа по электронной почте и паролю.

Функция assert_never — это известный трюк, который позволяет mypy проверить, что разобраны все варианты типа-объединения (exhaustiveness checking). Если мы расширим определение типа SignInMethod, добавив вход по секретному числу (идея так себе), но забудем обработать этот вариант:

# продолжение предыдущего примера

SignInMethod = Union[
    SignInWithEmail, 
    SignInWithSms, 
    SignInWithSecretToken, 
    int,
]

def sign_in(method: SignInMethod) -> None:
    # Этот метод остался без изменений
    ...

То mypy сообщит нам, что один из вариантов не учтён:

error: Argument 1 to "assert_never" has incompatible type "int"; expected "NoReturn"
   assert_never(method)

Сопоставление с образцом

Такой подход напоминает механизм сопоставления с образцом (pattern matching), который присутствует в некоторых языках программирования. А использование mypy для статической проверки типов позволяет проверить, что все варианты типа-объединения явно обработаны. Более того, начиная с версии 3.10 и в Python появилась поддержка сопоставления с образцом (подробнее можно почитать в PEP-622). Код из предыдущего примера в Python 3.10 будет выглядеть следующим образом:

# Python 3.10
# продолжение предыдущего примера

def sign_in(method: SignInMethod) -> None:
    match method:
        case SignInWithEmail(email=email, password=passw):
            print("Вход на сайт по email и паролю:", email, passw)
        case SignInWithSms(phone_number=pn, code=code):
            print("Вход на сайт через SMS-код:", pn, code)
        case SignInWithSecretToken(token=token):
            print("Вход на сайт с секретным токеном:", token)

# Выведет: Вход на сайт по email и паролю: email@example.org password123
sign_in(SignInWithEmail("email@example.org", "password123"))

# Выведет: Вход на сайт через SMS-код: 79001234567 abcd
sign_in(SignInWithSms("79001234567", "abcd"))

# Выведет: Вход на сайт с секретным токеном: secret-token
sign_in(SignInWithSecretToken("secret-token"))

Примечание. На момент написания статьи mypy 0.910 не поддерживает новый механизм сопоставления с образцом, но работа над этим уже идёт.

В чём польза?

Несмотря на простоту самой идеи, алгебраические типы данных являются очень мощным и выразительным средством моделирования предметной области программы. Итак, какие же преимущества есть у проектирования типов данных подобным образом? Можно выделить несколько важных моментов:

  • Использование алгебраических типов данных позволяет моделировать сущности предметной области более наглядно и просто. Имя пользователя — это (имя И фамилия) ИЛИ (фамилия И инициалы). Продукт в книжном магазине — это книга ИЛИ газета ИЛИ сувенир. И тому подобное.

  • Тип-сумма часто является более простой альтернативой иерархии классов в ООП. Не нужно выделять какую-то базовую абстракцию, которая определяет общие характеристики для всех вариантов. Не нужны интерфейсы и их реализация (см. паттерн посетитель). Данные просто используются, а mypy помогает статически проверить, что использование данных корректно с точки зрения объявленных типов.

  • Используя алгебраические типы данных, мы можем делать невалидные состояния непредставимыми. Например, тип-данных SignInMethod из предыдущего раздела мы могли бы определить следующим образом:

    from dataclasses import dataclass
from typing import Optional

@dataclass(frozen=True)
class SignInMethod:
    email: Optional[str] = None
    password: Optional[str] = None
    phone_number: Optional[str] = None
    code: Optional[str] = None
    token: Optional[str] = None

sign_in_with_email = SignInMethod(
    email="email@example.org", 
    password="password123",
)

sign_in_with_token = SignInMethod(token="secret-token")
...

    Чем это хуже использования типа-суммы? Такой подход плох тем, что можно создать концептуально невалидное значение SignInMethod(), все атрибуты которого будут None. Наш тип данных позволяет создать такое значение. Используя же тип Union[SignInWithEmail, SignInWithSms, SignInWithSecretToken], мы более строго определяем возможные значения и делаем невалидные состояния непредставимыми в наших типах данных.

Ссылки по теме