Type Family and Pokemon

Foreword

When I began to study Haskel, I was almost immediately amazed. To begin with, diving headlong into current work projects, discovered that most of these libraries use language extensions that are present only in the GHC (Glasgow Haskell Compiler). It jarred me slightly, primarily because someone who wants to use a language so weak that it will be necessary to use extensions that are present only from one supplier. It is so?
Well, I decided to master it again and learn all about these extensions, and I derived three hot topics for the Haskell society that solved similar problems: Generalized Algebraic Data Types, Type Families and Functional Dependencies. Trying to find resources that teach about them, I could only find articles describing what it is and how to use it. But no one, in fact, explained why they are needed! .. Therefore, I decided to write this article using a friendly example, trying to explain why the Type Types are still needed.



Have you ever heard of Pokemon? These are wonderful creatures that inhabit the World of Pokemon. You can consider them as animals with extraordinary abilities. All Pokemons own the element, and all their capabilities depend on this element. For example, the fire element pokemon can breathe fire, while the water element pokemon can splash water.
Pokemon belong to people, and their special abilities can be used to benefit productive activities, but some people just use their Pokemon to fight other Pokemon of other people. These people call themselves Pokemon Trainers. It may sound like animal abuse at first, but it's very fun and everyone seems happy, including Pokemon. Keep in mind that in the Pokémon world, everything seems to be in order, even if 10-year-olds leave home to risk their lives in order to become the best Pokémon Trainers, as if no one ever became one.
')
We are going to use Haskell to present a limited (and even somewhat simplified, forgive me fans) part of the world of pokemon. Namely:

• Pokemon has a type or element, in our case, stripped down to Fire, Water and Grass
• There are three pokemon each element:
  
  • Charmander, Charmeleon and Charizard - Fire Pokemon,
  • Squirtle, Warthortle and Blestoyz - Water Element,
  • Bulbasaurus, Ivizavr and Venozavr - Grass Element
• Each element has its own abilities, called movements or strikes: water Pokémon perform water strikes, fire Pokémon - fire strikes, herbal - grass blows
• When fighting, a fire pokemon always defeats a grass pokemon, a grass pokemon always defeats a water pokemon, and a water pokemon always defeats a fire pokemon
• Pokemons of one element never fight, because it is impossible to determine which one will win
• Other people should be able to replenish the program with their pokemon in their modules.
• The Type Checker (part of the interpreter and compiler) should help us in complying with the rules.

First try

To begin with, we will try to implement the rules without using type classes and type families.
Let's start with a few pokemon elements and their movements. We will implement separately, as this will help us to distinguish their movements from Pokemon types.
For this purpose, we will determine the functions for each pokemon, choosing its movement.

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 

While all is well, the type-checker helps to figure out where some pokemon use their element correctly.


6 of 9 pokémon of all three elements described by us. 2 for each type

Now we have to realize the battle. Fights will be a message output, where it is described how each Pokemon beats, then we indicate the winner, for example, like this:

 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" 

This is just a display of movements, we ourselves must find the winner, based on the elements of the pokemon and his blows. Here is an example of the function of the battle between the Fire and Water elements:

 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 --   ,   ,   ,    

If we combine all this and add other functions of the fights, we will get the program.

Introduction to Type Classes

How much of this is repeated code: imagine that someone wanted to add Pokemon Electric Elements, for example Pikachu, then you have to add your own functions of battleElectricVs(Grass|Fire|Water) . There are several templates that will help us to formalize and help people gain a greater understanding of what Pokemon is and how to add new ones.
What we have:

• pokemons use functions to select movement
• Battles find a winner and print a description of the battle.

We will define several types of types for formalization, and since we will rule, we will also rename the now unusual name scheme, where each function includes the element with which it operates.

Pokemon class

The Pokémon class displays knowledge that the Pokémon has chosen its movement. This will allow us to define pickMove , re-using it so that the same function can operate on different elements for which the class is defined.

In contrast to the “vanilla” classes, our Pokemon class will need 2 types: the elements of the Pokemon and the type of damage they use, and later one will depend on the other. We need to enable a language extension that allows 2 parameters in the class: MultiParamTypeClasses
Notice that we need to add constraints, such that Pokemon and their strikes should be able to be displayed on the screen.
Here is the definition, along with several instances for existing Pokemon elements.

 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 

and we can use the function like this

 pickMove Charmander :: FireMove 

Notice how things start to look untidy. Due to the fact that pokemon elements and movement types are processed independently by type classes. Saying that we choose the Fire Strike, we give the type inspector all the information so that he would decide which class to use and the blow.

Battle class

We already have Pokemon who can choose their own blows, now we need an abstraction that will represent the battle of two Pokemons in order to get rid of functions like battle*family*Vs*family
We would really like to write code like this:

 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 

However, if we start, we will get an error from the type checker, since there is no more general instance taking into account all types of impacts.
This problem is solved, however, the final code looks ugly, we actually need to change the type of the battle function to

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

Introduction Families of types, finally!

Well, our program looks depressing. We need to take care of all the type signatures, and we are even obliged to change the internal behavior of our functions ( battle ) only so that we can use type signatures in order to help the compiler. I can go much further and say that our current program refactoring is only slightly more formal and less repetitive, not so much a great achievement, after we have entered so much disgrace in the code.
Now we can look back at our definition of the Pokémon class. He has the pokemon element and the type of strikes as two separate class variables. The type checker does not know about the existence of a connection between the elements of Pokemon and the types of impacts. It even allows you to identify a Pokémon instance when Water Pokemon creates Fire Strikes!
It is here that the family of types comes into play: they allow the type-tester to say that the Fire Pokemon can only work with Fire Strikes and so on.

Pokemon class using family types

In order to use Family Types, we need to enable the TypeFamilies extension. As soon as we connect, we can try to write our class in style:

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

We have defined our Pokemon class in such a way that it has one argument and one associated type of movement. Movement type becomes a “type function” that returns the type of impact to be used. This means that instead of FireMove we will use Move Fire , instead of WaterMove - Move Water , etc.
Note that the dependency looks almost like in the previous case, only instead of Show move we use Show (Move a)) . We need to include another addition: FlexibleContexts , to work with this.
Now Haskel provides us with excellent syntactic sugar, so we can determine the actual associated data constructor on the right when we define our instance.
Let's redefine all our data types and create the necessary class instances using the type families.

 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 

Now we can calmly write

 pickMove Squirtle 

and get the result.
It's beautiful, right? No more need to write captions in order to choose a punch.
However, it is too early to compare with the initial version. It is better to compare the final result to get the full effect of what you see.

New Class Battle

Now there is no longer a need for a long signature, so you can remove the hideous crutch, and return almost the original value.

 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 

And note, now the Battle is no longer necessary to know anything about the attacks. And the fighting pokemons look almost the same as the naive implementation.

 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 

Using is also easy:

  battle Squirtle Charmander 

It's all! Our program finally got a great look, we improved it, and the type checker checks more, repeats less and has a clean API to offer it to other developers.

Cool! We did it! Hope you enjoyed it!
OK OK. I realized that you are having fun and you can’t believe that everything is already over, because your browser scrolling bar shows that there is still room for less than this phrase.

Well, let's add one more thing to the World of Pokemon.
Now we have defined our instances of the Water and Fire elements as Battle Water Fire , and then the Battle Water Fire is the same as the previous one, with the arguments reversed. The first pokemon always wins, and the following is always displayed:

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

Even when an instance has a loser first, the attacker of the winner will be displayed first.
Let's replace it all the same, and let the copies decide who wins the fight, and we can get

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

Associated Type Synonyms

When we decide to return the choice of two types, we usually use Either ab , but it is in the runtime, we want the type checker to be sure that when the elements Fire and Water will fight, Water will always be a winner.
Therefore, we will add a new function to the Battle and call it a winner , which will receive 2 arguments in the same order that were obtained by the battle function, and decide who will win.
However, to return one of several options causes the uncertainty of the choice of signature from the winner.

 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 

You see, for the Battle Water Fire instance, the winner type is the same as the pokemon , and the Battle Fire Water will already have a foe .

Fortunately, type families also support associated type synonyms. In the class of the Battle, we will have Winner pokemon foo , and in the instances we will determine who among them will be. We use the type, not the data, because it is just a synonym for pokemon or foe .
On its own, Winner is a type-signed type function * -> * -> * that receives both pokemon and foo and returns one of them.
We will also define a default implementation that pokemon will choose 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) 

Instances are created like this:

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

Now that's for sure.
The final version of the program is as follows:

Now you can add your own Electric Pokemon! Try it!

PS Original article Type Families and Pokemon
The article is printed with abbreviations, as it is intended for interactive interaction.