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

The List Functor

The List interface is one of the most important abstractions when you have to manage collections of data. This is also a functor because it has a map function which has this signature:

public inline fun <T, R> Iterable<T>.map(transform: (T) -> R): List<R> 

This is an extension function for Iterable<T>, and List is an Iterable. You can see how this definition is very similar to the one you have created for the Maybe<T> class.

You can see a pattern here, and this is one of the most powerful properties of category theory.

Arrow Typeclasses

In OOP, a design pattern is a guideline for a solution to a recurrent problem.

When you find an interface that defines an operation that creates objects of a specific type, you recognize the factory pattern. When you build some UI with nested components, you recognize the usage of the composite pattern.

The same process happens in FP. But how can you define what you have created with Maybe and List? How can you represent the idea of a Functor in a way that doesn’t depend on the specific type to which it is applied?

Arrow calls this a typeclass, which is a way to describe a reusable coding pattern in FP. This is not intuitive and needs some definitions.

Type Constructors and Higher Kinds

In the previous examples, you created a Maybe<T>. This is a generic type which means that you can define a Maybe<Int> or a Maybe<String> which are conceptually different types.

You can see the Maybe<T> as a way to create different types by changing the value of the type parameter T. This is a type constructor,where the input parameter is the generic type, and the result is a specific type.

Arrow represents the idea of type constructors using higher kinds, which are a mechanism introduced in Scala. They represent an abstraction of all type constructors. Arrow defines a Kind like this:

interface Kind<out F, out A>

The idea is to consider a type like Maybe<T> as a specific Kind<F, T> where F is Maybe and T is the usual parameter type.

As such, create a new file Maybe.kt in the rw package of the data-types module, and add the following definition:

import arrow.Kind

class Maybe<T>: Kind<Maybe<T>, T>

This definition compiles but it’s not very easy to work with. So, Arrow provides a surrogate type called Of type. In the same file, replace the previous definition of Maybe with this:

// 1
class ForMaybe private constructor()
// 2
typealias MaybeOf<T> = Kind<ForMaybe, T>
// 3
sealed class Maybe<out T> : MaybeOf<T>
class Some<T>(val value: T) : Maybe<T>()
object None : Maybe<Nothing>()

1. First, you define the ForMaybe type. This is very similar to the definition of Nothing. It defines a type but it prevents the creation of instances.
2. Then, you define the type MaybeOf<T> as an alias of the type Kind<ForMaybe, T>.
3. Finally, you define the type Maybe<T> as extension of MaybeOf<T> which you recall is a Kind<ForMaybe, T>.

You see that Maybe<T> is the only implementation of Kind<ForMaybe, T> so you can create an extension that gives you a Maybe<T> from a Kind<ForMaybe, T> with a simple downcast. The name of this extension, by convention, is fix().

Add this code to the same file Maybe.kt:

fun <T> MaybeOf<T>.fix() = this as Maybe<T>

Now you can get the specific implementation Maybe<T> from the abstraction Kind<ForMaybe, T> simply invoking the fix() method.

“So what?!”

What is the advantage of doing this? Since Maybe<T> is a Kind<MaybeOf, T>, if you define a function for the latter, it will be available to use for the former.

For example, imagine that you define a map function with this signature:

fun <F, A, B> Kind<F, A>.map(f: (A) -> B): Kind<F, B>

Since you’ve defined it as extension function of the type Kind<F, A>, it’s available for all the Kind specializations, including your Maybe<T> type.

The way you’ll work with higher kinded types most of the time is in the following pattern:

1. Create an instance of your own type. For example, Maybe<T>.
2. Work with this value by using all the functionality available for its Kind abstraction.
3. Finally, you can get your own concrete type back by using the fix function.

Arrow Data Types

In the previous paragraph, you had to create the Of type for the Maybe type because Kotlin is missing a way to represent the concept of a type constructor. Fortunately, you don’t have to create all that code because Arrow will do it for you using the @higherkind annotation.

Replace all the code in the Maybe.kt file with the following:

package rw

import arrow.higherkind

@higherkind
sealed class Maybe<out A> : MaybeOf<A> {
  companion object
}

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

Note the presence of an empty companion object, which is required since Arrow uses it as the anchor point for some generated code.

It’s important to note that this code won’t compile until you build the related module. That is because the MaybeOf type is one that Arrow will generate for you. Go ahead and choose Build Project from the Build menu.

You can check the generated code by looking at the higherkind.rw.Maybe.kt file in the build folder, which you can find following the path in the following picture:

Arrow generated code for data types

If you open that file, you’ll see that the generated code is practically the same as what you created earlier by hand, fix() method included:

class ForMaybe private constructor() { companion object }
typealias MaybeOf<A> = arrow.Kind<ForMaybe, A>

@Suppress("UNCHECKED_CAST", "NOTHING_TO_INLINE")
inline fun <A> MaybeOf<A>.fix(): Maybe<A> =
  this as Maybe<A>

Using the @higherkind annotation, you can create what Arrow calls Data Types.

Functors in Arrow

The Maybe data type you just created is not a functor yet. You need to implement a Type class through what Arrow calls an extension. Arrow makes this easy.

Create a new file MaybeFunctor.kt in the rw package of the app module, and add the following code:

import arrow.Kind
import arrow.extension
import arrow.typeclasses.Functor

// 1
@extension
// 2
interface MaybeFunctor : Functor<ForMaybe> {
  // 3
  override fun <A, B> Kind<ForMaybe, A>.map(fn: (A) -> B): Kind<ForMaybe, B> {
    // 4
    val maybe = this.fix()
    return when (maybe) {
      is Some<A> -> Some<B>(fn(maybe.value))
      else -> None
    }
  }

  companion object
}

This code contains several interesting points:

1. The @extension annotation triggers the Arrow code generation on the specific type class.
2. In this case, you create an implementation of the Functor<T> interface Arrow provides. If you look at its code (not shown here for brevity) you can see that it defines map and other functions based on that. You can see, for instance, the lift function, which converts map(), receives a function as its parameter into another function that receives the value to which the function should be applied. You’ll see more of that in a future tutorial.
3. Then you define the required map function in a similar way to what you already did in the custom implementation, but with a fundamental property: It’s defined on Kind<ForMaybe, B>.
4. Thanks to the previous point, you can use the fix() function to get your concrete data type to work with in your implementation of map().

The map() function alone doesn’t make your data type a functor. As you’ve seen in the first part of the tutorial, the other fundamental properties of identity, composition and associativity must be true.

Now you’re ready to test your new Arrow-based Functor code.

As a first step, copy the StringToIntMaybe.kt file from the custom-maybe module to the app module. This looks like a repetition of the code, but the Maybe types that you use in the two modules are not the same.

Now, create a Main.kt file in the rw package of the app module, and add the following code:

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

When you run this code, you’ll see that only the second usage produces output, the expected roman numberal. Your MaybeFunctor from Arrow is working as expected?