Functional Programming With Kotlin and Arrow — Algebraic Data Types

Other Algebraic Properties

The analogy between types and algebra is fun because it reveals some interesting facts. For instance, you know that:

A * 1 = A = 1 * A

Which translates into:

A * Unit = A = Unit * A

This tells you that Pair<A, Unit> is the same as Pair<Unit, A>, which is the same as A.

typealias UnitType<A> = Pair<A, Unit>

It also means that adding a property of type Unit to an existing type doesn’t add any useful information.

You also know that:

A + 0 = A = 0 + A

This becomes:

A + Nothing = A = Nothing + A

This represents a type that you can write as:

typealias NothingType<A> = Either<Nothing, A>

Finally, you can write:

A * 0 = 0 = 0 * A

Which becomes:

A * Nothing = 0 = Nothing * A

You can write this as:

typealias NothingPair<A> = Pair<A, Nothing>

You can’t create a Pair using a value of type A and Nothing, so this is basically the Nothing type.

Using Algebra With the Optional Type

Another curious thing is that:

A + 1 = A + Unit = Either<A, Unit>
1 + A = Unit + A = Either<Unit, A>

This means that the Either<A, Unit> type has all the possible values of A plus a single value which is Unit. It’s something you could represent like:

sealed class Opt<out A>
object None : Opt<Nothing>()
class Some<A>(value: A) : Opt<A>()

Do you recognize it? This is basically the Optional type. You have a value of type A or you have another single and unique value which is None here, but could also be Unit.

More Fun With Exponents

So far, you’ve seen what multiplication and addition mean in the context of types. Next, you’ll see what you can express using exponents.

Start by writing the following expression:

// 1
A ^ 2 = A * A = Pair<A,A>
// 2
A ^ 3 = A * A * A = Pair<A, Pair<A,A>> = Pair<Pair<A,A>, A>
// ...

Starting from a given type A, you can see that:

1. You can represent the value A ^ 2 as A * A, which is equivalent to Pair<A,A>.
2. For the same reason, you can think of A ^ 3 as A * A * A, which is equivalent to Pair<A,Pair<A,A>> or Pair<Pair<A,A>, A>.

The same is true for each value of the exponent.

But what about the meaning of the expression A ^ B, where A and B are types? How many possible values can you represent with a type that corresponds to the expression, like Boolean ^ Triage?

This is less intuitive and needs some more work.

If the analogy between types and algebra is true, the number of values for the type Boolean ^ Triage should be 8 because:

Boolean ^ Triage = 2 ^ 3 = 8

But what does the number 8 represent? It represents how you can take the number of values of Boolean to the power of the number of values of Triage. This can happen in multiple ways — which are the number of ways you can associate a Boolean value to a value of the Triage type.

This perfectly describes the (Triage) -> Boolean function type. You can prove this by adding the following code to Exponents.kt:

fun func0(triage: Triage): Boolean = when (triage) {
    Triage.RED -> false
    Triage.YELLOW -> false
    Triage.GREEN -> false
}

fun func1(triage: Triage): Boolean = when (triage) {
    Triage.RED -> false
    Triage.YELLOW -> false
    Triage.GREEN -> true
}

fun func2(triage: Triage): Boolean = when (triage) {
    Triage.RED -> false
    Triage.YELLOW -> true
    Triage.GREEN -> false
}

fun func3(triage: Triage): Boolean = when (triage) {
    Triage.RED -> false
    Triage.YELLOW -> true
    Triage.GREEN -> true
}

fun func4(triage: Triage): Boolean = when (triage) {
    Triage.RED -> true
    Triage.YELLOW -> false
    Triage.GREEN -> false
}

fun func5(triage: Triage): Boolean = when (triage) {
    Triage.RED -> true
    Triage.YELLOW -> false
    Triage.GREEN -> true
}

fun func6(triage: Triage): Boolean = when (triage) {
    Triage.RED -> true
    Triage.YELLOW -> true
    Triage.GREEN -> false
}

fun func7(triage: Triage): Boolean = when (triage) {
    Triage.RED -> true
    Triage.YELLOW -> true
    Triage.GREEN -> true
}

There are exactly 8 different ways of mapping a Triage value into a Boolean value. You can think of A ^ B as equivalent to a function from B to A. You can then assert that:

A ^ B = (B) -> A

Understanding Currying

You can use what you learned in the previous paragraph to prove some interesting facts. Given three types A, B and C, you know that:

(A ^ B) ^ C = A ^ (B * C)

The equality = is symmetric so you can also write:

A ^ (B * C) = (A ^ B) ^ C 

Now, recall what you learned in the previous paragraphs about multiplication and exponentiation and translate that to:

(Pair<B,C>) -> A = (C) -> (B) -> A 

Using some Kotlin notation, you can write this as:

(B,C) -> A = (C) -> (B) -> A 

Sorting the types’ variables in an easier way, you can read that equation by saying that a function of two input parameters, A and B, and output C (A, B) -> C is equivalent to a function with an input parameter of A and an output parameter of function type (B) -> C. This is called currying. You define currying by adding the following code to Exponents.kt.

fun <A, B, C> Func2<A, B, C>.currying(): (A) -> (B) -> C = { a: A ->
    { b -> this(a, b) }
}

Func2<A, B, C> is a typealias. Define it by copying the following code to Exponents.kt:

typealias Func2<A, B, C> = (A, B) -> C

This represents any function with two input parameters and one output parameter.

As you saw earlier, the equivalence is symmetric so you can define the inverse function by adding the following code:

fun <A, B, C> Chain<A, B, C>.uncurrying(): Func2<A, B, C> = { a: A, b: B ->
    this(a)(b)
}

Add this as well:

typealias Chain<A, B, C> = (A) -> (B) -> C

This is a typealias that defines a function’s type with a single input parameter and another function as an output parameter.