In this part of the course, we discuss the type system features that enable code reuse in more detail. We start with a discussion of parametric polymorphism, and continue looking more closely at overloading, and provide an overview of the most commonly used Haskell type classes.

## Accompanying materials

## 4–1 Parametric Polymorphism

We discuss what it means for a type to be the “most general type”. We explain that Haskell erases type information at run-time and that this means that types that are represented by unconstrained type variables are really totally unknown at runtime.

We conduct a thought experiment as to how the step-by-step generalisation of a type signature drastically limits the amount of functions we can write, and therefore how polymorphism provides us with implementation guidance.

#### Self Test

Which of the following types is the most general?

`-> [b] -> [(a,b)] [a] -> [a] -> [(a,a)] [a]`

Which of the following types is the most general?

`-> Int -> (a, Int) a Int -> a -> (Int, a)`

Which of the following types is the most general?

`-> [b] a -> b a a`

How many different total functions are there of type

`(Bool, Bool) -> (Bool, Bool)`

?How many different total functions are there of type

`(Bool, a) -> (a, Bool)`

?

## 4–2 Parametricity: The map Function as an Example

We take a look at the type of `map`

on lists and discuss what we can learn
from the parametric polymorphism occurring in its type signature about the
behaviour of the function.

#### Self Test

- Without knowing anything about the implementation of the function, if we
have a function
`f :: [a] -> Int`

and consider the calls`f [1,2,3]`

and`f "foo"`

, what can we say about the results?

- Both will yield
`Int`

s, of course, but we do not know which numbers the calls return. - Both will yield the same
`Int`

, but we do not know which one. - Both calls will yield the number
`3`

.

- Both will yield
- Without knowing anything about the implementation of the function, what
can you say about a function with type
`a -> a -> Bool`

? How many different total functions of this type are there?

## 4–3 Union Types

We show how parametric polymorphism is *not* the answer if a function wants
to have a choice between different types of values to return. We discuss how
union types such as `Either`

can be used instead, and how this approach is
also often taken by Haskell libraries that are embedding dynamically typed
languages into Haskell, such as the `aeson`

packages does for JSON.

#### Self Test

What does the datatype

`data Listy a = Plain a | ListOf [Listy a]`

allow you to express?

In the

`eval`

task from Assignments B, try to modify the datatype of expressions as follows`data Expr = Lit Int | Add Expr Expr | Neg Expr | And Expr Expr | Not Expr | Eq Expr Expr | If Expr Expr Expr`

and let us define

`data Value = IntVal Int | BoolVal Bool | Error`

Now redefine

`eval :: Expr -> Value`

such that`And`

represents`(&&)`

,`Not`

represents`not`

,`Eq`

represents`(==)`

. The`If`

construct should now expect a Boolean condition,`Add`

and`Neg`

should expect integer arguments, whereas`And`

and`Not`

should expect Bool arguments. If any conditions are violated, return`Error`

.

## 4–4 Overloading

We introduce type classes at the example of the `Eq`

class and discuss how one
can manually define instances of type classes. We also discuss default methods,
`MINIMAL`

pragmas, and the `InstanceSigs`

extension.

#### Self Test

What is the result of

`Left 3 == Right 3`

? Is it`True`

,`False`

, or a type error?Try to write down the correct type of

`map (==)`

including all class constraints. Only check in GHCi when you’re done.Does the type

`[[[Int]]]`

admit an equality test with`(==)`

? And what about the type`Maybe (Int -> Int)`

?If you ask for info in on the class

`Semigroup`

, you’ll see that it has methods called`(<>)`

and`sconcat`

and`stimes`

. Additionally, there is a MINIMAL pragma saying`{-# MINIMAL (<>) #-}`

What does this pragma mean?

- When defining an instance of the
`Semigroup`

class, we do not have to provide any definitions. - When defining an instance of the
`Semigroup`

class, we have to provide a definition for`sconcat`

and`stimes`

, but we can omit`(<>)`

. - When defining an instance of the
`Semigroup`

class, we have to provide a definition for`(<>)`

, but we can omit`sconcat`

and`stimes`

.

- When defining an instance of the

## 4–5 Type Class Overview: Eq, Ord, Enum, Bounded

We provide an overview of the most important type classes, starting with the
`Eq`

, `Ord`

, `Enum`

and `Bounded`

classes. We also discuss the concept of superclasses
in the context of the `Ord`

class, and we mention the notion of defaulting in the
context of the `Bounded`

class.

#### Self Test

Check in GHCi whether the class

`Monoid`

has any superclasses.What is the result of

`compare (Just (-1)) Nothing`

?What is

`minBound :: (Bool, Bool)`

? Check your answer in GHCi.What is

`[minBound ..] :: [(Bool, Bool)]`

? Check your answer in GHCi.What is

`[minBound ..] :: [Ordering]`

? Check your answer in GHCi.There is no real problem in defining class instances for functions, even though the classes we have been discussing so far have no such instances by default. Here is a possible equality instance for a subset of functions:

`instance (Bounded a, Enum a, Eq b) => Eq (a -> b) where == f2 = f1 all (\ x -> f1 x == f2 x) [minBound ..]`

With this definition, try what you get for

`||) == (||) (||) == (&&) (not . not == id +) == (+) (`

Explain how this instance works.

## 4–6 Type Class Overview: Show, Read

We continue our tour of the Haskell type classes by looking at `Show`

and `Read`

.
We also discuss the notion of ambiguous types and the differences in defaulting
behaviour between GHCi and GHC.

#### Self Test

What is the result of

`readMaybe "0" :: Maybe Bool`

? (You have to`import Text.Read`

first.)What is the result of

`readMaybe "[(1, True), (2, False)]" :: Maybe [(Int, Bool)]`

?Is the function

`f :: Int -> Int = read (show x) f x`

the identity function? If not, try to find a counterexample. If yes, try to argue why.

In the cases that the function

`g :: String -> String g x = show (read x :: Int)`

does not crash, does it then always produce the same string as the input? If not, try to find a counterexample. If yes, try to argue why?

## 4–7 Deriving Type Classes

We explain how instances for all the classes discussed so far can be automatically derived by GHC as long as the datatypes we try this on satisfy certain restrictions.

#### Self Test

Which of the type classes we discussed can be derived for the datatype

`data ChoiceOfThree a b c = One a | Two b | Three c`

Does it make sense to derive

`Eq`

and`Ord`

for the datatype`data IntegerWithInfinity = MinusInfinity | PlusInfinity | Finite Integer`

If not, what would need to be changed?

Can

`Bounded`

be derived for`IntegerWithInfinity`

? Can a sensible manual definition of`Bounded`

be given for`IntegerWithInfinity`

?

## 4–8 Type Class Overview: Functor, Foldable

We continue our overview of important type classes by discussing two classes that
define interfaces on type constructors (parameterised datatypes), namely `Functor`

and `Foldable`

. The `Functor`

class generalises the concept of types that have a
map function, and the `Foldable`

class is for types which contain elements in a
clear order, meaning in particular that their elements can be extracted as a list.

#### Self Test

What is the result of

`length [[1,2,3], [4,5,6]]`

? What is the result of`sum [[1,2,3], [4,5,6]]`

. What is the result of`fmap (+1) [[1,2,3], [4,5,6]]`

and what of`fmap length [[1,2,3], [4,5,6]]`

? Verify your answers in GHCi.Does

`newtype Matrix a = Matrix [[a]] deriving (Show, Functor, Foldable)`

work if you enable the language extensions for deriving

`Functor`

and`Foldable`

? If so, what is the result of`length (Matrix [[1,2,3], [4,5,6]])`

and of`sum (Matrix [[1,2,3], [4,5,6]])`

? What is the result of`fmap (+1) (Matrix [[1,2,3], [4,5,6]])`

and of`fmap length (Matrix [[1,2,3],[4,5,6]])`

? Verify your answers in GHCi.What is the result of

`product (Left 3)`

and of`product (Right 3)`

? What is the result of`elem 1 (1,2)`

and of`elem 2 (1,2)`

?

## 4–9 Optional: Classes for Numbers

We take a look at the different classes Haskell provides to deal with numbers and
operations on numbers, most prominently the `Num`

class. We also look at `Integral`

and `Fractional`

and a few others.

## 4–10 Optional: The Monomorphism Restriction and Defaulting

We discuss one of the darker and more confusing corners of Haskell. The monomorphism restriction causes that in some situations, Haskell deliberately refuses to infer the most general type of a declaration. Defaulting is a mechanism that Haskell uses to resolve otherwise ambiguous overloading in some circumstances. The defaulting rules that GHCi applies are somewhat different from the ones being used in normal Haskell source code.

## 4–11 Assignments D

It’s time for the next block of assignments. You can find them here.

You can save this file to a local directory and then open it in your editor and GHCi. The file then contains further instructions and several skeletons of functions that you are supposed to complete, as well as a few other questions.

Note that in this public version of the course, there is no way to submit the assignments.