# Algebraic Data Types

#######

# Algebraic Data Types

1. What problem are we solving?
2. Unions & intersections 
3. Define ADTs 
4. Solve our problem!

#######

# Problem

#######

# Problem

We would like to design the following function:

```typescript
function getCustomerDescription(customer: Customer): string {
  ...
}
```

Let's model this

-------

## Problem

1. A customer must have a name.
2. We have two types of customers right now: Guests and Hosts.
3. A guest can be verified or not. A guest should have a payment method.
4. A host can be a superhost, or not. A host should have an address.

-------

## Problem

```typescript
enum Type { Guest, Host }
enum Status { Verified, Super, None }

class Customer {
  constructor(
    public type: Type,
    public status: Status,
    public name: string,
    public payment?: Payment,
    public address?: Address,
  ) {}
}
```

Any issues?

-------

## Problem

```typescript
const customer = new Customer(
  Type.Guest,
  Status.Super,
  "John",
  null,
  null
);
```

We created a super guest with no payment information 😱

#######

# Aside: Union & Intersection

-------

# Union

```typescript[]
  type Fruit = 'orange'
  type Veggie = 'tomato'

type VeganFood = Fruit | Veggie
  ```

```typescript
  const veganDish: VeganFood = ???
  // What can go here?
  ```

```typescript
  const veganDish: VeganFood = 'orange';
  const anotherVeganDish: VeganFood = 'tomato';
  ```

</div>

-------

# Union

```typescript
  type Cat = {
    name: string,
    litterLocation: string,
  }

type Dog = {
    name: string,
    walkTime: Date,
  }

type Pet = Cat | Dog
  ```

```typescript
  const pet: Pet = ??? // What can go here?
  ```

```typescript
  const cat: Pet = { 
    name: 'Lilo', 
    litterLocation: 'basement' 
  }

const dog: Pet = { 
    name: 'Primo', 
    walkTime: Date.now(), 
  }
  ```

</div>

#######

# Intersections

```typescript
  type DeliciousFood = 'chocolate' | 'berries' | 'beef'

type HealthyFood = 'salad' | 'berries' | 'olives'

type GoodFood = DeliciousFood & HealthyFood
  ```

```typescript
  const goodFood: GoodFood = ???
  // What can go here?
  ```

```typescript
  const goodFood: GoodFood = 'berries'
  ```

</div>

It's the overlap between the two types

#######

# Intersections

```typescript
  type Cat = {
    name: string,
    litterLocation: string,
  }

type Dog = {
    name: string,
    walkTime: Date,
  }

type Pet = Cat & Dog
  ```

```typescript
  const pet: Pet = ??? 
  // What can go here?
  ```

<div>

```typescript
  const firstPet: Pet = {
    name: "Stitch",
  }
  ```

```typescript
  const secondPet: Pet = {
    name: "Stitch",
    litterLocation: "basement",
    walkTime: Date.now(),
  }
  ```

</div>

</div>

Is it firstPet or secondPet?

-------

# Intersections

![intersection-1](/images/intersection_1.svg)

![intersection-1](/images/intersection_2.svg)

</div>

#######

# Finally, ADTs

#######

# Definition

#######

# Definition

> A kind of type formed by combining other types.

It's likely you use these all the time.

#######

# Definition

There are two kinds:

1. Product type 
2. Sum type

#######

# Product Type

-------

# Product Type

Product types are formed by creating a structure with multiple values.

Does that sound familiar?

Intersection anyone?

-------

# Product Type

```typescript
type ProductFirst = { first: boolean }
type ProductSecond = { second: boolean }
```

```typescript
type Product = ProductFirst & ProductSecond
```

That's it.

-------

## Why is it called a product type?

How many unique possible values of `Product` can you have?

```typescript
type ProductFirst = { first: boolean }
type ProductSecond = { second: boolean }

type Product = ProductFirst & ProductSecond
```

Any guesses?

## 4

-------

## Why is it called a product type?

```typescript
type Product = ProductFirst & ProductSecond
```

We get our answer by multiplying 
`$$ |ProductFirst| \cdot |ProductSecond| $$`
`$$ 2 \cdot 2 $$`

## 4

#######

# Sum Type

-------

## Sum Type

```typescript
type Malus = "Apple";
type Citrus = "Orange" | "Mandarin";

type Sum = Malus | Citrus 
```

How many unique possible values of `Sum` can you have?

Any guesses?

## 3

You just add them up.

#######

## Algebraic Data Types

> ADTs are all about combining sum and product types using unions and intersections to model our data.

#######

# Back to the problem

-------

## Back to the problem

```typescript
enum Type { Guest, Host }
enum Status { Verified, Super, None }

class Customer {
  constructor(
    public type: Type,
    public status: Status,
    public name: string,
    public payment?: Payment,
    public address?: Address,
  ) {}
}
```

Let's use ADTs to improve this implementation.

-------

## Back to the problem

Let's create a union of Guest and Host

```typescript
type Guest = {
  type: Type.Guest,
  status: Status.Verified | Status.None,
  name: string,
  paymentMethod: Payment,
}

type Host = {
  type: Type.Host,
  status: Status.Super | Status.None,
  name: string,
  address: Address,    
}

type Customer = Guest | Host;
```

We've summed two product types.

There is no way we can create a Super guest or a Host without an address.

-------

## Type refinement

With that, we get free benefits:

```typescript

function getCustomerDescription(customer: Customer): string {
  if (customer.type === Type.Guest) {
    return `guest: ${customer.payment}`;
  } else if (customer.type === Type.Host) {
    return `host: ${customer.address}`;
  }

return "impossible";
}
```

-------

## Pattern Match

```typescript
// Stage 1 proposal

-------

### Wait a sec

### Couldn't I just do the same with interfaces?

-------

## OOP approach

```typescript
interface Customer {
  type: Type,
  status: Status,
}
```

```typescript
class Guest implements Customer {
  type = Type.Guest
  constructor(
    public status: GuestStatus, // limit to guest statuses
    public name: string,
    public payment: Payment) {}
}

class Host implements Customer {
  ...
}
```

Isn't that the same thing? Not exactly

-------

## Type refinement with OOP

```typescript
interface Customer {
  type: Type,
  status: Status,
}
```

```typescript
function getCustomerDescription(customer: Customer): string {
  if (customer.type === Type.Guest) {
    // What do we actually know here
  } else if (customer.type === Type.Host) {
    // What do we actually know here
  }

return "impossible"; // Are we sure?
}
```

</div>

Nothing! and that's a feature.

There is no control over who implements our interface.

-------

## Type refinement with ADTs

```typescript

function getCustomerDescription(customer: Customer): string {
  if (customer.type === Type.Guest) {
    return `guest: ${customer.payment}`; // we know for sure it's a guest with payment
  } else if (customer.type === Type.Host) {
    return `host: ${customer.address}`; // we know for sure it's a host with an address
  }

return "impossible"; // should never get here. customer is of type `never`.
}
```

-------

## Back to the problem

But We can still do better.

Let's use the algebra in algebraic.

#######

## Back to the problem

```typescript
type Guest = {
  type: Type.Guest,
  status: Status.Verified | Status.None,
  name: string, // this is common
  paymentMethod: Payment,
}

type Host = {
  type: Type.Host,
  status: Status.Super | Status.None,
  name: string, // this is common
  address: Address,    
}
```

</div>

#######

## Back to the problem

```typescript
type Guest = {
  type: Type.Guest,
  status: Status.Verified | Status.None,
  paymentMethod: Payment,
}

type Host = {
  type: Type.Host,
  status: Status.Super | Status.None,
  address: Address,    
}
```

</div>

#######

## Back to the problem

```typescript
  type Guest = {
    type: Type.Guest,
    status: Status.Verified | Status.None,
    paymentMethod: Payment,
  }

type Host = {
    type: Type.Host,
    status: Status.Super | Status.None,
    address: Address,    
  }
  ```

<div>

```typescript
  type CustomerBase = { name: string }
  ```

```typescript
  type Customer = CustomerBase & (Guest | Host)
  ```

</div>

Just like math!

#######

# One more thing

#######

## Type refinement

Imagine we extend our `Customer` to include `ExperienceHost` like so:

```typescript
type Customer = CustomerBase & (Guest | Host | ExperienceHost)
```

What do we get when we call

```typescript
getCustomerDescription(experienceHost)
```

We get `impossible`.

Wouldn't it be nice if the compiler warned us about this?

-------

## Type refinement

Let's introduce this absurd function:

```typescript
const absurd = <A,>(x: never): A => { throw 'impossible' };
```

Doesn't look very useful but ...

-------

## Type refinement

```typescript
function getCustomerDescription(customer: Customer): string {
  if (customer.type === Type.Guest) {
    // What do we actually know here
    return 'guest';
  } else if (customer.type === Type.Host) {
    // What do we actually know here
    return 'host';
  }

return absurd(customer);
}
```

Works great prior to ExperienceHost declaration

But once we extend Customer we will get `Argument of type 'CustomerBase & ExperienceHost' is not assignable to parameter of type 'never'`

-------

## [demo](https://www.typescriptlang.org/play?#code/KYOwrgtgBAKgngB2FA3lA4mYBnALgGigAkB7PQgUQA8kAnAS1AGNkBfAWAChRIoBlXAENcYbKigA1YAwBmjACaE+YOoQByJEGy5dciZAEF582jjEBeKHgYgA5gG5d+qAAVBcCKFxRL1+ncdOJyQMLDwfVC4oKD0kAC5YfQA6TBwCKKshEWwEgWFRJKlZBSgAH34sgo0tfAyEd08QXABZYFwACxJ5BLcPL1rODiDOWORScMsUDNGE+CQk8fTOaLx8nIq1pOU6Mo3spOrgAejBY1NsdaMTM0JoqC4h4ORqOkYQFkWIqeWY-Vnkl7SN4sY5QYA0IHMYAJPx2AaPEbOADColwJE8tAAQoJsMhJlAQIJPDDcDZbFAEaMoCi8OjpBEaWiMdjcVAAGRQAAUqXC5U+5UBDChiwAlDpOExNOFBAAjbBgWjyCIAHgM+AAfJyqAktAA3aQihIGHzq1AdWgkADuUAA5PQIAgyNh6DKADbAG2sQJcGRgd64eiaKC2NqMum0AAiOCYDAQAc0nKYqPDCTDGMNmTJkR+9BkXKTtIxSSp5lLiXmPNwIuzdygAHo61AAOrtYRQeQkKCW5CCJgiQSu11wKAAaxAVqg7WkwAy0VMIloIFttjCuBtgWirDBrtZufzyaLJbLc2ACzIVZrdwbzdb3g7XZ7fbAA6Ho-H1qnplnUHnCqXNs6PB1wyBE5zaP8oFleVFUTA8DUCVggA)

```demo
enum Type { Guest, Host, Experience }
enum Status { Verified, Super, None }

type Address = string;
type Payment = string;

type Guest = {
  type: Type.Guest,
  status: Status.Verified | Status.None,
  paymentMethod: Payment,
}

type Host = {
  type: Type.Host,
  status: Status.Super | Status.None,
  address: Address,    
}

type ExperienceHost = {
  type: Type.Experience,
  experience: string,
}

type CustomerBase = { name: string }

type Customer = CustomerBase & (Guest | Host | ExperienceHost)

const absurd = <A,>(x: never): A => {throw 'impossible'};

function getCustomerDescription(customer: Customer): string {
  if (customer.type === Type.Guest) {
    // What do we actually know here
    return 'guest';
  } else if (customer.type === Type.Host) {
    // What do we actually know here
    return 'host';
  }

return absurd(customer);
}
```

#######

# Thank you