## Recap: Haskell Crash Course II

- Core program element is an
**expression** - Every
*valid*expression has a**type**(determined at compile-time) - Every
*valid*expression reduces to a*value*(computed at run-time)

## Recap: Haskell

**Basic values & operators**

`Int`

,`Bool`

,`Char`

,`Double`

`+`

,`-`

,`==`

,`/=`

**Execution / Function Calls**

- Just
*substitute equals by equals*

**Producing Collections**

- Pack data into
*tuples*&*lists*

**Consuming Collections**

- Unpack data via
*pattern-matching*

## Next: Creating and Using New Data Types

`type`

Synonyms:*Naming*existing types`data`

types:*Creating*new types

## Type Synonyms

Synonyms are just names (“aliases”) for existing types

- think
`typedef`

in`C`

## A type to represent `Circle`

A tuple `(x, y, r)`

is a *circle* with center at `(x, y)`

and radius `r`

`type Circle = (Double, Double, Double)`

## A type to represent `Cuboid`

A tuple `(length, depth, height)`

is a *cuboid*

`type Cuboid = (Double, Double, Double)`

## Using Type Synonyms

We can now use synonyms by creating values of the given types

```
circ0 :: Circle
= (0, 0, 100) -- ^ circle at "origin" with radius 100
circ0
cub0 :: Cuboid
= (10, 20, 30) -- ^ cuboid with length=10, depth=20, height=30 cub0
```

And we can write functions over synonyms too

```
area :: Circle -> Double
= pi * r * r
area (x, y, r)
volume :: Cuboid -> Double
= l * d * h volume (l, d, h)
```

We should get this behavior

```
>>> area circ0
31415.926535897932
>>> volume cub0
6000
```

## QUIZ

Suppose we have the definitions

```
type Circle = (Double, Double, Double)
type Cuboid = (Double, Double, Double)
circ0 :: Circle
= (0, 0, 100) -- ^ circle at "origin" with radius 100
circ0
cub0 :: Cuboid
= (10, 20, 30) -- ^ cuboid with length=10, depth=20, height=30
cub0
area :: Circle -> Double
= pi * r * r
area (x, y, r)
volume :: Cuboid -> Double
= l * d * h volume (l, d, h)
```

What is the result of

`>>> volume circ0`

**A.** `0`

**B.** Type error

## Beware!

Type Synonyms

Do not

*create*new typesJust

*name*existing types

And hence, synonyms

- Do not prevent
*confusing*different values

## Creating *New* Data Types

We can avoid mixing up by creating *new* `data`

types

```
-- | A new type `CircleT` with constructor `MkCircle`
data CircleT = MkCircle Double Double Double
-- | A new type `CuboidT` with constructor `MkCuboid`
data CuboidT = MkCuboid Double Double Double
```

### Constructors are the **only way** to create values

`MkCircle`

creates`CircleT`

`MkCuboid`

creates`CuboidT`

## QUIZ

Suppose we create a new type with a `data`

definition

```
-- | A new type `CircleT` with constructor `MkCircle`
data CircleT = MkCircle Double Double Double
```

What is the **type of** the `MkCircle`

*constructor*?

**A.** `MkCircle :: CircleT`

**B.** `MkCircle :: Double -> CircleT`

**C.** `MkCircle :: Double -> Double -> CircleT`

**D.** `MkCircle :: Double -> Double -> Double -> CircleT`

**E.** `MkCircle :: (Double, Double, Double) -> CircleT`

## Constructing Data

Constructors let us *build* values of the new type

```
circ1 :: CircleT
= MkCircle 0 0 100 -- ^ circle at "origin" w/ radius 100
circ1
cub1 :: Cuboid
= MkCuboid 10 20 30 -- ^ cuboid w/ len=10, dep=20, ht=30 cub1
```

## QUIZ

Suppose we have the definitions

```
data CuboidT = MkCuboid Double Double Double
type Cuboid = (Double, Double, Double)
volume :: Cuboid -> Double
= l * d * h volume (l, d, h)
```

What is the result of

`>>> volume (MkCuboid 10 20 30)`

**A.** `6000`

**B.** Type error

## Deconstructing Data

Constructors let us *build* values of new type … but how to *use* those values?

How can we implement a function

```
volume :: Cuboid -> Double
= ??? volume c
```

such that

```
>>> volume (MkCuboid 10 20 30)
6000
```

## Deconstructing Data by Pattern Matching

Haskell lets us *deconstruct* data via pattern-matching

```
volume :: Cuboid -> Double
= case c of
volume c MkCuboid l d h -> l * d * h
```

`case e of Ctor x y z -> e1`

is read as as

**IF** - `e`

evaluates to a value that *matches the pattern* `Ctor vx vy vz`

**THEN** - evaluate `e1`

after naming `x := vx`

, `y := vy`

, `z := vz`

## Pattern matching on Function Inputs

Very common to do matching on function inputs

```
volume :: Cuboid -> Double
= case c of
volume c MkCuboid l d h -> l * d * h
area :: Circle -> Double
= case a of
area a MkCircle x y r -> pi * r * r
```

So Haskell allows a nicer syntax: *patterns in the arguments*

```
volume :: Cuboid -> Double
MkCuboid l d h) = l * d * h
volume (
area :: Circle -> Double
MkCircle x y r) = pi * r * r area (
```

Nice syntax *plus* the compiler saves us from *mixing up* values!

## But … what if we *need* to mix up values?

Suppose I need to represent a *list of shapes*

- Some
`Circle`

s - Some
`Cuboid`

s

What is the problem with `shapes`

as defined below?

`= [circ1, cub1] shapes `

Where we have defined

```
circ1 :: CircleT
= MkCircle 0 0 100 -- ^ circle at "origin" with radius 100
circ1
cub1 :: Cuboid
= MkCuboid 10 20 30 -- ^ cuboid with length=10, depth=20, height=30 cub1
```

## Problem: All list elements must have the *same* type

**Solution???**

## QUIZ: Variant (aka Union) Types

Lets create a *single* type that can represent *both* kinds of shapes!

```
data Shape
= MkCircle Double Double Double -- ^ Circle at x, y with radius r
| MkCuboid Double Double Double -- ^ Cuboid with length, depth, height
```

What is the type of `MkCircle 0 0 100`

?

**A.** `Shape`

**B.** `Circle`

**C.** `(Double, Double, Double)`

## Each *Data Constructor* of `Shape`

has a different type

When we define a data type like the below

```
data Shape
= MkCircle Double Double Double -- ^ Circle at x, y with radius r
| MkCuboid Double Double Double -- ^ Cuboid with length, depth, height
```

We get *multiple constructors* for `Shape`

```
MkCircle :: Double -> Double -> Double -> Shape
MkCuboid :: Double -> Double -> Double -> Shape
```

## Now we can create collections of `Shape`

Now we can define

```
circ2 :: Shape
= MkCircle 0 0 100 -- ^ circle at "origin" with radius 100
circ2
cub2 :: Shape
= MkCuboid 10 20 30 -- ^ cuboid with length=10, depth=20, height=30 cub2
```

and then define collections of `Shape`

s

```
shapes :: [Shape]
= [circ1, cub1] shapes
```

## EXERCISE

Lets define a type for 2D shapes

```
data Shape2D
= MkRect Double Double -- ^ 'MkRect w h' is a rectangle with width 'w', height 'h'
| MkCirc Double -- ^ 'MkCirc r' is a circle with radius 'r'
| MkPoly [Vertex] -- ^ 'MkPoly [v1,...,vn]' is a polygon with vertices at 'v1...vn'
type Vertex = (Double, Double)
```

Write a function to compute the `area`

of a `Shape2D`

```
area2D :: Shape2D -> Double
= ??? area2D s
```

**HINT**

You may want to use this helper that computes the area of a triangle at `v1`

, `v2`

, `v3`

```
areaTriangle :: Vertex -> Vertex -> Vertex -> Double
= sqrt (s * (s - s1) * (s - s2) * (s - s3))
areaTriangle v1 v2 v3 where
= (s1 + s2 + s3) / 2
s = distance v1 v2
s1 = distance v2 v3
s2 = distance v3 v1
s3
distance :: Vertex -> Vertex -> Double
= sqrt ((x2 - x1) ** 2 + (y2 - y1) ** 2) distance (x1, y1) (x2, y2)
```

## Polymorphic Data Structures

Next, lets see **polymorphic data types**

which **contain** many kinds of values.

## Recap: Data Types

Recall that Haskell allows you to create brand new data types

```
data Shape
= MkRect Double Double
| MkPoly [(Double, Double)]
```

## QUIZ

What is the type of `MkRect`

?

```
data Shape
= MkRect Double Double
| MkPoly [(Double, Double)]
```

**a.** `Shape`

**b.** `Double`

**c.** `Double -> Double -> Shape`

**d.** `(Double, Double) -> Shape`

**e.** `[(Double, Double)] -> Shape`

## Tagged Boxes

Values of this type are either two doubles *tagged* with `Rectangle`

```
>>> :type (Rectangle 4.5 1.2)
Rectangle 4.5 1.2) :: Shape (
```

or a list of pairs of `Double`

values *tagged* with `Polygon`

```
> :type (Polygon [(1, 1), (2, 2), (3, 3)])
ghciPolygon [(1, 1), (2, 2), (3, 3)]) :: Shape (
```

### Data values inside special **Tagged Boxes**

*Recursive* Data Types

We can define datatypes *recursively* too

```
data IntList
= INil -- ^ empty list
| ICons Int IntList -- ^ list with "hd" Int and "tl" IntList
deriving (Show)
```

(Ignore the bit about `deriving`

for now.)

## QUIZ

```
data IntList
= INil -- ^ empty list
| ICons Int IntList -- ^ list with "hd" Int and "tl" IntList
deriving (Show)
```

What is the type of `ICons`

?

**A.** `Int -> IntList -> List`

**B.** `IntList`

**C.** `Int -> IntList -> IntList`

**D.** `Int -> List -> IntList`

**E.** `IntList -> IntList`

## Constructing `IntList`

Can *only* build `IntList`

via constructors.

```
>>> :type INil
INil:: IntList
>>> :type ICons
ICons :: Int -> IntList -> IntList
```

## EXERCISE

Write down a representation of type `IntList`

of the list of three numbers `1`

, `2`

and `3`

.

```
list_1_2_3 :: IntList
= ??? list_1_2_3
```

**Hint** Recursion means boxes *within* boxes

## Trees: Multiple Recursive Occurrences

We can represent `Int`

*trees* like

```
data IntTree
= ILeaf Int -- ^ single "leaf" w/ an Int
| INode IntTree IntTree -- ^ internal "node" w/ 2 sub-trees
deriving (Show)
```

A *leaf* is a box containing an `Int`

tagged `ILeaf`

e.g.

```
>>> it1 = ILeaf 1
>>> it2 = ILeaf 2
```

A *node* is a box containing two sub-trees tagged `INode`

e.g.

```
>>> itt = INode (ILeaf 1) (ILeaf 2)
>>> itt' = INode itt itt
>>> INode itt' itt'
INode (INode (ILeaf 1) (ILeaf 2)) (INode (ILeaf 1) (ILeaf 2))
```

## Multiple Branching Factors

e.g. 2-3 trees

```
data Int23T
= ILeaf0
| INode2 Int Int23T Int23T
| INode3 Int Int23T Int23T Int23T
deriving (Show)
```

An example value of type `Int23T`

would be

```
i23t :: Int23T
= INode3 0 t t t
i23t where t = INode2 1 ILeaf0 ILeaf0
```

which looks like

## Parameterized Types

We can define `CharList`

or `DoubleList`

- versions of `IntList`

for `Char`

and `Double`

as

```
data CharList
= CNil
| CCons Char CharList
deriving (Show)
data DoubleList
= DNil
| DCons Char DoubleList
deriving (Show)
```

## Don’t Repeat Yourself!

Don’t repeat definitions - Instead *reuse* the list *structure* across *all* types!

Find abstract *data* patterns by

- identifying the
*different*parts and - refactor those into
*parameters*

## A Refactored List

Here are the three types: What is common? What is different?

```
data IList = INil | ICons Int IList
data CList = CNil | CCons Char CList
data DList = DNil | DCons Double DList
```

**Common:** `Nil`

/`Cons`

structure

**Different:** type of each “head” element

### Refactored using Type Parameter

`data List a = Nil | Cons a (List a)`

### Recover original types as *instances* of `List`

```
type IntList = List Int
type CharList = List Char
type DoubleList = List Double
```

## Polymorphic Data has Polymorphic Constructors

Look at the types of the constructors

```
>>> :type Nil
Nil :: List a
```

That is, the `Empty`

tag is a value of *any* kind of list, and

```
>>> :type Cons
Cons :: a -> List a -> List a
```

`Cons`

takes an `a`

*and* a `List a`

and returns a `List a`

.

```
cList :: List Char -- list where 'a' = 'Char'
= Cons 'a' (Cons 'b' (Cons 'c' Nil))
cList
iList :: List Int -- list where 'a' = 'Int'
= Cons 1 (Cons 2 (Cons 3 Nil))
iList
dList :: List Double -- list where 'a' = 'Double'
= Cons 1.1 (Cons 2.2 (Cons 3.3 Nil)) dList
```

## Polymorphic Function over Polymorphic Data

Lets write the list length function

```
len :: List a -> Int
Nil = 0
len Cons x xs) = 1 + len xs len (
```

`len`

doesn’t care about the actual *values* in the list - only “counts” the number of `Cons`

constructors

Hence `len :: List a -> Int`

- we can call
`len`

on**any kind of list**.

```
>>> len [1.1, 2.2, 3.3, 4.4] -- a := Double
4
>>> len "mmm donuts!" -- a := Char
11
>>> len [[1], [1,2], [1,2,3]] -- a := ???
3
```

## Built-in Lists?

This is exactly how Haskell’s “built-in” lists are defined:

```
data [a] = [] | (:) a [a]
data List a = Nil | Cons a (List a)
```

`Nil`

is called`[]`

`Cons`

is called`:`

Many list manipulating functions e.g. in [Data.List][1] are *polymorphic* - Can be reused across all kinds of lists.

```
(++) :: [a] -> [a] -> [a]
head :: [a] -> a
tail :: [a] -> [a]
```

## Generalizing Other Data Types

Polymorphic trees

```
data Tree a
= Leaf a
| Node (Tree a) (Tree a)
deriving (Show)
```

Polymorphic *2-3* trees

```
data Tree23 a
= Leaf0
| Node2 (Tree23 a) (Tree23 a)
| Node3 (Tree23 a) (Tree23 a) (Tree23 a)
deriving (Show)
```

## Kinds

`List a`

corresponds to *lists of values* of type `a`

.

If `a`

is the *type parameter*, then what is `List`

?

A *type-constructor* that - takes *as input* a type `a`

- returns *as output* the type `List a`

But wait, if `List`

is a *type-constructor* then what is its “type”?

- A
*kind*is the “type” of a type.

```
>>> :kind Int
Int :: *
>>> :kind Char
Char :: *
>>> :kind Bool
Bool :: *
```

Thus, `List`

is a function from any “type” to any other “type”, and so

```
>>> :kind List
List :: * -> *
```

## QUIZ

What is the *kind* of `->`

? That, is what does GHCi say if we type

`>>> :kind (->) `

**A.** `*`

**B.** `* -> *`

**C.** `* -> * -> *`

We will not dwell too much on this now.

As you might imagine, they allow for all sorts of abstractions over data.

If interested, see this for more information about kinds.