**Learning goals**

- To understand howÂ
**type**,Â **newtype**Â andÂ **data**Â declarations work and how they differ.
- To be able to define functions over recursively defined data types using pattern matching.
- To understand how recursively defined data types can be used to implement the formation rules of a language.
- To understand the notion of term constructors and how they are used.
- To understand the principles of and be able to declare new instances of type classes.
- To understand how the above notions can be applied in the setting of a larger program.

**Note thatÂ ***data*Â declarations are also known asÂ *algebraic datatypes*Â elsewhere.

## Type declarations

You can define a new name for an existing type with a *type declaration*:

```
type String = [Char]
type Pos = (Int, Int)
-- You can give parameters
type Pair a = (a, a)
```

Type declarations can be nested, but **not recursive!**

## Newtype

If your defined type has a single constructor with a single argument, you could use `newtype`

.

E.g. a type of natural numbers could be:

```
newtype Nat = N Int
-- Similar to
type Nat = Int
data Nat = N Int
```

Using `newtype`

ensures that, in the above example, `Nat`

and `Int`

arenâ€™t synonyms, but different types. So the type checker will prevent mix-ups.

## Data Declarations

You can define a competely new type by specifying its values using a *data declaration*:

`data Bool = False | True`

The two values (T/F) seen above are called *constructors* for the type `Bool`

.
Type and constructor names must always begin with an upper-case letter.
Data declarations are similar to CFGs. The former specifies the values of a type, while the latter the sentences of a language.

### Example

```
data Answer = Yes | No | Unknown
answers :: [Answer]
answers = [Yes, No, Unknown]
flip :: Answer -> Answer
flip Yes = No
flip No = Yes
flip Unknown = Unknown
```

### Constructors can have parameters

```
-- Circle and Float can be seen as constructors.
data Shape = Circle Float | Rect Float Float
square :: Float -> Shape
square n = Rect n n
area :: Shape -> Float
area (Circle r) = pi * r^2
area (Rect x y) = x * y
```

### Data declarations can have parameters

`Maybe`

already exists, this just shows its declaration:

```
data Maybe a = Nothing | Just a -- Maybe represents something that can fail.
safediv :: Int -> Int -> Maybe Int
safediv _ 0 = Nothing
safediv m n = Just (m `div` n)
safehead :: [a] -> Maybe a
safehead [] = Nothing
safehead xs = Just (head xs)
```

## Recursive Types

```
data Nat = Zero | Succ nat
nat2int :: Nat -> Int
nat2int Zero = 0
nat2int (Succ n) = 1 + nat2int n
int2nat :: Int -> Nat
int2nat 0 = Zero
int2nat n = Succ (int2nat (n-1))
add :: Nat -> Nat -> Nat
add m n = int2nat (nat2int m + nat2int n)
-- or, using recursion
add Zero n = n
add (Succ m) n = Succ (add m n)
```

## Arithmetic Expressions example

```
data Expr = Val Int
| Add Expr Expr
| Mul Expr Expr
-- example: add (Val 1) (Mul (Val 2) (Val 3))
-- which is: 1 + 2 * 3
size :: Expr -> Int
size (Val n) = 1
size (Add x y) = size x + size y
size (Mul x y) = size x + size y
eval :: Expr -> Int
eval (Val n) = n
eval (Add x y) = eval x + eval y
eval (Mul x y) = eval x * eval y
```

## Class and instances declarations

```
class Eq a where
(==), (/=), :: a -> a -> Bool
x /= y = not (x == y)
```

**Says:** For a type `a`

to be an instance of the class `Eq`

, it must support equality and inequality operators of the specified types.

It also includes a *default definition* for the `/=`

operator, so declaring an instance only requires a definition for the == operator

So you might make the `Bool`

type into an equality type like so:

```
instance Eq Bool where
False == False = True
True == True = true
_ == _ = False
```

**You can extend classes to make new ones**, e.g. like so:

```
class Eq a => Ord a where
(<), (<=), (>), (>=) :: a -> a -> Bool
min, max :: a -> a -> a
min x y | x <= y = x
| otherwise = y
max x y | x <= y = y
| otherwise = x
```

Which is actually how the `Ord`

class is defined in the prelude.

It means that, for a type to be an instance of `Ord`

, it must be an instance of `Eq`

, but also support the denoted operators.

## Derived instances

When you declare a new type, youâ€™d usually also make them instances of some built-in classes.

You use the *deriving* mechanism for this.

Hereâ€™s how the type `Bool`

is declared in the prelude:

```
data Bool = False | True
deriving (Eq, Ord, Show, Read)
```

And the result of this is that all member functions of the derived classes can be used with logical values. E.g. `False == False`

.

# Flashcards