Теория языков программирования

Типы-классы и трейты

В 1989 году создатели Haskell спорили: как написать функцию `sort`, которая работает для любого типа с порядком - но не требует единого суперкласса? Решением стали типы-классы. Тридцать лет спустя Rust скопировал эту идею в трейты - и весь Rust ecosystem держится на них.

  • **Rust serde**: библиотека сериализации работает с любым типом через трейты `Serialize`/`Deserialize` - без единой строки кода в самой библиотеке для конкретных типов пользователя
  • **Haskell lens**: оптики строятся через типы-классы `Functor`, `Applicative`, `Monad` - позволяя писать код, работающий с любой структурой данных без общего суперкласса
  • **Rust async**: `Future`, `Stream`, `AsyncRead` - все async-абстракции в Rust реализованы через трейты, что позволяет разным async-рантаймам (tokio, async-std) быть взаимозаменяемыми

Haskell Typeclasses

В 1989 году авторы Haskell столкнулись с задачей: функция `(+)` должна работать для `Int`, `Float` и `Double`, но статическая типизация не позволяет написать один тип без потери точности. Решением стали **типы-классы** - механизм ad-hoc полиморфизма, где класс описывает интерфейс, а экземпляр (`instance`) реализует его для конкретного типа. Это не классы ООП: типы-классы - это набор сигнатур функций, которые тип обязуется реализовать.

Ключевое отличие от интерфейсов ООП: экземпляр типа-класса определяется **отдельно** от самого типа. Можно добавить новый тип-класс к уже существующему типу, даже если этот тип определён в другой библиотеке - главное соблюдать правила когерентности.

Класс `Functor` определён как `class Functor f where { fmap :: (a -> b) -> f a -> f b }`. Что означает ограничение `Functor f` в сигнатуре функции?

Rust Traits

Rust взял идею типов-классов и встроил её в систему владения. **Трейт** - это набор методов (и ассоциированных типов), которые тип обязуется реализовать. В отличие от Haskell, где типы-классы влияют только на типизацию, трейты Rust участвуют в разрешении заимствований и лайфтаймов. Трейт-объекты (`dyn Trait`) дают динамическую диспетчеризацию; `impl Trait` в позиции возврата - статическую без раскрытия конкретного типа.

Трейты в Rust бывают трёх видов по диспетчеризации: **статическая** (monomorphization через generics - нулевая цена во время выполнения), **динамическая** (`dyn Trait` - vtable, разыменование указателя) и **impl Trait** (статическая без экспозиции типа, полезно для возврата замыканий).

В чём принципиальная разница между `fn f<T: Display>(x: T)` и `fn f(x: &dyn Display)` в Rust?

Coherence

**Когерентность** - гарантия, что для любой пары (тип, трейт/класс) существует не более одного экземпляра. Без этой гарантии код `show (1 :: Int)` мог бы давать разные результаты в зависимости от порядка импорта модулей - катастрофа для статической типизации. Haskell и Rust вводят жёсткие правила, ограничивающие, где можно определять экземпляры, ради сохранения этой инварианты.

Нарушение когерентности называется **overlapping instances** (Haskell) или **conflicting implementations** (Rust). В Haskell существуют расширения `OverlappingInstances` и `IncoherentInstances`, но их использование считается опасным - они нарушают предсказуемость вывода типов.

Почему в Haskell нельзя одновременно иметь два экземпляра `Show Int` в одной программе?

Orphan Rules

**Правило сирот** (orphan rule): экземпляр трейта/класса можно определить только в том модуле, где определён **либо тип, либо трейт**. Если кто-то напишет `impl Display for Vec<i32>` в своём крейте - компилятор откажет, потому что `Display` из `std::fmt` и `Vec` из `std::vec` - оба чужие. Экземпляр называется 'сиротой', если он не принадлежит ни одному из двух домов.

Обход orphan rule в Rust - паттерн **newtype**: `struct Wrapper(Vec<i32>)`. Это собственный тип, поэтому `impl Display for Wrapper` законно. Цена: необходимость разворачивать обёртку через `.0` или реализовывать `Deref`.

Трейты Rust и типы-классы Haskell - это просто интерфейсы, как в Java или C#

Ключевое отличие: экземпляр определяется отдельно от типа и может быть добавлен постфактум. В Java интерфейс нужно указать при объявлении класса - ретроактивное расширение невозможно без изменения исходного кода.

Именно ретроактивность делает типы-классы мощнее интерфейсов ООП: можно добавить новый трейт к чужому типу (соблюдая orphan rule) без доступа к его исходному коду.

Крейт `my_crate` хочет реализовать трейт `serde::Serialize` (из крейта `serde`) для типа `chrono::DateTime` (из крейта `chrono`). Что произойдёт?

Ключевые идеи

  • **Типы-классы / трейты** - механизм ad-hoc полиморфизма: одно имя функции, разные реализации для разных типов, выбор на этапе компиляции
  • **Когерентность** гарантирует уникальность экземпляра для пары (тип, трейт) - это делает вывод типов детерминированным и предсказуемым
  • **Orphan rule** запрещает определять экземпляр вне модуля типа или трейта - обход через паттерн newtype

Связанные темы

Типы-классы и трейты - фундамент для более продвинутых механизмов типизации:

  • Алгебраические типы данных — ADT + типы-классы = выразительность без наследования; типы-классы описывают поведение, ADT - структуру
  • Зависимые типы — Некоторые языки (Idris, Lean) реализуют интерфейсы через зависимые типы, что ещё мощнее типов-классов

Вопросы для размышления

  • Почему паттерн newtype в Rust - это вынужденная мера обхода orphan rule, а не плохой дизайн?
  • Если убрать правило когерентности из Haskell, что конкретно сломается в выводе типов?
  • Чем ретроактивное расширение типов через трейты принципиально отличается от monkey-patching в Ruby или JavaScript?

Связанные уроки

  • plt-07-algebraic-types — Most typeclasses are instantiated over ADTs; need to know the shapes before defining behavior on them
  • plt-08-generics — Higher-kinded types enable Functor/Monad; generics are a prerequisite for HKT
  • plt-12-subtyping — Typeclasses (ad-hoc polymorphism) vs subtype polymorphism are two competing models for polymorphic dispatch
  • plt-19-oop-theory — OOP interfaces vs Haskell typeclasses - same goal, different semantics and expressiveness
  • ct-02
Типы-классы и трейты

0

1

Войти