Fun with Types

types.md

Reading & Understanding Types: Exercises to Level Up!

A type is a set of values. A value stores information at runtime in computer memory (such as a certain integer, a certain list of strings, etc.).

Monomorphic Function Types

In many languages, functions are values (Haskell, PureScript, Javascript)! Or at least, you can pretend they are (Scala, Java).

trait Function1[A, B] {
  def apply(v: A): B
}

interface Function1<A, B> {
  B apply(A a);
}

Basic

1. In English, express the meaning of the following type:

   String => Int

   Function1<String, Int>

   String -> Int

2. Implement a function that satisfies this type.

Higher-Order

Parameters and return values may themsevles be functions!

1. In English, express the meaning of the following types:

   (String => Int) => (String => Int)

   Function1<Function1<String, Int>, Function1<String, Int>>

   (String -> Int) -> (String -> Int)

2. Implement a function that satisfies this type.

Polymorphic Function Types

Imagine a world in which functions can accept and return types, not just values. In fact, you don't have to imagine it, because many languages can, although they use a funky, irregular syntax to do that!

These are called polymorphic functions (or sometimes, universally-quantified types), from the Greek "poly" (many) and morphos (shape — in this case, a type!).

trait MyPolyFunction {
  def apply[A](v: A): A
}

interface MyPolyFunction {
  <T> T apply(T v);
}

forall a. a -> a

Basic

1. In English, express the meaning of the following type:

   trait MyPolyFunction {
     def apply[A, B](left: A, right: B): B
   }

   interface MyPolyFunction {
     <A, B> B apply(A left, B right);
   }

   forall a b. a -> b -> b

2. Implement a function that satisfies this type.

3. BONUS: How many functions are there that satisfy this type:

Higher-Ranked

Polymorphic functions can accept and return polymorphic functions. The horrors!!!

1. In English, express the meaning of the following type:

   trait F {
     def apply[A](left: A, right: A): A
   }
   trait G {
     def apply(v: F): F
   }

   interface F {
     <T> T apply(T left, T right);
   }
   interface G {
     F apply(F v);
   }

   type F = forall a. a -> a -> a
   type G = F -> F

2. Implement a function that satisfies this type.

3. BONUS: How many functions are there that satisfy this type?

Existential Types

If you understand higher-ranked types, guess what, you already understand existentials! Any existential type can be converted to a (higher-ranked) universally-quantified type. This process is called skolemization.

An existential says: OK, I can look at that type, but only if I am polymorphic enough to handle its variation.

1. In English, express the meaning of whatever the heck this thing is:

   trait ListMap[B] {
     type A
   
     val list : List[A]
   
     val map : A => B
   }

   type ListMap b = forall z. (forall a. List a -> (a -> b) -> z) -> z

2. Implement a function that satisfies this type.