# Polymorphy and classes in Haskell

Hello dear reader!

Today we’ll talk about the polymorphism of functions and about classes in the Haskell language, how to use them and why they are needed. We all used the polymorphism method, for example, in the Java language. How can this be applied to Haskell? Haskell is not an object-oriented language, but it still has classes. Although classes in Haskell have some properties of classes of object-oriented languages, they are more abstracted from this and much more powerful. Drawing an analogy with the Java language further, classes in Haskell are nothing more than interfaces — only function declarations are written to the class, and implementations of these functions themselves will be made later.

I would like to thank the user Darkus for reading and correcting all the flaws and inaccuracies in the article, as well as for good advice and help in writing.

In Haskell, there are two types of polymorphism - parametric and special (in English they call the term “ad hoc”, which came from the Latin language).

If you have ever programmed in the Haskell language, you have certainly come across examples of parametric polymorphism in functions

In the first three functions of the input parameter type

A is also used here - an unknown data type that will be determined at compile time. Polymorphism is used when it is not known what type of data the parameter will be, but the operations that will be performed on it (ilm with it) are known.

All identifiers of typical variables in the Haskell language must begin with a capital letter (for example

The parameter

The type of function in the GHCi interpreter (and in Hugs) can always be found using the command

A synonym for special polymorphism is the term “overloaded functions”. This is a weaker type of polymorphism than parametric. Take for example the addition operator (function) (+). Expressions of this kind

differ from expressions

in that in the first case, numerical values were used, and in the second, values of type Bool and [Int]. The addition operator is not defined for non-numeric types. This is because this function has a type not

like this

The restriction that is imposed on type

The following binary tree types are given: A

binary tree that can store any type of data

A binary tree that can store two elements, and each branch ends with a “leaf” with one element (and not Nil):

A binary tree that can store data of type String and also ends with a sheet:

And, let's say, there are two more kinds of lists:

regular

and type “rope”

Having all these data structures, I would like to write a function

Now, if any other data structure appears, you will have to make a new function that will be suitable

It remains only to make instances (instances) of this class for specific values

Done! Now if we write in GHCi

Each instance of the class

But there are also disadvantages to such a decision. For example, we would like to know the number of elements in a paired list, i.e.

It would be obvious to do the following:

But here we have a problem, because we already have an instance for the usual list (

Now a little more about classes.

In the previous example, we passed the class

Incomplete because restrictions can also be imposed on the class declaration

Type classes are collections of types for which special functions are defined. Here are some (one of the most important) classes in Haskell:

Only these classes can be automatically inherited by any type of data (= put in a section

Let's look at the equivalence class in

The code shows that for any instance of the Eq class, it is enough to implement one of two functions. For example, for the Bool type (two types are equal only when they are both True or False) this is done as follows:

As you can see, the case True False and False True (as well as the last line) is not necessary to write, because inequality is the inverse of equality. If before that we had the case that the type is a cokretization of another

For

Everything to the left of the symbol

Equality (==) is a type-dependent property that requires implementation for each type (such as the implementation of equality of binary trees). I would like to be able to compare two functions in this way:

This would require writing such code in Haskell:

Is it possible to write such a function that would yield the result of the equality of

Instead of implementing its function for equality, for example, binary trees, you can always put those classes that are inherited by this type automatically after the keyword

This allows us not to write an instance of the class Eq (

The following function will be implemented (automatically):

As we can see, the first argument of Node3 was omitted, which we would not want in some cases.

The informal difference between the two types of polymorphy:

Today we’ll talk about the polymorphism of functions and about classes in the Haskell language, how to use them and why they are needed. We all used the polymorphism method, for example, in the Java language. How can this be applied to Haskell? Haskell is not an object-oriented language, but it still has classes. Although classes in Haskell have some properties of classes of object-oriented languages, they are more abstracted from this and much more powerful. Drawing an analogy with the Java language further, classes in Haskell are nothing more than interfaces — only function declarations are written to the class, and implementations of these functions themselves will be made later.

I would like to thank the user Darkus for reading and correcting all the flaws and inaccuracies in the article, as well as for good advice and help in writing.

### Function Polymorphism

In Haskell, there are two types of polymorphism - parametric and special (in English they call the term “ad hoc”, which came from the Latin language).

#### Parametric

If you have ever programmed in the Haskell language, you have certainly come across examples of parametric polymorphism in functions

`length, head, teal, curry, uncurry, map, filter, ...`

. What unites all these functions? Let's look at the implementation of some of them:```
length :: [a] -> Int
length [] = []
length (_:xs) = 1 + length xs
head :: [a] -> a
head (x:_) = x
tail :: [a] -> [a]
tail (_:xs) = xs
curry :: ((a,b) -> c) -> (a -> b -> c)
curry f x y = f (x,y)
uncurry :: (a -> b -> c) -> ((a,b) -> c)
uncurry g (x,y) = g x y
```

In the first three functions of the input parameter type

`a`

, and have `curry`

and `uncurry`

still `b`

and `c`

. Instead of a specific data type ( `Int, Bool, Char,`

...), typing is used. Java example:`public class Test {...}`

A is also used here - an unknown data type that will be determined at compile time. Polymorphism is used when it is not known what type of data the parameter will be, but the operations that will be performed on it (ilm with it) are known.

All identifiers of typical variables in the Haskell language must begin with a capital letter (for example

`a, abc, aA101`

), and all specific types (constructors) begin with a capital letter (for example `String, Int, Node`

). The parameter

`a`

can accept any types, be it Int, String or even functions (for example `length [f, g, h]`

, where f, g, h are functions that have the same types). It is worth noting that the type `b`

can also accept any types, including the type of the parameter `a`

.The type of function in the GHCi interpreter (and in Hugs) can always be found using the command

`:t`

, for example:```
Main>:t length
length :: [a] -> Int
```

#### Special (ad hoc)

A synonym for special polymorphism is the term “overloaded functions”. This is a weaker type of polymorphism than parametric. Take for example the addition operator (function) (+). Expressions of this kind

`(+) 2 3 ->> 5`

`(+) 2.5 3.85 ->> 6.35`

differ from expressions

` (+) True False`

`(+) [1,2,3] [3,2,1]`

in that in the first case, numerical values were used, and in the second, values of type Bool and [Int]. The addition operator is not defined for non-numeric types. This is because this function has a type not

`(+) :: a -> a -> a`

like this

`(+) :: Num a => a -> a -> a`

. That is, there is a restriction on the type of input (and output) data. The restriction that is imposed on type

`a`

: Num a says that type`a`

must be an element of class Num. Such type classes are very important in Haskell, as they add additional protection against programming errors, and can also reduce the amount of code written at times. We will see this in the following example. The following binary tree types are given: A

binary tree that can store any type of data

`data Tree1 a = Nil | Node1 a (Tree1 a) (Tree1 a)`

A binary tree that can store two elements, and each branch ends with a “leaf” with one element (and not Nil):

`data Tree2 a b = Leaf2 b | Node2 a b (Tree2 a b) (Tree2 a b)`

A binary tree that can store data of type String and also ends with a sheet:

`data Tree3 = Leaf3 String | Node3 String Tree3 Tree3`

And, let's say, there are two more kinds of lists:

regular

`type Lst a = [a]`

and type “rope”

`data Rope a b = Nil | Twisted b (Rope b a)`

Having all these data structures, I would like to write a function

`size`

that, regardless of the data structure, would display either its depth (for trees), or length (for lists), or in a word - size. A naive solution would be to write a function for everyone:**Hidden text**

```
sizeT1 :: Tree1 a -> Int --считаем кол-во узлов
sizeT1 Nil = 0
sizeT1 (Node1 _ l r) = 1 + sizeT1 l + sizeT1 r
sizeT2 :: (Tree2 a b) -> Int --считаем кол-во элементов
sizeT2 (Leaf 2 _) = 1
sizeT2 (Node2 _ _ l r) = 2 + sizeT2 l + sizeT2 r
sizeT3 :: Tree3 -> Int --считаем длины элементов типа String
sizeT3 (Leaf3 m)= length m
sizeT3 (Node m l r) = length m + sizeT3 l +sizeT3 r
-- и для списков:
sizeLst :: [a] -> Int
sizeLst = length
sizeRope :: (Rope a b) -> Int
sizeRope Nil = 0
sizeRope (Twisted _ ls) = 1 + sizeRope ls
```

Now, if any other data structure appears, you will have to make a new function that will be suitable

**only**for this structure. And we would like for one function to get the size of*any*data structure. As the function (+) had a restriction by the Num class, so we need to make the restriction by the Size class, and for this we need to create it first:```
class Size a where
size :: a -> Int
```

It remains only to make instances (instances) of this class for specific values

`a`

(= for specific data types):```
instance Size (Tree1 a) where
size Nil = 0
size (Node1 _ l r) = 1 + size l + size r
instance Size (Tree2 a b) where
size (Leaf2 _) = 1
size (Node2 _ _ l r) = 2 + size l + size r
instance Size Tree3 where
size (Leaf3 m) = length m
size (Node3 m l r) = length m + size l + size r
instance Size [a] where
size = length
instance Size (Rope a b) where
size Nil = 0
size (Twisted _ ls) = 1 + size ls
```

Done! Now if we write in GHCi

`:t size`

, we will see `size :: Size a => a -> Int`

. We got what we wanted:```
size Nil ->> 0
size (Node1 "foo" (Node1 "bar" Nil Nil) Nil) ->> 2
size (Leaf 2 "foo") ->> 1
size (Node3 "foo" (Node3 "bar" (Leaf3 "abc") (Leaf "cba")) (Leaf "tst")) ->> 15 --3*5
size [1..5] ->> 5
size (Rope 2 (Rope ‘a’ (Rope 5 Nil))) ->> 3
```

Each instance of the class

`Size`

implemented a function size, which is applicable only to values of a certain type (= data structures). In this case, this function, like other predefined operators (+), (*), (-), is overloaded. But there are also disadvantages to such a decision. For example, we would like to know the number of elements in a paired list, i.e.

```
size [(1,2), (3,4)] ->> 4
size [('a','b'), ('c','d'), ('e','f')] ->> 6
```

It would be obvious to do the following:

```
instance Size [(a,b)] where
size = (*2) . length
```

But here we have a problem, because we already have an instance for the usual list (

`instance Size [a] where`

), we can no longer use a different definition, because, as mentioned earlier, a type `a`

can be any type, including `(b,c)`

, that is, . `[a] == [(b,c)]`

To solve this problem, you can use Overlapping Instances (English overlapping class instances). This solution has its drawbacks (importing one of the modules can change the value of the program, can cause confusing errors, and so on). Now a little more about classes.

### Classes

In the previous example, we passed the class

`Size`

, but here is the incomplete declaration of the class in Haskell: (tv = type variable):```
class Name tv where
сигнатура включающая переменную tv
```

Incomplete because restrictions can also be imposed on the class declaration

`tv`

(for example, it `tv`

must be an element of the class `Ord`

). The signatures can be as many as you like, but each of them must include (as an input and / or output parameter) the variable tv. Type classes are collections of types for which special functions are defined. Here are some (one of the most important) classes in Haskell:

**Eq**- class for the test for equality (inequality) of two data types (operations ==, / =)**Ord**- a class for determining the type order, that is, which element is larger, which is smaller (operations>,> =, <, <=, min, max ...)**Enum**- a class for types whose values can be "counted" (for example, [1..10])**Bounded**- the class is also used for types of the Enum class. Used to name the lower and upper bounds of a type.**Show**- a class for types whose values can be converted to a string (= can be represented as characters)**Read**- a class for types whose values can be converted from a string

Only these classes can be automatically inherited by any type of data (= put in a section

`deriving`

). There is also a dependency between classes. For example, if we know how to compare two elements (class Ord), then we must be able to determine in advance whether one element is equal to another (class Eq). Indeed, to implement the operator ( `>=`

), you must have an implemented operator (==). Therefore, we can say that the class Ord depends (inherits) from the class Eq. Here is a more detailed diagram of class dependency: Let's look at the equivalence class in

`Eq`

more detail. As previously mentioned, this class must have two functions (==) and (/ =):```
class Eq a where
(==), (/=) :: a -> a -> Bool --так как сигнатуры (==) и (/=) одинаковы, их можно записать в 1 строчку
x /= y = not (x == y)
x == y = not (x /= y)
```

The code shows that for any instance of the Eq class, it is enough to implement one of two functions. For example, for the Bool type (two types are equal only when they are both True or False) this is done as follows:

```
instance Eq Bool where
(==) True True = True
(==) False False = True
(==) _ _ = False
```

As you can see, the case True False and False True (as well as the last line) is not necessary to write, because inequality is the inverse of equality. If before that we had the case that the type is a cokretization of another

**type**(for example, [Int] is an instance of the type [a]), now the type can be an instance of the**class**(for example, Bool is an instance of the Eq class). By the same analogy, we can write the equality functions of those binary trees that we used above. For example, for Tree2:```
instance (Eq a) => Eq (Tree2 a) where --накладываем условие на a, что этот тип может сравниваться
(==) (Leaf2 s) (Leaf2 t) = (s==t)
(==) (Node2 s t1 t2) (Node2 t u1 u2)= (s==t) && (t1 == u1) && (t2 == u2)
(==) _ _ = False
```

For

`(Tree3 a b)`

we will already have to impose a condition on both `a`

, and on `b`

, that is, `instance (Eq a, Eq b) => Eq (Tree3 a b)`

Everything to the left of the symbol

`=>`

is called a context, everything to the right of this symbol must be either a base type (Int, Bool, ...), or type constructors (Tree a, [...], ...). The operator (==) is an overloaded function (ad-hoc polymorphism). Equality (==) is a type-dependent property that requires implementation for each type (such as the implementation of equality of binary trees). I would like to be able to compare two functions in this way:

```
(==) fac fib ->> False --где fac - факториал числа, а fib - число Фибоначчи
(==) (\x -> x+x) (\x -> 2*x) ->> True
(==) (+2) (2+) ->> True
```

This would require writing such code in Haskell:

```
instace Eq (Int -> Int) where
(==) f g = ... --где f и g являются какими-то функциями
```

Is it possible to write such a function that would yield the result of the equality of

**any**two functions (True or False)? Unfortunately, from the Church-Turing thesis it follows that the equality of any two functions cannot be determined. There is no algorithm that, for any two given functions, always and through a finite number of steps, decides whether the two functions are equal or not. Such an algorithm cannot be programmed in any programming language.Instead of implementing its function for equality, for example, binary trees, you can always put those classes that are inherited by this type automatically after the keyword

`deriving`

. That is, we could quite safely write:`data Tree a = Nil | Node a (Tree a) (Tree a) deriving Eq`

This allows us not to write an instance of the class Eq (

`instance Eq a => Eq (Tree a) where ...`

) with our own hands . But for any function, then you have to impose a condition on the variable `a`

that this variable is an element of the class Eq. Sometimes, you still have to write these functions yourself, since the “automatic” comparison does not always work as we would like. For example for a binary tree`data Tree3 a b = Leaf3 bl | Node3 a b (Tree3 a b) (Tree3 a b) deriving Eq`

The following function will be implemented (automatically):

```
instance (Eq a, Eq b) => Eq (Tree3 a b) where
(==) (Leaf3 q) (Leaf3 s) = (q==s)
(==) (Node3 _ q t1 t2) (Node3 _ s u1 u2) = (q==s)&&(t1==u1)&&(t2==u2)
(==) _ _ = False
```

As we can see, the first argument of Node3 was omitted, which we would not want in some cases.

#### Conclusion

The informal difference between the two types of polymorphy:

- parametric - the same code regardless of type.
- ad-hoc - different code, although the same function names.

Only registered users can participate in the survey. Please come in.

## What topic would you like to see the next article about Haskell?

**33.8%**Error Handling 43**18.8%**Abstract Data Structures 24**19.6%**Recursion and recursion types 25**3.9%**Higher Order Functions 5**23.6%**Lambda calculus 30