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

Предисловие

Когда я начал изучать Хаскель, я был почти сразу поражён. Для начала, нырнув с головой в актуальные рабочие проекты, открыл, что большинство настоящих библиотек используют языковые расширения, присутствующие только в 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 

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

{-# LANGUAGE TypeFamilies, MultiParamTypeClasses, FlexibleContexts #-} class (Show pokemon, Show (Move pokemon)) => Pokemon pokemon where   data Move pokemon :: *   pickMove :: pokemon -> Move pokemon  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  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"  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  instance Battle Grass Water where   pickWinner pokemon foe = pokemon  instance Battle Water Grass where   type Winner Water Grass = Grass   pickWinner = flip pickWinner  instance Battle Fire Grass where   pickWinner pokemon foe = pokemon  instance Battle Grass Fire where   type Winner Grass Fire = Fire   pickWinner = flip pickWinner      main :: IO () main = do   battle Squirtle Charmander   battle Charmeleon Wartortle   battle Bulbasaur Blastoise   battle Wartortle Ivysaur   battle Charmeleon Ivysaur   battle Venusaur Charizard 

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

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