Алгебраические типы данных и Python09.07.2021 20:31

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

«Что?! Алгебраические типы данных?! Это же что-то из мира функциональных языков программирования. 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], мы более строго определяем возможные значения и делаем невалидные состояния непредставимыми в наших типах данных.

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