Классы типов и словари

Как Haskell делает ad-hoc полиморфизм без хаоса: классы типов и их реализация словарями.

Класс типов — именованный набор операций (интерфейс), для которого типы предоставляют реализации (instance); вызов выбирает реализацию по типу.

Проблема перегрузки и решение Haskell

Хочется писать show x, x == y, x + y для разных типов с разной реализацией — это ad-hoc полиморфизм. Но бесконтрольная перегрузка плохо дружит с выводом типов. Haskell ввёл классы типов: объявляем класс с сигнатурами методов, а для каждого типа — instance с реализациями. Тип функции тогда несёт ограничение: show : Show a => a -> String читается «для любого a, у которого есть instance Show».

class Show a where
  show :: a -> String

instance Show Bool where
  show True  = "True"
  show False = "False"

instance Show Int where
  show n = ... -- своё

-- ограничение в типе:
print2 :: Show a => a -> a -> String
print2 x y = show x ++ ", " ++ show y

Под капотом: словари

Магии нет. Компилятор превращает ограничение Show a => в дополнительный скрытый аргумент — словарь (dictionary): запись с реализациями методов класса для конкретного типа. Вызов show x компилируется в «взять метод show из словаря и применить к x». Class — это тип записи-словаря, instance — конкретная запись, ограничение в сигнатуре — скрытый параметр-словарь.

Демонстрация: классы типов руками

Смоделируем класс Show явными словарями и функцию с «ограничением» — она просто принимает словарь дополнительным аргументом, как и делает GHC после трансляции.

# словарь = реализации методов класса Show для конкретного типа
show_bool = {"show": lambda b: "True" if b else "False"}
show_int  = {"show": lambda n: "Int(" + str(n) + ")"}

# функция с ограничением (Show a => ...) принимает словарь явно
def print2(dict_show, x, y):
    s = dict_show["show"]
    return s(x) + ", " + s(y)

print("print2 Bool :", print2(show_bool, True, False))
print("print2 Int  :", print2(show_int, 7, 42))
# выбор словаря по типу делает компилятор; здесь — мы вручную

Вывод:

print2 Bool : True, False
print2 Int  : Int(7), Int(42)

Видно, как один и тот же print2 ведёт себя по-разному в зависимости от переданного словаря. Компилятор Haskell подставляет нужный словарь автоматически, выводя его из типа аргумента.

Классы против интерфейсов ООП

Классы типов мощнее ООП-интерфейсов в нескольких отношениях. Реализацию можно добавить после определения типа (даже для чужого типа) — нет проблемы «не могу реализовать интерфейс для String». Метод может зависеть от типа в возвращаемом значении (read : Read a => String -> a) — диспетчеризация по результату, чего ООП не умеет. И instance выбирается на этапе компиляции по типу, а не по значению-объекту.

Как работает под капотом

Суперклассы (class Eq a => Ord a) — это словари, ссылающиеся на другие словари. Несколько ограничений ((Show a, Eq a) => ...) — несколько скрытых аргументов. Когерентность (один тип — один instance) гарантирует, что выбор словаря однозначен. Этот же приём «передачи словаря» лежит в основе implicit-параметров Scala и трейтов Rust (где словарь — таблица методов, vtable).

Частые ошибки

Путать класс типов и класс ООП. Класс типов — это интерфейс плюс механизм словарей, без наследования объектов и состояния.
Забывать ограничение в сигнатуре. Использовали show в полиморфной функции — обязаны написать Show a =>, иначе словаря неоткуда взять.
Ожидать выбор instance по значению. Выбор идёт по типу на этапе компиляции (с поправкой на полиморфизм времени выполнения через словари).

Итоги

Класс типов — интерфейс операций; instance — реализация для конкретного типа.
Ограничение C a => компилируется в скрытый аргумент-словарь.
Словарь — запись методов; вызов берёт метод из словаря.
Классы мощнее ООП-интерфейсов: поздняя реализация, диспетчеризация по результату.