Functional Programming with Kotlin and Arrow Part 2: Categories and Functors

The Associativity of Function Composition

To complete the proof that types and functions are a category, you need to prove that function composition has associativity, which is the following:

h compose (g compose f) = (h compose g) compose f

given that these functions have the following types:

f: (A) -> B
g: (B) -> C
h: (C) -> D

To prove this, keep the previous code and apply the referential transparency you’ve learned about in the previous tutorial to the left and right sides of the equation above. From the left side, you get this:

h compose (g compose f) = h compose ({ a: A -> g(f(a)) }) = { a: A -> h(g(f(a))) }

On the right you get:

(h compose g) compose f = ({ b: B -> h(g(b)) }) compose f = { a: A -> h(g(f(a))) }

These two sides are then identical. You just proved that types and functions create a category!

Morphisms and Function Types

In the category of types and functions, each object is a type, and each morphism is a function. Given two types, you can have infinite morphisms. The set of all morphisms between two types, which can even be equal in case of identity, has a name: hom-set. A hom-set is a representation of the concept of a function type.

If types and functions create a category, anything you discover to be true in category theory will also be true for types and functions. Identity, composition and associativity are just the tip of the iceberg, and in the next sections, your efforts to prove that types and functions create a category will pay off.

Mapping Between Categories: Functors

Suppose you have a category C which contains two objects, a and b, and a morphism, f, between them.

You want to define a mapping, which you can call F between a and b and another pair of objects in a different category D, which you’ll call a’ and b’.

You also want F to map morphisms, so it will map f into a morphism f’ in the D category.

Take a look at all of this in this next image, visually:

a' = F a
b' = F b
f' = F f

Functor definition

For F to be a correct mapping, then if f is a morphism from a to b, f : (a) -> b, then the same must be true for their mapped counterparts, so Ff must be a morphism from Fa to Fb:

F f : (F a) -> F b

The F mapping that you’ve defined here is a functor and, thanks to the property above, it maintains the structure of a category. But what is a functor in practice?

The Maybe Functor

Suppose you have the function stringToInt that converts a String into the Int that it contains. If this is not possible, the function throws an exception.

A function like this is simple and you can find it in the StringToInt.kt file in the functions module:

val stringToInt: (String) -> Int = Integer::parseInt

You need to explicitly type the function to remove the ambiguity with another overload of the parseInt method of the Int class.

Now, suppose you want to convert an Int into the related roman numeral.

To do so, you can use the intToRoman function in the IntToRoman.kt file in the same functions module. It uses the toRoman function in the Roman.kt file. The type of this function is (Int?) -> String.

val intToRoman: (Int?) -> String = Int?::toRoman

It would be nice to compose these two functions in a declarative way. A possible way of doing this is by implementing a functor called Maybe<T>.

Navigate to the custom-maybe module, create a CustomMaybe.kt file in the rw package and copy this code into the file:

sealed class Maybe<out T>
class Some<T>(val value: T): Maybe<T>()
object None: Maybe<Nothing>()

This is a sealed class with a generic type T, which has two possible realizations. The type Some<T> represents the case when you can encapsulate a value of type T. The second is the case when the result doesn’t exist.

If you think about about the previous stringToInt function, this is exactly the type the function should return. Depending on whether the input string can be converted to a valid `Int` value, you might have a result or not.

As a first option, you could rewrite the same function like this in a new file called StringToIntMaybe.kt in the rw package, still in the custom-maybe module:

val stringToIntMaybe: (String) -> Maybe<Int> =
  { s ->
    try {
      Some(Integer.parseInt(s))
    } catch (e: NumberFormatException) {
      None
    }
  }

If the input contains something that can be converted to an Int, the function will return a Some with the value. Otherwise it will return a None.

Chaining Operations on Maybe

But what’s the advantage of this?

Remember that your superpowers are abstraction and composition.

What you tried to do here is apply a function to a value of a generic type T and get a value as a result or nothing. Then you want to apply other functions like the one which converts the Int into roman numerals.

To do that, define the map function like this in the CustomMaybe.kt file in the custom-maybe module:

fun <T, S> Maybe<T>.map(fn: (T) -> S): Maybe<S> = when (this) {
  is Some<T> -> Some<S>(fn(this.value))
  else -> None
}

This is an extension function on the type Maybe<T> that has a parameter with a function type, which maps values in T into values in S. The return type is Maybe<S> and it’ll be a Some<S> in case the function returns a value, or None if it doesn’t. If the receiver of the function is None, the result will be None.

If you want to compose the function for converting a String into Int and then get its roman numeral representation, it will be quite easy.

Write and run this code in a file called Main.kt, which you can create in the custom-maybe module:

fun main() {
  stringToIntMaybe("Hello")
    .map(intToRoman)
    .map { print(it) }
}

Run this main function.

You’ll get nothing in output because the input is a String that cannot be converted into Int, and so the conversion to a roman numeral won’t happen.

Replace the previous code with this:

fun main() {
  stringToIntMaybe("123")
    .map(intToRoman)
    .map { print(it) }
}

If you run this code, you’ll get the following output, which is the roman numeral representation of the number 123.

CXXIII

What you’ve just built in Maybe<T> is a functor. It’s a safe way to control side effects.

You’re Maybe<T> is similar to the nullable types that Kotlin gives you for free using the ? symbol with a type.