# Types & Typeclasses

Haskell is a strongly, statically typed programming language, which helps prevent us from writing bad programs.

- Java, C, Rust - strongly typed
- Python, Ruby - dynamically typed

Types have many benefits:

- Describe the value of an expression
- Prevent us from doing silly things
`not 7`

gives`Type Error`

- Good for documentation
- Type errors occur at compile time

GHC checks types and infers the type of expressions for us. Types are discarded after type checking, and are not available at runtime.

## Type notation

We say an expression has a type by writing `expression :: type`

, read as "expression has type".

- If we can assign a type to an expression, it is "well typed"
- A type approximates and describes the value of an expression.

```
42 :: Int
True :: Bool
'c' :: Char
"Cake" :: String
0.5 :: Double
4 + 8 :: Int
2 * 9 + 3 :: Int
True && False :: Bool
"AB" ++ "CD" :: String
even 9 :: Bool
```

Before writing a definition, it is good practice to write its type.

```
daysPerWeek :: Int
daysperWeek = 7
```

### Function Types

The types of functions are denoted using arrows `->`

. The `not`

function is defined as `not :: Bool -> Bool`

, read "not has type bool to bool". It means if you give me a `Bool`

, I will give you back another `Bool`

.

The definition of the `not`

function is shown below.

```
not :: Bool -> Bool
not True = False
not False = True
not True :: Bool
```

The last line shows how function application eliminates function types, as by applying a function to a value, one of the types from the function definition is removed as it has already been applied.

The `xor`

function takes two boolean arguments and is defined:

```
xor :: Bool -> Bool -> Bool
xor False True = True
xor False False = False
xor True True = False
xor True False = True
```

Applying one argument to a function that takes two is called *partial function application*, as it partially applies arguments to a function to return another function. This is because all functions in haskell are *curried*, meaning all functions actually only take one argument, and functions taking more than one argument are constructed from applying multiple functions with one argument.

```
xor :: Bool -> Bool -> Bool
xor True :: Bool -> Bool -- partially applied function
xor True False :: Bool
```

## Polymorphic Types

What is the type of `\x -> x`

? Could be:

```
f :: Int -> Int
f :: Bool -> Bool
f :: Char -> Char
```

These are all permissible types. To save redifining a function, we can use type variables. Anything with a single lowercase character is a type variable (`a`

in this case).

```
\x -> x :: a -> a
```

`\x -> x`

is the identity function, as it returns its argument unchanged. We can also have functions with more than one type variable, to specify that arguments have different types:

```
const :: a -> b -> a
const x y = x
```

## Tuples

Tuples are a useful data structure

```
(4, 7) :: (Int, Int)
(4, 7.0) :: (Int, Double)
('a', 9, "Hello") :: (Char, Int, String)
--can nest tuples
((4, 'g'), False) :: ((Int, Char), Bool)
--can also contain functions
(\x -> x, 8.15) :: (a->a, Double)
```

Functions on pairs. These are all in the standard library

```
fst :: (a,b) -> a
snd :: (a,b) -> b
swap :: (a,b) -> (b,a)
-- these functions can also be defined by pattern matching
fst (x,y) = x
snd (x,y) = y
swap (x,y) = (y,x)
```

## Type Classes

Type classes are used for restricting polymorphism and overloading functions.

- The
`(+)`

operator probably has type`(+) :: Int -> Int -> Int`

,- This is correct, as this typing is permissible

- What about
`1.2 + 3.4`

?- Will raise an error with this definition of
`(+)`

- Will raise an error with this definition of
- Can polymorphism help?
`(+) :: a -> a -> a`

- This is stupid
- Allows any types
- Won't work

- A
*type class constraint*is needed - The actual type is
`(+) :: Num a => a -> a -> a`

- The
`Num a =>`

part is the constraint part - Tells the compiler that
`a`

has to belong to the typeclass`Num`

- The
- Type class constraints are used to constrain type variables to only types which support the functions or operators specified by the type class
- Type class names start with an uppercase character
`Num`

is a type class that represents all types which support arithmetic operations

### Defining Type Classes

A type class is defined as follows:

```
class Num a where
(+) :: a -> a -> a
(-) :: a -> a -> a
abs :: a -> a
```

`Num`

is the name of the type class`a`

is the type variable representing it in the method typings- The type class contains method signatures for all functions that members of the type class must implement

The type class contains type definitions, but no implementations for the functions. To implement them, we need to tell the compiler which types implement the type class and *how* they implement the functions in the type class. The `Show`

typeclass tells the compiler that a type can be converted to a string.

```
-- typeclass definition
class Show a where
show :: a -> String
-- instance of typeclass for bool type
instance Show Bool where
show True = "True"
show False = "False"
```

The `instance`

definition tells the compiler that `Bool`

is a member of `Show`

, and how it implements the functions that `Show`

defines.

### Prelude Type Classes

`Num`

for numbers`Eq`

for equality operators`==`

`/=`

`Ord`

for inequality/comparison operators`>`

`<=`

etc`Show`

for converting things to string- Many More

The REPL makes extensive use of `Show`

to print things. There are no show instances for function types, so you get an error if you try to `Show`

functions. Typing `:i`

in the REPL gets info on a type class. `:i Num`

gives:

```
class Num a where
(+) :: a -> a -> a
(-) :: a -> a -> a
(*) :: a -> a -> a
negate :: a -> a
abs :: a -> a
signum :: a -> a
fromInteger :: Integer -> a
{-# MINIMAL (+), (*), abs, signum, fromInteger, (negate | (-)) #-}
-- Defined in ‘GHC.Num’
instance Num Word -- Defined in ‘GHC.Num’
instance Num Integer -- Defined in ‘GHC.Num’
instance Num Int -- Defined in ‘GHC.Num’
instance Num Float -- Defined in ‘GHC.Float’
instance Num Double -- Defined in ‘GHC.Float’
```

### Types of Polymorphism

In Java, there are two kinds of polymorphism:

- Parametric polymorphism
- (Generics/Templates)
- A class is generic over certain types
- Can put whatever type you like in there to make a concrete class of that type

- Subtype polymorphism
- Can do
`class Duck extends Bird`

- Can put
`Duck`

s wherever`Bird`

s are expected

- Can do

Haskell has two kinds of polymorphism also:

- Parametric polymorphism
- Type variables
`id :: a -> a`

- Can accept any type where
`a`

is

- Ad-hoc polymorphism
- Uses type classes
`double :: Num a => a -> a`

`double x = x * 2`

### Further Uses of Constraints

An example `Show`

instance for pairs:

```
instance (Show a, Show b) => Show (a,b) Show where
show (x,y) = "(" ++ show x ++ ", " ++ show y ++ ")"
```

The `(Show a, Show b) => `

defines a constraint on `a`

and `b`

that they must both be instances of show for them to be used with this instance. The instance is actually defined on the type `(a,b)`

.

Can also define that a typeclass has a superclass, meaning that for a type to be an instance of a typeclass, it must be an instance of some other typeclass first. The `Ord`

typeclass has a superclass constraint of the `Eq`

typeclass, meaning something cant be `Ord`

without it first being `Eq`

. This makes sense, as you can't have an ordering without first some notion of equality.

```
class Eq a => Ord a where
(<) :: a -> a -> Bool
(<=) :: a -> a -> Bool
```

### Default Implementations

Type classes can provide default method implementations. For example, `(<=)`

can be defined using the definition of `(<)`

, so a default one can be provided using `(==)`

```
class Eq a => Ord a where
(<) :: a -> a -> Bool
(<=) :: a -> a -> Bool
(<=) x y = x < y || x == y
-- or defined infix
x <= y = x < y || x == y
```

### Derivable Type Classes

Writing type class instances can be tedious. Can use the `deriving`

keyword to automatically generate them, which does the same as manually defining type class instances.

```
data Bool = False | True
deriving Eq
data Module = CS141 | CS118 | CS126
deriving (Eq, Ord, Show)
```

Certain other typeclasses can be dervied too, by enabling language extensions within GHC. The extension `XDeriveFunctor`

allows for types to include a `deriving Functor`

statement.

## Data Types

How do we make our own data types in haskell? Algebraic data types.

`Bool`

is a type- There are two values of type
`Bool`

`True`

`False`

```
data Bool = True | False
```

A type definition consists of the type name `Bool`

and it's data constructors, or values `True | False`

. A type definition introduces data constructors into scope, which are just functions.

```
True :: Bool
False :: Bool
```

We can pattern match on data constructors, and also use them as values. This is true for *all* types.

```
not :: Bool -> Bool
not True = False
not False = True
```

More examples:

```
data Module = CS141 | CS256 | CS263
data Language = PHP | Java | Haskell | CPP
--for this one, the type name and constructor name are separate names in the namespace
data Unit = Unit
-- this one has no values
data Void
```

### Parametrised Data Constructors

Parameters can be added to a data constructor by adding their types after the constructor's name. The example below defines a type to represent shapes. Remember that data constructors are just functions, and can be partially applied just like other functions.

```
data Shape = Rect Double Double | Circle Double
Rect :: Double -> Double -> Shape
Circle :: Double -> Shape
-- functions utilising the Shape type
-- constructs a square
square x :: Double -> Shape
square x = Rect x x
-- calculates area of a shape using pattern matching on constructors
area :: Shape -> Double
area (Rect w h) = w * h
area (Circle r) = pi * r * r
isLine :: Shape -> Bool#
isLine (Rect 1 h) = True
isLine (Rect w 1) = True
isLine _ = False
-- examples
area (square 4.0)
=> area (Rect 4.0 4.0)
=> 4.0 * 4.0
=> 16.0
area (Circle 5.0)
=> pi * 5.0 * 5.0
=> pi * 25.0
=> 78.53981...
```

### Parametrised Data Types

The `Maybe`

type is an example of a data type parametrised over some type variable `a`

. It exists within the standard library, defined as `data Maybe a = Nothing | Just a`

. This type is used to show that either there is no result, or some type `a`

.

A function using the `Maybe`

type to perform devision safely, returning `Nothing`

if the divisor is 0, and the result wrapped in a `Just`

if the division can be done.

```
data Maybe a = Nothing | Just a
safediv :: Int -> Int -> Maybe Int
safediv x 0 = Nothing
safediv x y = Just (x `div y)
-- safediv 8 0 => Nothing
-- safediv 8 4 = Just (8 `div` 4) = Just 2
-- this is included in stdlib for extracting the value using pattern matching
fromMaybe :: a -> Maybe a -> a
fromMaybe x Nothing = x
fromMaybe _ (Just x) = x
```

Null references were invented in the 1960s ... the guy who invented them called them his "billion dollar mistake". The `Maybe`

type is a good alternative, which makes it clear that a value may be absent. Similar concepts exist in other procedural languages (Swift, Rust)

### Recursive Data Types

In Haskell, data types can be defined in terms of themselves. An example definition of the natural numbers is shown below, where a number is either zero, or one plus another number.

```
data Nat = Zero | Succ Nat
Zero :: Nat
Succ :: Nat -> Nat
one = Succ Zero
two = Succ one
three = Succ two
add :: Nat -> Nat -> Nat
add Zero m = m
add (Succ n) m = Succ (add n m)
mul :: Nat -> Nat -> Nat
mul Zero m = Zero
mul (Succ n) m = add m (mul n m)
```

Another example defining binary trees in terms of themselves. A binary tree consists of subtrees (smaller binary trees). This type is parametrised over some type variable `a`

also.

```
Data BinTree a = Leaf a | Node (BinTree a) (BinTree a)
--converts a binary tree to a list
flatten :: BinTree a -> [a]
flatten (Leaf x) = [x]
flatten (Node l r) = flatten l ++ flatten r
-- computes the max depth of the tree
depth :: BinTree a -> Int
depth (Leaf _) = 1
depth (Node l r) = 1 + max (depth l) (depth r)
```

## Type Aliases

Types can be aliased. For example, `String`

has been an alias of `[Char]`

all along.

```
type String = [Char]
```

Another example, defining a `Predicate`

type

```
type Predicate a = a -> Bool
isEven :: Predicate Int
isEven n = n `mod` 2 == 0
isEven' :: (Eq a, Integral a) => Predicate a
isEven' n = n `mod` 2 == 0
```