Exploring properties of function composition in Kotlin

Function composition is a technique where you create a new function by applying the result of one function to another. I've sometimes heard this described as "chaining" multiple functions together.

Assuming two functions \(f(x)\) and \(g(x)\), we can compose a new function \(h(x)\) by passing the result of \(g(x)\) to \(f(x)\)

\[h(x)=f(g(x))\]

Another notation for \( f(g(x)) \) is \(f \circ g(x) )\) ( or \(f \circ g\) omitting the parameter), read as \(f\) of \(g\) of \(x\), or \(f\) after \(g\) of \(x\).

We can begin to describe this as code by declaring f and g functions. Here f is a function that accepts a Double an returns a String, while g is a function that accepts an Integer and returns a Double.

val f: (Double) -> String = { x ->
    "$x"
}

val g: (Int) -> Double = { x ->
    x * 1.0
}

We can compose these functions by declaring a new function h that applies the result of f and then g. This creates a new function that accepts an Integer and returns a String.

val h: (Int) -> String = { x -> f(g(x)) }

By composing the functions we've created a new function that's a direct mapping from Integer to String.

We can create a higher order function to generify the process of composing functions easier. Note that the order of the parameters is resolved right to left to match the mathematical notation.

fun <T, U, V> compose(fn2: (U) -> V, fn1: (T) -> U): (T) -> V {
    return { fn2(fn1(it)) }
}

and refactor the previous example to use compose to create h

val h: (Int) -> String = compose(f, g)

Category Theory for Programmers^[1] describes two properties that composition in any category must satisfy.

1. "Composition is associative" - Regardless of how they are grouped by parenthesis, the result should always be the same^[2].

\[ f \circ (g \circ h) = (f \circ g) \circ h = f \circ g \circ h \]

Let's update our example to demonstrate this

val f: (Double) -> String = { x ->
    "$x"
}

val g: (Int) -> Double = { x ->
    x * 1.0
}

val h: (List<Int>) -> Int = {
    it.size
}

We now have 3 functions f, g, and h which have their corresponding implementations. Composing the functions in any pair gives us the same result.

val `f o g o h`: (List<Int>) -> String = {
    f(g(h(x)))
}

val `(f o g) o h`: (List<Int>) -> String = compose(compose(f, g), h)

val `f o (g o h)`: (List<Int>) -> String = compose(f, compose(g, h))

2. "For every object A there is an arrow which is a unit of composition. This arrow loops from the object to itself" - This describes an identity function.

\[ f \circ \text{id}_A = f\]

or

\[ \text{id}_B \circ f = f\]

We can describe an identity \( \text{id}_A \), read identity on A as a mapping to itself.

In code, it's a function that returns the value that is passed to it

fun <T> id(x: T): T {
    return x
}

When composed with another function, we can see that the result is the function it was composed with as expected.

val `f o id`: (Double) -> String = compose(f, ::id)
val `id o f`: (Double) -> String = compose(::id, f)