Семьи типов и Покемоны

Предисловие

Когда я начал изучать Хаскель, я был почти сразу поражён. Для начала, нырнув с головой в актуальные рабочие проекты, открыл, что большинство настоящих библиотек используют языковые расширения, присутствующие только в GHC (Glasgow Haskell Compiler). Это меня покоробило слегка, прежде всего потому, кто захочет использовать язык настолько немощный, что будет необходимо использовать расширения, присутствующие лишь у одного поставщика. Ведь так?
Хорошо, я решился снова это осилить и узнать всё об этих расширениях, и я вывел три горячих топика для общества Хаскеля, которые решали похожие проблемы: Обобщённые Алгебраические Типы Данных, Семьи Типов и Функциональные Зависимости. Пытаясь найти ресурсы, которые обучают о них, я смог найти только статьи, описывающие, что это такое, и как их использовать. Но никто, на самом деле, не объяснял зачем они нужны!.. Поэтому я решил написать эту статью, используя дружественный пример, пытаясь объяснить зачем всё-таки нужны Семьи Типов.



Вы когда-нибудь слышали про Покемонов? Это замечательные существа, которые населяют Мир Покемонов. Вы можете считать, что они как животные с экстраординарными способностями. Все покемоны владеют стихией, и все их возможности зависят от этой стихии. Например, покемон Огненной стихии может дышать огнём, в то время как покемон Водной стихии может брызгать струями воды.
Покемоны принадлежат людям, и их специальные способности могут быть использованы во благо для продуктивной деятельности, но некоторые люди всего лишь используют своих покемонов для борьбы с другими покемонами других людей. Эти люди называют себя Тренерами Покемонов. Это может сначала звучать как жестокое обращение с животными, но это очень даже весело и все, похоже, рады, включая покемонов. Имейте в виду, что в мире покемонов, кажется, всё в порядке, даже если 10-летние покидают дом, дабы рисковать своими жизнями ради того, чтобы стать самыми лучшими Тренерами Покемонов, как будто никто и никогда таковыми не становился.

Мы собираемся использовать Хаскель для того, что бы представить ограниченную (и даже несколько упрощённую, да простят меня фанаты) часть мира покемонов. А именно:

• Покемон имеет тип или стихию, в нашем случае урезанную до Огня, Воды и Травы
• Существуют три покемона каждой стихии:
  
  • Чармандер, Чармелион и Чаризард — Огненные покемоны,
  • Сквиртл, Вартортл и Блестойз — Водной стихии,
  • Бульбазавр, Ивизавр и Венозавр — Травяной стихии
• Каждая стихия имеет свои собственные способности, называемые движениями или ударами: водные покемоны выполняют водные удары, огненные покемоны — огненные удары, травяные — травяные удары
• Когда бьются, огненный покемон всегда побеждает травяного покемона, травяной покемон всегда побеждает водного покемона, а водный покемон всегда побеждает огненного покемона
• Никогда не дерутся покемоны одной стихии, поскольку нельзя определить, кто из них выиграет
• Другие люди должны быть способны пополнять программу своими покемонами в своих модулях
• Проверщик Типов (часть интерпретатора и компилятора) должен помочь нам в соблюдении правил

Первая попытка

Для начала попытаемся реализовать правила без использования классов типов и семей типов.
Начнём с нескольких стихий покемонов и их движений. Мы будем реализовывать отдельно, поскольку это поможет нам отличить их движения от типов покемонов.
Для этой цели мы определим функции для каждого покемона, выбрав его движение.

data Fire = Charmander | Charmeleon | Charizard deriving Show 
data Water = Squirtle | Wartortle | Blastoise deriving Show
data Grass = Bulbasaur | Ivysaur | Venusaur deriving Show

data FireMove = Ember | FlameThrower | FireBlast deriving Show 
data WaterMove = Bubble | WaterGun deriving Show
data GrassMove = VineWhip deriving Show

pickFireMove :: Fire -> FireMove
pickFireMove Charmander = Ember
pickFireMove Charmeleon = FlameThrower
pickFireMove Charizard = FireBlast

pickWaterMove :: Water -> WaterMove
pickWaterMove Squirtle = Bubble
pickWaterMove _ = WaterGun

pickGrassMove :: Grass -> GrassMove
pickGrassMove _ = VineWhip

Пока всё хорошо, проверщик типов помогает разобраться, где какой покемон правильно использует свою стихию.


6 из описываемых нами 9 покемонов всех трёх стихий. По 2 на каждый тип

Теперь мы должны реализовать бой. Бои будут представлять собой вывод сообщения, где описано как каждый покемон бьёт, затем указываем победителя, например, так:

printBattle :: String -> String -> String -> String -> String -> IO ()
printBattle pokemonOne moveOne pokemonTwo moveTwo winner = do
  putStrLn $ pokemonOne ++ " used " ++ moveOne
  putStrLn $ pokemonTwo ++ " used " ++ moveTwo
  putStrLn $ "Winner is: " ++ winner ++ "\n"

Это всего лишь отображение движений, мы сами должны найти победителя, на основании стихии покемона и его ударов. Вот пример функции боя между Огненной и Водной стихиями:

battleWaterVsFire :: Water -> Fire -> IO ()
battleWaterVsFire water fire = do
  printBattle (show water) moveOne (show fire) moveTwo (show water)
 where
  moveOne = show $ pickWaterMove water
  moveTwo = show $ pickFireMove fire

battleFireVsWater = flip battleWaterVsFire -- То же самое, что и выше, только с аргументами, которых поменяли местами

Если всё это объединим, и допишем другие функции драк, мы получим программу.

Введение в Классы типов

Сколько в этом повторенного кода: представьте себе, что кто-то захотел добавить Электрической стихии покемонов, например Пикачу, тогда придётся дописывать собственные функции драк battleElectricVs(Grass|Fire|Water). Есть несколько шаблонов, которые помогут нам формализовать и помочь людям получить большее понимание, что такое покемоны и как добавлять новые.
Что мы имеем:

• покемоны используют функции, чтобы выбрать движение
• Битвы находят победителя и печатают описание битвы

Мы определим несколько классов типов для формализации, и раз мы будем править, мы так же переименуем необычную ныне схему имён, где каждая функция включает стихию, с которой оперирует.

Класс покемонов

Класс покемонов отображает знания, что покемон выбрал своё движение. Это позволит нам определить pickMove, пере-используя так, что одна и та же функция может оперировать разными стихиями, для которых определён класс.

В отличие от «ванильных» классов, наш класс покемонов будет нуждаться в 2х типах: стихии покемона и типа урона им используемым, а позже одно будет зависеть от другого. Мы должны включить языковое расширение, разрешающее иметь 2 параметра в классе: MultiParamTypeClasses
Заметьте, что мы должны добавить ограничения, такие, что покемоны и их удары должны иметь возможность быть выведенными на экран.
Вот определение, наряду с несколькими экземплярами для существующих стихий покемонов.

class (Show pokemon, Show move) => Pokemon pokemon move where
  pickMove :: pokemon -> move

instance Pokemon Fire FireMove where
  pickMove Charmander = Ember
  pickMove Charmeleon = FlameThrower
  pickMove Charizard = FireBlast

instance Pokemon Water WaterMove where
  pickMove Squirtle = Bubble
  pickMove _ = WaterGun

instance Pokemon Grass GrassMove where
  pickMove _ = VineWhip

и сможем использовать функцию так

pickMove Charmander :: FireMove

Заметьте, как вещи начинают выглядеть неопрятно. Из-за того, что стихии покемонов и типы движения обрабатываются независимо классами типов. Говоря, что мы выбираем Огненный удар, мы даём проверщику типов всю информацию, для того, что бы он решил, какой использовать класс и удар.

Класс битвы

У нас уже есть покемоны, которые могут выбирать себе удары, теперь нам необходима абстракция, которая будет представлять битву двух покемонов, для того, что бы избавиться от функций типа battle*family*Vs*family
Нам бы очень хотелось написать код так:

class (Pokemon pokemon move, Pokemon foe foeMove) => Battle pokemon move foe foeMove where
  battle :: pokemon -> foe -> IO ()
  battle pokemon foe = do
    printBattle (show pokemon) (show move) (show foe) (show foeMove) (show pokemon)
   where
    move = pickMove pokemon
    foeMove = pickMove foe

instance Battle Water WaterMove Fire FireMove

Однако, если мы запустим, получим ошибку от проверщика типов, поскольку нет более общего экземпляра с учётом всех типов ударов.
Эта проблема решаема, однако, итоговый код выглядит некрасивым, нам фактически необходимо изменить тип функции битвы на

battle :: pokemon -> foe -> IO (move, foeMove)

Введение Семей типов, наконец-то!

Ну вот, наша программа выглядит удручающе. Мы должны заботится обо всех подписях типов, и мы даже обязаны изменять внутреннее поведение наших функций (battle) только для того, чтобы мы могли использовать подписи типов для того, дабы помочь компилятору. Я могу пойти значительно дальше и сказать, что наш нынешний рефакторинг программы — лишь чуть более формальный и менее повторяемый, не настолько уж и большое достижение, после того, как мы ввели столько безобразия в код.
Теперь мы можем оглянутся назад, на наше определение класса Покемон. Он имеет стихию покемонов и тип ударов как два отдельных переменных класса. Проверщик типов не знает о существовании связи между стихиями покемонов и типами ударов. Он даже позволяет определить экземпляр Покемонов, когда Водный покемон создаёт Огненные удары!
Именно тут семьи типов вступают в игру: они позволяют сказать проверщику типов, что Огненный покемон может работать только с Огненными ударами и так далее.

Класс Покемон, используя семьи типов

Для того, что бы использовать Семьи типов нам необходимо включить расширение TypeFamilies. Как только мы подключим, мы сможем попробовать написать наш класс в стиле:

{-# LANGUAGE TypeFamilies, FlexibleContexts #-}
class (Show p, Show (Move p)) => Pokemon p where
  data Move p :: *
  pickMove :: p -> Move p

Мы определили наш класс Покемон таким образом, что он имеет один аргумент и один ассоциированный тип Движения. Тип Движения становится «функцией типа», возвращающей тип удара, который будет использован. Это означает, что мы будем вместо FireMove использовать Move Fire, вместо WaterMove — Move Water и т.д.
Заметим, что зависимость выглядит почти как в предыдущем случае, только вместо Show move мы используем Show (Move a)). Нам необходимо включить ещё одно дополнение: FlexibleContexts, что бы работать с этим.
Теперь Хаскель обеспечивает нас отличным синтаксическим сахаром, поэтому мы можем определить актуальный ассоциированный конструктор данных справа, когда мы определяем наш экземпляр.
Давайте переопределим все наши типы данных и создадим необходимые экземпляры класса, используя семьи типов.

data Fire = Charmander | Charmeleon | Charizard deriving Show
instance Pokemon Fire where
  data Move Fire = Ember | FlameThrower | FireBlast deriving Show
  pickMove Charmander = Ember
  pickMove Charmeleon = FlameThrower
  pickMove Charizard = FireBlast

data Water = Squirtle | Wartortle | Blastoise deriving Show
instance Pokemon Water where
  data Move Water = Bubble | WaterGun deriving Show
  pickMove Squirtle = Bubble
  pickMove _ = WaterGun

data Grass = Bulbasaur | Ivysaur | Venusaur deriving Show
instance Pokemon Grass where
  data Move Grass = VineWhip deriving Show
  pickMove _ = VineWhip

Теперь мы можем спокойно писать

pickMove Squirtle

и получить результат.
Это красиво, правда же? Нет больше необходимости писать подписи, для того, чтобы выбрать удар.
Однако ещё рано сравнивать с начальным вариантом. Лучше сравнить финальный результат, чтобы получить полный эффект от увиденного.

Новый класс Битвы

Теперь уже нет необходимости в длинной подписи, поэтому можно убрать отвратительный костыль, и вернуть почти первоначальное значение.

class (Pokemon pokemon, Pokemon foe) => Battle pokemon foe where
  battle :: pokemon -> foe -> IO ()
  battle pokemon foe = do
    printBattle (show pokemon) (show move) (show foe) (show foeMove) (show pokemon)
   where
    foeMove = pickMove foe
    move = pickMove pokemon

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

instance Battle Water Fire
instance Battle Fire Water where
  battle = flip battle

instance Battle Grass Water
instance Battle Water Grass where
  battle = flip battle

instance Battle Fire Grass
instance Battle Grass Fire where
  battle = flip battle

Использовние тоже просто:

  battle Squirtle Charmander

Это всё! Наша программа наконец приобрела отличный вид, мы улучшили её, и проверщик типов проверяет больше, меньше повторяем и имеем чистую API для того, что бы предлагать её другим разработчикам.

Классно! Мы сделали это! Надеюсь, вам понравилось!
Ладно-ладно. Я понял, что вам весело и вы не можете поверить, что всё уже закончилось, потому что ваш скролбар в браузере показывает, что ещё есть место пониже этой фразы.

Что же, давайте добавим ещё одну вещь в Мир Покемонов.
Сейчас мы определили наши экземпляры Битвы для стихий Water и Fire как Battle Water Fire, и затем Battle Water Fire таким же самым как и предыдущий, с аргументами поменянными местами. Первый покемон всегда выигрывает, и выводится всегда следующее:

-- Winner Pokemon move
-- Loser Pokemon move
-- Winner pokemon Wins.

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

-- Loser Pokemon move
-- Winner Pokemon move
-- Winner pokemon Wins

Ассоциированные Синонимы типов

Когда мы решаем возвращать выбор двух типов, мы обычно используем Either a b, но это в ран-тайме, мы же хотим, что бы проверщик типов был уверен, что когда будут драться стихии Огонь и Вода, Вода будет всегда победителем.
Поэтому мы добавим новую функцию в Битву и назовём её победитель, которая будет получать 2 аргумента в том же самом прядке, которые были получены функцией битвы, и решим кто будет выигрывать.
Однако возвращать одно из нескольких вариантов вызывает неопределённость выбора подписи у победителя.

class Battle pokemon foe where
..
winner :: pokemon -> foe -> ??? -- Так что же, 'pokemon' или 'foe'?

instance Battle Water Fire where
  winner :: Water -> Fire -> Water -- Water первая переменная класса : pokemon
  winner water _ = water

instance Battle Fire Water where
  winner :: Fire -> Water -> Water -- Water вторая переменная класса: foe
  winner _ water = water

Видите, для Battle Water Fire экземпляра возвращается тип победителя такого же, как и pokemon, а у Battle Fire Water это уже будет foe.

К счастью, семьи типов так же поддерживают ассоциированные синонимы типов. В классе Битвы мы будет иметь Winner pokemon foo, а в экземплярах будем определять, кто же из них им будет. Мы используем тип, а не данные, потому что это всего лишь синоним pokemon или foe.
Самостоятельно Winner является функцией типа с подписью видов * -> * -> *, которая получает обоих pokemon и foo, и возвращает одного из них.
Мы так же определим реализацию по умолчанию, которая будет выбирать pokemon

class (Show (Winner pokemon foe), Pokemon pokemon, Pokemon foe) => Battle pokemon foe where
  type Winner pokemon foe :: *      -- это ассоцированный тип
  type Winner pokemon foe = pokemon -- это его имплементация по умолчанию

  battle :: pokemon -> foe -> IO ()
  battle pokemon foe = do
    printBattle (show pokemon) (show move) (show foe) (show foeMove) (show winner)
   where
    foeMove = pickMove foe
    move = pickMove pokemon
    winner = pickWinner pokemon foe
  
  pickWinner :: pokemon -> foe -> (Winner pokemon foe)

Экземпляры создаются так:

instance Battle Water Fire where
  pickWinner pokemon foe = pokemon

instance Battle Fire Water where
  type Winner Fire Water = Water
  pickWinner = flip pickWinner

Теперь уж точно всё.
Окончательный вариант программы таков:

Теперь можно своего Электрического покемона очень просто добавить! Попробуйте!

P.S. Оригинал статьи Type Families and Pokemon
Статья печатается с сокращениями, поскольку предназначена для интерактивного взаимодействия.