# 6. Simple Algebraic Data Types

# 6. Simple Algebraic Data Types¶

## Notes¶

The category of sets **Set** is a monoidal category - we can multiply its
objects. These are product types.

Product types in Haskell are n-tuples, like `(a, b, c)`

. The creation of a
product type can be viewed as a binary operation on types, where the
isomorphism:

can look like the monoidal associative law:

where the multiplication of type objects is their cartesian product.

A more general way of defining product types in Haskell is by using `Pair`

:

```
data Pair a b = Pair a b
statement :: Pair String Int
statement :: Pair "My favourite number is" 5
```

`()`

is the unit of the product, as `(a, ())`

is isomorphic to `a`

:

```
toA :: (a, ()) -> a
toA (x, _) = x
fromA :: a -> ((), a)
fromA x = ((), x)
```

Symbolically, \(a * 1 = a\).

The coproduct gives rise to sum types, such as `Either a b`

:

```
data Either a b = Left a | Right b
```

Where `Either a b`

can have the value of `a`

or `b`

, but never both. Like
pairs and tuples, sum types are also commutative and nesting order is irrelevant
up to isomorphism.

**Set** is also a monoidal category with respect to the coproduct, the sum type.
The initial object acts as the unit (`Void`

in this case). Adding `Void`

to a sum type doesn’t change its content, similar to zero in addition.
`Either a Void`

is isomorphic to `a`

, as there is no way to construct
a `Right Void`

value. Symbolically, \(a + 0 = a\).

The product type of `(a, Void)`

is isomorphic to `Void`

, as there is no
value to satisfy `(a, Void)`

- the product type is **uninhabited**. Symbolically,
\(a * 0 = 0\).

The distributive property also holds:

Translated into types, `(a, Either b c)`

would correspond to `Either (a, b) (a, c)`

.

Two such intertwined monoids, product and sum types, form a **semiring**. We can’t
define subtraction of types, so it does not form a **ring**.

Recursive types, such as `List a`

:

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

form an equation. If we substitute `List a`

for \(x\) and `Nil`

for
\(1\) (as it can only have 1 value, it is essentially `()`

):

Resulting in an infinite list of products. A list can be empty (\(1\)),
a singleton (\(a\)), a pair (\(aa\)), a tuple (\(aaa\)), etc. Hence,
these are called **algebraic data types**.

A product type, `(a, b)`

must have values for both `a`

**and** `b`

. A sum
type, `Either a b`

has a value for either `a`

**or** `b`

. Logical and &
logical or also form a semiring. Mapped to types:

```
False = Void
True = ()
a || b = Either a b
a && b = (a, b)
```

## Challenges¶

### 6.1¶

**Show to isomorphism between Maybe a and Either () a.**

```
maybeToEither :: Maybe a -> Either () a
maybeToEither (Just a) = Right a
maybeToEither Nothing = Left ()
eitherToMaybe :: Either () a -> Maybe a
eitherToMaybe (Left ()) = Nothing
eitherToMaybe (Right a) = Just a
```

These functions are inverses of each other.

### 6.2¶

**Here’s a a sum type defined in Haskell:**

```
data Shape = Circle Float
| Rect Float Float
```

**When we want to define a function like area that acts on a Shape, we do it by
pattern matching on the two constructors:**

```
area :: Shape -> Float
area (Circle r) = pi * r * r
area (Rect d h) = d * h
```

**Implement Shape in C++ or Java as an interface and create two classes: Circle
and Rect. Implement area as a virtual function.**

```
interface Shape {
public float area();
}
class Circle implements Shape {
float r;
public Circle(float r) {
this.r = r;
}
public float area() {
return (float) Math.PI * r * r;
}
}
class Rect implements Shape {
float d;
float h;
public Rect(float d, float h) {
this.d = d;
this.h = h;
}
public float area() {
return d * h;
}
}
```

### 6.3¶

**Continuing with the previous example: We can easily add a new function circ
that calculates the circumference of a Shape. We can do it without touching the
definition of Shape:**

```
circ :: Shape -> Float
circ (Circle r) = 2.0 * pi * r
circ (Rect d h) = 2.0 * (d + h)
```

**Add circ to your C++ or Java implementation. What parts of the original code
did you have to touch?**

First, we have to add the function to the `Shape`

interface:

```
interface Shape {
public float area();
public float circ();
}
```

And then add the implementation of `circ`

to each of the classes that
implement the `Shape`

interface:

```
class Circle implements Shape {
...
public float circ() {
return 2.0F * (float) Math.PI * r;
}
}
class Rect implements Shape {
...
public float circ() {
return 2.0F * (d + h);
}
}
```

### 6.4¶

**Continuing further: Add a new shape, Square, to Shape and make all the
necessary updates. What code did you have to touch in Haskell vs. C++ or Java?
(Even if you’re not a Haskell programmer, the modifications should be pretty
obvious.)**

For Java, one would just need to add a new class that implements `Shape`

:

```
class Square implements Shape {
float w;
public Square(float w) {
this.w = w;
}
public float area() {
return w * w;
}
public float circ() {
return 4.0F * w;
}
}
```

In Haskell, however, one would need to update the `Shape`

type, as well
as add a new pattern to `area`

and `circ`

:

```
data Shape = Circle Float
| Rect Float Float
| Square Float
area :: Shape -> Float
...
area (Square w) = w * w
circ :: Shape -> Float
...
circ (Square w) = 4.0 * w
```

### 6.5¶

**Show that a + a = 2 * a holds for types (up to isomorphism). Remember that 2
corresponds to Bool, according to our translation table.**

Translated into types, \(a + a = 2 * a\) would be `Either a a -> (Bool, a)`

.
If they hold for types up to isomorphism, we should be able to define a pair
of inverse functions:

```
sumToProduct :: Either a a -> (Bool, a)
sumToProduct (Left a) = (False, a)
sumToProduct (Right a) = (True, a)
productToSum :: (Bool, a) -> Either a a
productToSum (True, a) = Right a
productToSum (False, a) = Left a
```