Functional Programming With Kotlin and Arrow — Algebraic Data Types

Carrying and the Flip Function

When you work on platforms like Android, it’s not uncommon to use functions like the one below. Enter the following code into Exponents.kt:

// 1
typealias Task = () -> Unit

// 2
fun runDelayed(task: Task, delay: Long) {
    // 3
    thread {
        // 4
        sleep(delay)
        // 5
        task()
    }
}

With this example you:

1. Define the Task typealias for any generic function which contains some code to execute at some time in the future.
2. Create a function, runDelayed(), which has a Task as its first parameter and the delay as the second.
3. Start a thread to simulate the async execution of the task.
4. Use sleep() to wait for the delay you pass as a parameter.
5. Run the task, invoking the related parameter.

What’s important here is that the delay parameter comes second. This is not unusual; in Android, you can find similar methods like:

fun postDelayed(r: Runnable, delayMillis: Long): Boolean

The same happens, for instance, in other contexts like the one related to the following constructor for String:

String(byteArrayOf(), Charsets.ISO_8859_1)

As you can see, in this case, the Charset is the second parameter. You have to include it in every place where you use that specific constructor in the same way as the delay in the previous snippets of code. How can you make the code easier to write and maintain?

As a first step, define flip() by copying the following code into Exponents.kt:

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

This is a higher-order function that transforms a function of type (A) -> (B) -> C into a function of type (B) -> (A) -> C. There, the first two parameters are swapped or, as the function name says, flipped.

Now, use this function to define a new run1SecondDelayed by entering the following code into Exponents.kt:

val run1SecondDelayed = ::runDelayed // 1
    .currying() // 2
    .flip()(1000L) // 3

In this code, you define run1SecondDelayed by:

1. Using the reference to the existing runDelayed(), which is of type (Task, Long) -> Unit.
2. Applying currying() to get a new function of type (Task) -> (Long) -> Unit.
3. Using flip() to get a function of type (Long) -> (Task) -> Unit, which you invoke using a specific duration value.

The result is a function of type (Task) -> Unit, which you invoke with the following simple code:

    run1SecondDelayed {
        println("Printed after 1 sec")
    }

Note that you specify the duration just once. You can do the same with the String constructor by writing code like:

// 1
val strContr: Func2<ByteArray, Charset, String> = ::String
// 2
val isoStrConstr = strContr.currying().flip()(Charsets.ISO_8859_1)

In this code, you:

1. Define strContr as the reference to the constructor, which accepts an array of bytes as the first parameter and the Charset as the second. It’s important to note that Kotlin requires an explicit type definition to address a specific constructor overload.
2. Apply currying and flip to set the Charset in a single location.

Using Algebra With the List Type

As a last bit of fun with algebra and types, enter the following definition into List.kt:

sealed class NaturalNumber
// 1
object Zero : NaturalNumber()
// 2
class Successor(prec: NaturalNumber) : NaturalNumber()

This is a simple sealed class which represents all the natural numbers as:

1. The Zero value.
2. A set of all the possible Successors.

As an example, add the following to the same file:

// 1
val ZERO = Zero
// 2
val ONE = Successor(Zero)
// 3
val TWO = Successor(Successor(Zero)) // Successor(ONE)
// 4
val THREE = Successor(Successor(Successor(Zero))) // Successor(TWO)
// 5
// ...

Here you define:

1. The first value as ZERO.
2. ONE as the successor of ZERO.
3. TWO as the successor of ONE.
4. THREE as the successor of TWO.
5. And so on…

What’s more interesting is, comparing the previous definition with the one about Either<E, A>, you can say that:

NaturalNumber = 1 + NaturalNumber

This is because you translate Either into an addition operation, but the previous addition becomes:

NaturalNumber = 1 + NaturalNumber
NaturalNumber = 1 + (1 + NaturalNumber)
NaturalNumber = 1 + (1 + (1 + NaturalNumber))
NaturalNumber = 1 + (1 + (1 + (1 + NaturalNumber)))
...

This suggests that the Set of NaturalNumber can be seen as a sequence of ones, one for each natural number.

Consider now the List<A> data type. Using the same reasoning, you can think of it as something you can define by entering the following code into List.kt:

sealed class FList<out A>
object FEmpty : FList<Nothing>()
class Tail<A>(val head: A, val tail: FList<A>) : FList<A>()

Use the name FList — aka, Functional List — to distinguish it from the existing List type.

This means that a FList<A> can be empty, or you can think of it as a head and a tail which might be empty or not. You can then create a list of five values in the following way, and add it to List.kt:

val countList = Tail(1, Tail(2, Tail(3, Tail(4, Tail(5, FEmpty)))))

Functional Lists and Algebra

Now, what if you want to calculate the sum of the elements in the FList<Int>? Do it by implementing a recursive function, like this:

fun FList<Int>.sum(): Int = when (this) {
    is FEmpty -> 0
    is Tail<Int> -> head + tail.sum()
}

Now, test it by copying and running the following code in List.kt:

fun main() {
    println(countList.sum())
}

But from an algebraic point of view, you write the previous FList<A> type like this:

FList<A> = 1 + A * FList<A>

This is because it can be the FEmpty (and so the 1) or a Pair of an object of type A and another FList<A>.

Now, repeat what you did in the case of the NaturalNumber and get:

FList<A>  = 1 + A * FList<A>
          = 1 + A * (1 + A * FList<A>) = 1 + A + A ^ 2 + A * FList<A>
          = 1 + A + A ^ 2 + A ^ 3 + A ^ 4 * FList<A>
...

This allows you to see the FList<A> as a possible combination of all the possible FList<A> of length 0, 1, 2, 3 and so on.

The + here has the meaning of a logical OR so an FList<A> is an empty Flist OR a single element of type A OR a pair of elements of type A OR a triplet of elements of type A and so on.

Write this as:

FList<A> = 1 + A * FList<A>    =>
FList<A> - A * FList<A> = 1    =>

FList<A> * (1 - A) = 1         =>

               1
FList<A> =  -------
            (1 - A)

This is the geometric series, which is equivalent to:

               1
FList<A> =  ------- = 1 + A + A^2 + A^3 + A^4 + .... + A^N + ...
            (1 - A)

It’s curious how a complex data type like List<A> has an algebraic relationship.