jdegoes/lambdaconf-sums-products.md

## lambdaconf-sums-products.md

      
    Raw
  

              lambdaconf-sums-products.md
            
          
    Introduction

A type is a set of values.
Int -- The set of all integer values (that fit into 64 bits)

To say that a term a has type A is to say that a is a member of the set of values represented by A.
3.1415 -- Has type Decimal; i.e. is a member of the set of decimal values

There are two very special types. These are called product types and sum types.
Product Types

A product type is a specific and very fundamental way to combine two types.
The product of A and B, denoted A * B, is a set of values such that each value consists of both a value of type A AND a value of type B.
In other words, if ab has type A * B, then ab has both an A value and a B value.
class Tuple<A, B> {
  public final A _1;
  public final B _2;
  
  public Tuple(A a, B b) {
    this._1 = a;
    this._2 = b;
  }
}   

data Tuple a b = Tuple a b

case class Tuple[A, B](_1: A, _2: B)

Exercises


EASY: Create a product type of strings and strings, representing a container for first names and last names. Create a few values of that type.
MODERATE: Create a product of strings and strings and integers, representing a container for first names, last names, and ages.
HARD: How many unique ways of solving (2) are there? Prove that they are or are not equivalent.

Sum Types

A sum type is another specific and fundamental way to combine two types.
The sum of A and B, denoted A + B, is a set of values such that each value consists of either a value of type A, OR a value of type B.
In other words, if ab has type A + B, then ab has either an A value or a B value.
interface Either<A, B> {
  <Z> Z fold(Function<A, Z> left, Function<B, Z> right);
}
class Left<A, B> implements Either<A, B> {
  public final A value;
  public Left(A value) {
    this.value = value;
  }
  public <Z> Z fold(Function<A, Z> left, Function<B, Z> right) {
    return left.apply(this.value);
  }
}
class Right<A, B> implements Either<A, B> {
  public final B value;
  public Right(B value) {
    this.value = value;
  }
  public <Z> Z fold(Function<A, Z> left, Function<B, Z> right) {
    return right.apply(this.value);
  }
}

data Either a b = Left a | Right b

sealed trait Either[A, B]
final case class Left[A, B](value: A) extends Either[A, B]
final case class Right[A, B](value: B) extends Either[A, B]

Exercises


EASY: Create a sum type of strings or integers, representing a street name that might be a string or that might be a number (such as 11). Create a few values of that type.
MODERATE: Create a sum type of strings or integers or decimals, representing a number that is represented as an unbounded string, or a finite integer, or a finite decimal.
HARD: How many unique ways of solving (2) are there? Prove that they are or are not equivalent.

Why Products and Sums?

These may seem like strange names and notations, but they actually make sense!
Let's define |A| as the number of unique values in the set represented by A.
So, for example, |Boolean| = 2.
Then finite products observe the following law:
|A * B| = |A| * |B|

Similarly, finite sums observe the following law:
|A + B| = |A| + |B|

Exercises


EASY: Let's say Size comes in small, medium, and large, and Roast comes in dark, medium, and light. What is |Size * Roast|?
EASY: Let's say either everyone is a Powerlifter (light, medium, or heavy) or they are a Runner (slow, moderate, fast). What is |Powerlifter + Runner|?
MODERATE: Come up with an example product and an example sum, and compute their unique values by using the sum and product laws introduced in this section.
HARD: Prove that |A * B * C| = |A| * |B| * |C|.
HARD: Prove that |A + B + C| = |A| + |B| + |C|.

Universality

An amazing fact is that sums and products are universal: all the data structures in your favorite programming language can be represented by them!
Although you would seldom program this way in real life, it's still useful to see the universality of sums and products for yourself.
Products

Let's model a person that has a first name, last name, age, and address.
Tuple<String, Tuple<String, Tuple<Integer, Address>>> person;

type Person = Tuple String (Tuple String (Tuple Int (Tuple Address)))

type :*:[A, B] = Tuple[A, B]
   
type Person = String :*: String :*: Int :*: Address

Sums

Let's model a shape that is a rectangle or a circle or a square.
Either<Rectangle, Either<Circle, Square>> shape;

type Shape = Either Rectangle (Either Circle (Either Square))

type :+:[A, B] = Either[A, B]

type Shape = Rectangle :+: Circle :+: Square

Exercises


MODERATE: Take any data structure, identify how it can be decomposed into sums and products, and then, if your programming language supports it, create a type alias which faithfully models the data structure.

Special Sauce: 0 and 1

There are two very important types, which I will give special names: 0 and 1.
The type 0 represents a type with no values. Such a type is sometimes called Void, and it's said to be uninhabited, because its set of values is empty.
The type 1 represents a type with a single value. Such a type is sometimes called Unit, and while it's inhabited, it doesn't really convey any information content.
Exercises


MODERATE: Describe the type 0 + 1. Can you simplify this without changing the representable states of the type?
MODERATE: What is the sum / product representation of a type that has the same information content as a single bit?
HARD: Define both Void and Unit in your programming language of choice. Note that Void typically comes with a function which can convert a value of type Void (of which there are none) into any other type — which, as strange as it sounds, is actually legitimate and completely type safe!

Extensible, Compositional Sums & Products

Nested tuples and eithers arise naturally in combinators. For example, you might have a combinator or which takes a Parser<A>, and a Parser<B>, and returns a Parser<Either<A, B>>.
Some languages allow you to reduce the pain of dealing with these nested types.
Exercises


EASY: Define a type alias for a 3-way product and a 3-way sum. Define the same thing for a 4-way product and a 4-way sum.


MODERATE: Accessing the nested data is not very easy. For your 3- and 4-way products and sums, define accessor / fold functions that make it easier.


HARD: It is hard to define projection and injection functions that are reusable across product and sums of different arity. This is caused by the asymmetry of the tail element in the product or sum. Investigate the properties of the following alternate definitions and try to define reusable projection and injection functions:
type Either3 a b c = Either a (Either b (Either c Void))

type Tuple3 a b c = Tuple a (Tuple b (Tuple c Unit))