Kotlin: Function type

Kotlin: Function type

In this blog we introduce the notion of function types. A function type is syntactic sugar for a (function) interface which is not used directly. These function types have a special notation that corresponds to the signature of functions describing their parameter types and their return type.

In this blog we also introduce higher order functions: functions that are parameters to other functions and the results of executing functions. It turns out that they are a highly expressive mechanism for defining behaviors without recourse to more primitive programming constructs such as for loops and if statements. They are a really powerful way of solving problems and thinking about programs.

This material is a precursor to a series of blogs on immutable and persistent data types in Kotlin. The features described here are included in the custom library Dogs consisting of immutable and persistent data types as well as a mix of functional primitives.

Functions

Kotlin supports functions at a number of levels. A function can be declared at package level. We might develop an application in terms of these functions. This might be appropriate for a utility application that performs some simple processing of, say, data stored in a file or spreadsheet. The data might be represented as, say, data classes but the program architecture is procedural.

Functions can also be declared in the body of other functions. Such local functions have a support role to the enclosing function. These nested functions are inaccessible to other parts of the code and so reduce the concepts surrounding the supported function.

Member functions in a class define the behaviors of object instances of that class. Extension functions in Kotlin enable you to add new functions to existing classes without creating a new derived class, recompiling, or otherwise modifying the original class. Extension functions are a special kind of ‘static’ function, but they are called as if they were instance functions on the extended type. For client code there is no apparent difference between calling an extension function and the member functions that are actually defined in a class.

Below are a number of simple functions.

fun increment(n: Int): Int = 1 + n                       // increment: (Int) -> Int
fun negate(n: Int): Int = -n                                 // negate: (Int) -> Int
fun sum(m: Int, n: Int): Int = m + n                    // sum: (Int, Int) -> Int
fun same(text: String, len: Int): Boolean =        // same: (String, Int) -> Boolean
    (text.length == len)

assertEquals(-4, negate(increment(3)))
assertEquals(12, sum(3, sum(4, 5)))
assertEquals(true, same("four  +  nine", 13))



Function types

In Kotlin functions are first class citizens. The implication of this is that a function can be treated like any other object. For example, a String object can be referenced in a value binding, can be passed as the actual parameter in a function call, can be the return value from a function call, can be a property of a class, can be an element of a container such as a List, and can be considered an object instance of the String class and call one of its member functions on it (such as the length member function or the indexOf member function).

These features of a String object are also applicable to a function object.  A function can be referenced in a value binding, can be passed as the actual parameter in a function call or be the return value from a function call (giving rise to higher order functions), can be the property of a class, can be an element of a container such as a List, and can be considered an object instance of some function class and call one of its member functions on it (such as the invoke member function).

Kotlin is a statically typed programming language so we are required to provide the type of each object either explicitly or by type inference. To use a function we must have a way to present a function type. A function type is syntactic sugar for a (function) interface which is not used directly. The syntax of a function type is:

(parameter type, parameter type, …) -> return type

with the left side specifying the function parameter types enclosed in parentheses, and the right side specifying the return type of the function.

These function types have a special notation that corresponds to the signature of functions describing their parameter types and their return type. In the following listing the val bindings for inc, neg and add include these function types.

fun increment(n: Int): Int = 1 + n          // increment: (Int) -> Int

fun negate(n: Int): Int = -n                    // negate: (Int) -> Int

fun sum(m: Int, n: Int): Int = m + n     // sum: (Int, Int) -> Int

val inc: (Int) -> Int = ::increment

val neg: (Int) -> Int = ::negate

val add: (Int, Int) -> Int = ::sum

assertEquals(-4,    negate(increment(3)))

assertEquals(12,    sum(3, sum(4, 5)))

assertEquals(-4,    neg(inc(3)))

assertEquals(12,    add(3, add(4, 5)))

assertEquals(-4,    neg.invoke(inc.invoke(3)))

assertEquals(12,    add.invoke(3, add.invoke(4, 5)))

To obtain an instance of a function type we use a callable reference to an existing function declaration with the expression ::increment which is the value of the function type (Int) -> Int.

There are several other ways to obtain an instance of a function type. Two of the more common are anonymous functions and lambda expressions. An anonymous function (or function expression) has a regular function declaration except its name is omitted. The parameter types and return type are specified as for regular functions. The body of an anonymous function can be an expression or a block. The return type of the anonymous function can be inferred automatically from the function if it is an expression and has to be specified explicitly for the anonymous function if it is a block. Here are some examples:

val isOdd = fun(n: Int): Boolean = (n % 2 == 1)

val isEven: (Int) -> Boolean = fun(n) = (n % 2 == 0)

val add: (Int, Int) -> Int = fun(m: Int, n: Int): Int = (m + n)

val sum: (Int, Int) -> Int = add

assertEquals(true,      isOdd(5))

assertEquals(false,     isEven(5))

assertEquals(7,         add(3, 4))

assertEquals(7,         sum(3, 4))

The val binding isOdd has the regular function declaration (with its name omitted). The val binding for isEven includes a function type so the types of the parameter and the return type can be omitted. The val binding for add redundantly includes both the function type and the function parameter and return type. Finally, the sum val binding includes the function type but this could be omitted as the Kotlin compiler will infer the correct type.

Lambda expressions (or function literals) are essentially anonymous functions that we can treat as values – we can, for example, pass them as arguments to functions, return them, or do any other thing we could do with a normal object. A lambda expression is presented as a code block:

{parameter: type, parameter: type, … -> code body}

where the type can be omitted if it can be inferred. Like anonymous functions, lambda expressions are instances of some appropriate interface with an invoke member function. Then { ... }.invoke(...) executes the function invoke on the lambda expression { ... } and passing the actual parameters ( ... ). Here are some examples:

assertEquals(9, {n: Int -> n * n}.invoke(3))

assertEquals(9, {n: Int -> n * n}(3))        // invoke is inferred

assertEquals(3, {n: Int -> n + 1}(2))        // invoke is inferred

Since a lambda expression is a Kotlin object, then we can bind an identifier to it. The identifier is a reference to that function and the function can be called through the identifier:

val square = {n: Int -> n * n}

val increment = {n: Int -> n + 1}

assertEquals(9,     square.invoke(3))

assertEquals(9,     square(3))            // invoke is inferred

assertEquals(3,     increment(2))    // invoke is inferred

The full syntactic form for binding a lambda expression would be shown by the following example:

val sum: (Int, Int) -> Int = {m: Int, n: Int -> m + n}

The formal parameters are presented exactly as for a normal function: the name and type for each parameter. The lambda expression is enclosed by matching braces and the parameter list and function body is separated by ->.

More commonly we will associate the function type with the bound reference. The parameter types and the return type represent the function type and would look like:

val sum: (Int, Int) -> Int = {m, n -> m + n}

Here, sum is bound to a function that expects two Ints and returns an Int.

Simple as these function type signatures may appear, they are the key to unlocking some of the more advanced programming we shall encounter with functions. The higher-order extension functions for the custom List class are examples of the more powerful capabilities possible with lambda expressions.

The arrow notation in function types is right associative. The function type (String) -> (Int) -> Boolean describes a function that accepts a single String parameter and returns a function with the type (Int) -> Boolean. Since parentheses can be used in function types the latter is equivalent to (String) -> ((Int) -> Boolean). Notice that the function type ((String) -> Int) -> Boolean describes a function that returns a Boolean and take a single function parameter of the type (String) -> Int.

Higher order functions

A function can be passed as a parameter to another function. A function can be the return value from the call to a function. Such functions are called higher order functions. Through functions as parameters and functions as results we are able to fully exploit the machinery of functions, such as function composition. The resulting function declarations can be both more concise and more readable than traditional approaches.

In the following listing function doTwice is a higher order function as it expects a function as its second parameter. The interpretation of the signature for doTwice is that it returns an Int as its value. Two parameters are required, the first of which is an Int. The second parameter is the function parameter. The effect of doTwice is to apply the function twice to the numeric parameter.

fun triple(n: Int): Int = 3 * n                                               // as function

val quadruple: (Int) -> Int = {n -> 4 * n}                            // as lambda expression

val twelveTimes = fun(n: Int): Int = triple(quadruple(n))   // anonymous function

fun doTwice(n: Int, f: (Int) -> Int): Int = f(f(n))

assertEquals(6,     triple(2))

assertEquals(12,    quadruple(3))

assertEquals(36,    twelveTimes(3))

assertEquals(18,    doTwice(2, ::triple))

assertEquals(48,    doTwice(3, quadruple))

assertEquals(144,   doTwice(1, twelveTimes))

assertEquals(75,    doTwice(3, {n -> 5 * n}))

assertEquals(75,    doTwice(3){n -> 5 * n})

Consider a function with two parameters of type String and Int returning a Boolean result. If we are required to partially apply the function (see below) on the Int parameter then we require the Int to be the first parameter. We define a function that takes a binary function as parameter, and which returns a binary function that accepts its parameters in the opposite order. The flip function is declared as:

fun <A, B, C> flip(f: (A, B) -> C): (B, A) -> C =

    {b: B, a: A -> f(a, b)}

We use a lambda expression for the result. The function is defined generically so it can be applied to all parameter types. Function flip is a generic higher order function taking a function parameter and delivering a function result.

fun isSameSize(str: String, n: Int): Boolean = (str.length == n)

val isSame: (Int, String) -> Boolean = flip(::isSameSize)

assertTrue(isSame(3, "Ken"))

assertFalse(isSame(3, "John"))

The function flip is provided by the Dogs custom library. It is defined in the object declaration FunctionF from the com.adt.kotlin.dogs.fp package. It is overloaded to operate on both an uncurried binary function and a curried binary function (see later).

Function composition

Perhaps one of the more important characteristics of functions is composition, wherein you can define one function whose purpose is to combine other functions. Using composition, two or more simple functions can be combined to produce a more elaborate one. For example, suppose we have two arithmetic functions f and g. One way of composing these two functions would be to first compute y, and then to compute z from y, as in y = g(x) followed by z = f(y). One could get the same result with the single composition written z = f(g(x)). We write this as f ● g, meaning function f composed with function g (sometimes also described as f after g).

Function composition lets us compose a solution by combining separately designed and implemented functions. Structuring a large solution into separate functions simplifies the programming activity. The functions can be defined, implemented and tested separately. Simple functions can be used to construct more elaborate functions, reducing the burden and complexity of a system. The functions can also be defined for one application and re-used in other applications.

fun f(n: Int): Int = 2 * n + 3

fun g(n: Int): Int = n * n

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

val fg1: (Int) -> Int = ::f compose ::g

val fg2: (Int) -> Int = ::f o ::g

assertEquals(121,       gf(4))

assertEquals(35,        fg1(4))

assertEquals(35,        fg2(4))

Pay attention to the signature of compose. It is a function that takes two functions as its parameters and returns a function as its result. The second function g accepts an input of the type A and delivers a result of type B. The result is passed as input to the first function f and delivers a result of type C. Hence the composed function has the signature (A) -> C:

    fun <A, B, C> compose(f: (B) -> C, g: (A) -> B): (A) -> C = {a: A -> f(g(a))}

The function compose is provided by the Dogs library. Note the complementary infix functions compose and o. Both are defined as an infix function on the interface that represents the function type (B) -> C. They expects a function parameter with type (A) -> B and composes them using compose to deliver the function (A) -> C.

In the following example function compose is used to compose isEven and strLength. In some circumstances the Kotlin compiler is unable to infer the actual types for the type parameters A, B and C. In that case you must assist the compiler and provide the actual type parameters. This is shown in the call to compose, though in this case it is unnecessary since the compiler correctly infers these types.

fun strLength(str: String): Int = str.length
fun isEven(n: Int): Boolean = (n % 2 == 0)

val strIsEven: (String) -> Boolean = compose(::isEven, ::strLength)

assertEquals(false,     strIsEven("Ken"))
assertEquals(true,      strIsEven("John"))

The order in f compose g is significant and can be confusing: f compose g means apply g and then apply f to the result. The Dogs library also declares the forwardCompose function which takes its parameters in the opposite order to compose:

    fun <A, B, C> forwardCompose(f: (A) -> B, g: (B) -> C): (A) -> C = {a: A -> g(f(a))}

The library also declares the infix forms forwardCompose, fc and pipe:

val successor: (Int) -> Int = {n -> 1 + n}     // as function literal

fun triple(n: Int): Int = 3 * n                         // as function

val quadruple = fun(n: Int): Int = 4 * n        // as function expression

val twelveTimes: (Int) -> Int = compose(::triple, quadruple)

val threePlusOne: (Int) -> Int = ::triple fc successor

assertEquals(60, twelveTimes(5))

assertEquals(16, threePlusOne(5))

val up2: (Int) -> Int = successor o successor

val upDown: (Int) -> Int = successor o {n -> n - 1}

val up2Down2: (Int) -> Int = up2 pipe {n -> n - 2}

assertEquals(5, up2(3))

assertEquals(5, upDown(5))

assertEquals(5, up2Down2(5))

The function type signatures are an important resource in this work. They alert us when compositions would not work. For example, consider that we have the function f: (Int) -> Boolean and the function g: (String) -> Int. The signature for compose tells us compose(f, g) will produce a function with the signature (String) -> Boolean. Equally, the signature reveals that compose(g, f) will not compose correctly.

It is relatively easy to prove that map(f ● g, xs) = (map f ● map g)(xs) for a List xs. Applying f ● g to every element of a list is the same as applying g to every member of the list and then applying f to every member of the resulting list. The equality demonstrates how we might refactor our code to make it more efficient. If our code includes (map f ● map g) then we optimize it with map(f ● g). The former makes one pass across the initial list and then a second pass across the result list. The latter makes only a single pass across the initial list reducing the amount of work to be done.

val f: (Int) -> Int = {n -> 2 * n}
val g: (Int) -> Int = {n -> n + 1}
val map: ((Int) -> Int) -> (List<Int>) -> List<Int> = {f -> {list -> list.map(f)}}

val fg: (Int) -> Int = f compose g
val mapfmapg: (List<Int>) -> List<Int> = map(f) compose map(g)

val numbers: List<Int> = ListF.of(1, 2, 3, 4)

assertEquals(map(fg)(numbers),  mapfmapg(numbers))

Perhaps rather pedantically the full signature for function literals will be given. Kotlin's type inferencing engine would make some parts of the signature unnecessary. Their inclusion is for the benefit of the reader. Their absence may make some of the code opaque to the reader and so the full signatures are retained.

Curried functions

In this section we demonstrate how a single function can effectively define a complete family of functions. Having defined the parent function, we are able to specialize from it a number of related functions. To achieve this we use the notion of currying, named after the mathematician Haskell Curry.

Currying is the process of transforming a function that takes multiple parameters into a function that takes just a single parameter and returns another function which accepts further parameters.

Consider the function add which adds together two Int parameters. Its definition is given by:

fun add(m: Int, n: Int): Int = m + n

The type signature informs us that add is a function which when given a pair of Ints will return an Int. If we were able to call function add and give only one actual parameter, then we would get a result which is itself another function. For example, if we could call add with the parameter 1, then effectively the first formal parameter m is replaced throughout the definition for add with this value. Further, since the value for the parameter m is now specified, then this formal parameter can be removed from the definition. We then effectively produce the function:

fun add1(n: Int): Int = 1 + n

one that takes a single numeric parameter and returns its successor to that value.

In the following listing we declare the add function in the usual way and use it in the first assert. Since a function can be the result for a function, then any multi-parameter function can be converted into a series of one parameter functions. The function sum is defined to operate like add but in its curried form. We execute sum with the call sum(6)(7). Observe how sum10 is defined by calling sum with its first parameter delivering a function that adds 10 to its parameter.

fun add(m: Int, n: Int): Int = m + n

val sum: (Int) -> (Int) -> Int = {m: Int -> {n: Int -> m + n}}

val sum10: (Int) -> Int = sum(10)

assertEquals(7,     add(3, 4))

assertEquals(13,    sum(6)(7))

assertEquals(17,    sum10(7))

Suppose we want to develop a curried version of a binary function f which is uncurried and of the type (A, B) -> C. This binary function f expects its parameters as a pair but its curried version will apply them sequentially. We therefore have to form them into a pair before applying f to them. The custom function C2 does exactly this:

fun <A, B, C> C2(f: (A, B) -> C): (A) -> (B) -> C = {a: A -> {b: B -> f(a, b)}}

Again, the signature reveals what is happening. Function C2 expects a function as its parameter. That parameter function has the signature (A, B) -> C, an uncurried binary function. Function C2 returns the curried variant with the signature (A) -> (B) -> C, as required. We can use C2 where we need to transform an uncurried binary function into its curried form:

fun add(m: Int, n: Int): Int = m + n

val sum: (Int) -> (Int) -> Int = C2(::add)

assertEquals(7,     add(3, 4))

assertEquals(13,    sum(6)(7))

The Dogs library define this function C2 as well as the related functions C3, C4, C5 and C6. The library also includes the complementary functions U2, U3, U4, U5 and U6 to uncurry curried functions.

Partial function application

A key value of curried functions is that they can be partially applied. For example consider the curried binary function sum declared in the earlier example. In the listing the binding sum10 is a function from Int to Int obtained by partially applying the function sum. In effect the function sum10 is defined as:

    val sum10: (Int) -> Int = {n: Int -> 10 + n}

The Dogs library includes a number of variants of the function partial. Here, we are using:

fun <A, B, C> partial(a: A, f: (A) -> (B) -> C): (B) -> C =

    {b: B -> f(a)(b)}

in the following code:

fun add(m: Int, n: Int): Int = m + n

val sum: (Int) -> (Int) -> Int = {m: Int -> {n: Int -> m + n}}

val sum1: (Int) -> Int = partial(1, sum)

val add10: (Int) -> Int = partial(10, ::add)

assertEquals(11,    sum1(10))

assertEquals(12,    add10(2))

Further callable references

A callable reference to an existing function declaration was introduced earlier. A callable reference to a class member function or to a an extension function is also supported. In the following listing the first three val bindings refer to function members of the String class. In the callable reference String::length the function length of class String has no parameters and returns an Int. The function type for this includes the class String as the first function type parameter.

val strLength: (String) -> Int = String::length
val subStr: (String, IntRange) -> String = String::substring
val subStrC: (String) -> (IntRange) -> String = C2(String::substring)

val crop: (String) -> String = String::trim
val clip: (String, (Char) -> Boolean) -> String = String::trim

val take: (Int) -> (String) -> String = flip(C2(String::take))
val take4: (String) -> String = take(4)

assertEquals(3,     strLength("Ken"))
assertEquals("nn",  subStr("Kenneth", 2..3))
assertEquals("nn",  subStrC("Kenneth")(2..3))

assertEquals("ken", crop("   ken "))
assertEquals("ken", clip("123ken4", Character::isDigit))

assertEquals("Kenn",    take4("Kenneth"))
assertEquals("Barc",    take4("Barclay"))

The callable reference operator :: can also be used with overloaded functions when the expected type is known from the context. This is shown using the overloaded substring function from class String.

At the time of writing (April 2020) there are some problems when using callable references to function members of a generic class. Workarounds are possible and need to be used.



Case Study

This example includes a number of individual functions which together compile the index of the words in a text document. The index is an alphabetical list of the words and, for each word, the line numbers in the document on which it appears. The solution is a composition of the functions that perform the various operations on the text.

We start by introducing a number of aliases that make it easier to interpret the signatures of the various functions:

typealias Document = String
typealias Line = String
typealias Word = String
typealias Number = Int
typealias LineNumber = Pair<Line, Number>
typealias WordNumber = Pair<Word, Number>
typealias WordNumbers = Pair<Word, List<Number>>

The use of Document, Line and Word, for example, help to distinguish how a String is being used.

We start with a Document and break it into one or more Line at the line breaks. The function to do this is called lines and has the signature:

    fun lines(document: Document): List<Line>

Once we have the lines from the document we use the function numberedLines to convert each Line to a LineNumber, pairing the line with its line number:

    fun numberedLines(lines: List<Line>): List<LineNumber>

At this point we have the means to convert a document into its lines and their corresponding line number:

    ::lines pipe ::numberedLines

The next task is to break the numbered lines into words numbered with their line number:

    fun numberedWords(lines: List<LineNumber>): List<WordNumber>

This function additionally transforms each word to lowercase so that, for example, all the 'anonymous' and 'Anonymous' are considered identical. To group the word number pairs we sort them:

    fun sort(numberedWords: List<WordNumber>): List<WordNumber>

then merge the line numbers of adjacent matching words:

    fun merge(words: List<WordNumber>): List<WordNumbers>

Finally we provide the means whereby we select the first n elements:

    val take: (Int) -> (List<WordNumbers>) -> List<WordNumbers>

Now we can define:

fun wordConcordance(n: Int): (Document) -> List<WordNumbers> =
    ::lines pipe ::numberedLines pipe ::numberedWords pipe ::sort pipe ::merge pipe take(n)

The declaration of wordConcordance is a pipeline of six component functions glued through functional composition.

We run our code against the following document:

There are several other ways to obtain an instance of a function type
Two of the more common are anonymous functions and lambda expressions
An anonymous function or function expression has a regular function
declaration except its name is omitted The parameter types and return
type are specified as for regular functions The body of an anonymous
function can be an expression or a block The return type of the anonymous
function can be inferred automatically from the function if it is an expression
and has to be specified explicitly for the anonymous function if it is a block

Executing concordance(7)(document) and printing the result delivers:

    <[(a, <[1, 3, 6, 8]>), (an, <[1, 3, 5, 6, 7]>), (and, <[2, 4, 8]>), (anonymous, <[2, 3, 5, 6, 8]>), (are, <[1, 2, 5]>), ... ]>

showing the word 'anonymous' appearing on lines 2, 3, 5, 6 and 8.

If we run concordance(4)(document) we have the following correct assertion:

assertEquals(
    ListF.of(
        WordNumbers("a", ListF.of(1, 3, 6, 8)),
        WordNumbers("an", ListF.of(1, 3, 5, 6, 7)),
        WordNumbers("and", ListF.of(2, 4, 8)),
        WordNumbers("anonymous", ListF.of(2, 3, 5, 6, 8))
    ),
    concordance
)

Here, our aim was to build a concordance of the words in a document, namely, a pairing of each word and the line numbers on which it appears. The Dogs library includes the MultiMap data type - a MultiMap is a special kind of Map: one that allows a collection of elements to be associated with each key. Using a MultiMap would have simplified this solution.

This simple idea scales to the more realistic business problem of an order taking system for a  manufacturing company. The workflow for the order taking system can be broken into smaller and simpler stages: validation, pricing, etc. We can create a pipeline to represent the business process as:

class UnvalidatedOrder

class ValidatedOrder

class PricedOrder

class CompletedOrder

fun validateOrder(uvo: UnvalidatedOrder): ValidatedOrder = TODO()

fun priceOrder(vo: ValidatedOrder): PricedOrder = TODO()

fun completeOrder(po: PricedOrder): CompletedOrder = TODO()

val placeOrder: (UnvalidatedOrder) -> CompletedOrder = ::validateOrder pipe ::priceOrder pipe ::completeOrder

Of course, any of the stages might give rise to some sort of failure. For example, when validating an order we might find the unvalidated order may have omitted the quantity for an order item or referenced an unknown item and we will have to consider how to address failure.

The code for the Dogs library can be found at:

https://github.com/KenBarclay/TBA

Kotlin: Pattern matching

The past year I have evolved a simple pattern matching scheme that I now automatically incorporate into new Kotlin class hierarchies. The scheme is trivial to include, costs nothing to program and offers some beneficial features. Its development is thanks to the many nice features offered by Kotlin.

Consider the development of an immutable list type. The architecture comprises the trait ListIF, the abstract class ListAB, and the two concrete classes Nil and Cons. The ListIF trait operates as an interface, introducing the behaviours supported. The abstract class ListAB is the home for the implementation of most of the common behaviours. The concrete classes Nil and Cons are used to create list instances.

The implementation for this architecture is shown in Example 1. Note the match member function introduced in the trait. This is the pattern matching scheme for this class hierarchy. The function is given two parameters, one for each concrete class. The first parameter is a function to convert a Nil into the result type B. The second parameter is a function from a Cons to the result type B.

The concrete subclasses Nil and Cons override the definition for match. In the class Nil the first parameter is invoked against the Nil instance. In the class Cons the second parameter is invoked against the Cons instance. This pattern matching scheme is effectively the strategy design pattern.

Example 1: Pattern matching

package example1

import kotlin.test.*

trait ListIF<A> {
    fun size(): Int
    fun length(): Int
    fun interleave(xs: ListIF<A>): ListIF<A>

    fun <B> match(nil: (Nil<A>) -> B, cons: (Cons<A>) -> B): B
}

abstract class ListAB<A> : ListIF<A> {
    override fun size(): Int {...}

    override fun length(): Int {...}
    
    override fun interleave(xs: ListIF<A>): ListIF<A> {...}
}

class Nil<A> : ListAB<A>() {
    override fun <B> match(nil: (Nil<A>) -> B, cons: (Cons<A>) -> B): B = nil(this)
}

class Cons<A>(val hd: A, val tl: ListIF<A>) : ListAB<A>() {
    override fun <B> match(nil: (Nil<A>) -> B, cons: (Cons<A>) -> B): B = cons(this)
}

fun main(args: Array<String>) {
    val xs: ListIF<Int> = Cons(1, Cons(3, Cons(5, Nil<Int>())))
    val ys: ListIF<Int> = Cons(2, Cons(4, Nil<Int>()))

    assertEquals(3, xs.size())
    assertEquals(2, ys.length())
    assertEquals(4, xs.interleave(ys).length())
}

The definition for member function size is:

override fun size(): Int {

    return this.match(

        {(nil: Nil<A>) -> 0},

        {(cons: Cons<A>) -> 1 + cons.tl.size()}

    )

}

A match is performed against the recipient list and if it is empty then zero is returned. If the list is non empty then we return 1 plus the size of the remaining list. Of course we could achieve the same using a when clause and a number of is selector clauses. However, it is incumbent on the programmer to provide all the necessary choices. With the match function if you omit a choice you get a compiler error.

The second function literal given to match reveals another feature. The formal parameter cons is of type Cons and is effectively a smart cast of this. Hence in the body of this function literal we can reference the tl property of cons.

The definition for member function interleave shows how we handle nested pattern matching:

override fun interleave(xs: ListIF<A>): ListIF<A> {

    return this.match(

        {(nil1: Nil<A>) -> Nil<A>()},

        {(cons1: Cons<A>) ->

            xs.match(

                {(nil2: Nil<A>) -> Nil<A>()},

                {(cons2: Cons<A>) -> Cons(cons1.hd, Cons(cons2.hd, cons1.tl.interleave(cons2.tl)))}

            )

        }

    )

}

Interleaving the values from two lists requires a number of considerations. They are fully captured by the nested pattern matching. If the first list (this) is empty then an empty list is delivered. If the first list is not empty then we look to the second list (xs). If this is empty then an empty list is returned. Otherwise, for two non empty lists we prefix the head of the first and the head of the second on to interleaving their tails. As well as a type safe implementation of our logic it also allows us to reason about its correctness before we test it.

The recursive definition of the list data type naturally leads to a recursive definition of the classes and its member functions. Here is member function length:

override fun length(): Int {

    fun recLength(xs: ListIF<A>, acc: Int): Int {

        return xs.match(

            {(nil: Nil<A>) -> acc},

            {(cons: Cons<A>) -> recLength(cons.tl, 1 + acc)}

        )

    }

    return recLength(this, 0)

}

The nested function recLength has an accumulating parameter so that the recursive call might exploit tail call optimization. If I understand the Kotlin annotation tailRecursive this does not apply here since the recursive call is nested in the function literal. Perhaps the clever people at IntelliJ could find a way so that I can have my cake and eat it.

Of course not all my class hierarchies are defined recursively and so this issue does not arise. The pattern matching scheme is inexpensive to implement, is type safe, supports smart casts and a clarity in function bodies that we can reason about their correctness.

Kotlin: An Option type #2

The first blog introduced the OptionIF<T> trait and some of the supporting member functions. The package level functions inject and bind are used to make the OptionIF<T> trait into a monad. A monad is a way to structure computations in terms of values and sequences of computations using those values. Monads allow the programmer to build up computations using sequential building blocks, which can themselves be sequences of computations. The monad determines how combined computations form a new computation and frees the programmer from having to code the combination manually each time it is required. It is useful to think of a monad as a strategy for combining computations into more complex computations. The inject and bind functions have the signatures:

fun <T> inject(t: T): OptionIF<T>
fun <T, V> bind(op: OptionIF<T>, f: (T) -> OptionIF<V>): OptionIF<V>

The inject function is simply a factory method to create an instance of OptionIF<T>.

The basic intuition behind the bind operation is that it allows us to combine two computations into one more complex computation and allows them to interact with one another. The first parameter type OptionIF<T> represents the first computation. Significantly, the second parameter type is T -> OptionIF<V> which can, given the result of the first computation, produce a second computation to run. In other words bind(op){t -> ... } is a computation which runs op and binds the value wrapped in op to the function literal parameter t. The function body then decides what computation to run using the value for t.

Example 5 demonstrated the map member function of OptionIF<T>. Example 6 shows how we might achieve the same using inject and bind. The mapped function applies the function parameter f to the content of the option type parameter op. Significantly the definition of mapped does not have to distinguish between the concrete OptionIF<A> types of op.

Example 6: The monadic option type

package example6

import kotlin.test.*

import com.adt.kotlin.data.immutable.option.*

fun <A, B> mapped(f: (A) -> B, op: OptionIF<A>): OptionIF<B> = bind(op){(a: A) -> inject(f(a))}

fun main(args: Array<String>) {

    val name: OptionIF<String> = Some("Ken Barclay")

    val absentName: OptionIF<String> = None<String>()

    assertEquals(Some(11), mapped({(str: String) -> str.length()}, name))

    assertEquals(None<Int>(), mapped({str -> str.length()}, absentName))

}

Example 7 demonstrates how we might use the monadic option type. Running the program with the inputs 18, 27 and 9 delivers the result Some(Pair(2, 3)), demonstrating that 18 and 27 are exactly divisible by 9. The inputs 18, 27 and 6 produce the result None, showing that 18 and 27 and not both exactly divisible by 6.

Example 7: Staircasing

package example7

import kotlin.test.*
import com.adt.kotlin.data.immutable.option.*

fun divide(num: Int, den: Int): OptionIF<Int> {
    return if (num % den != 0) None<Int>() else Some(num / den)
}

fun division(a: Int, b: Int, c: Int): OptionIF<Pair<Int, Int>> {
    val ac: OptionIF<Int> = divide(a, c)
    return when (ac) {
        is None<Int> -> None<Pair<Int, Int>>()
        is Some<Int> -> {
            val bc: OptionIF<Int> = divide(b, c)
            when (bc) {
                is None<Int> -> None<Pair<Int, Int>>()
                is Some<Int> -> Some(Pair(ac.get(), bc.get()))
                else -> None<Pair<Int, Int>>()
            }
        }
        else -> None<Pair<Int, Int>>()
    }
}

fun bindDivision(a: Int, b: Int, c: Int): OptionIF<Pair<Int, Int>> {
    return bind(divide(a, c)){(ac: Int) -> bind(divide(b, c)){(bc: Int) -> inject(Pair(ac, bc))}}
}

fun main(args: Array<String>) {
    assertEquals(Some(Pair(2, 3)), division(18, 27, 9))
    assertEquals(None<Pair<Int, Int>>(), division(18, 27, 6))
    assertEquals(Some(Pair(2, 3)), bindDivision(18, 27, 9))
    assertEquals(None<Pair<Int, Int>>(), bindDivision(18, 27, 6))
}

Function division threatens to march off to the right side of the listing if it became any more complicated. It is very typical imperative code that is crying out for some refactoring.

We can bring the staircasing effect under control with bind. Consider the implementation of bindDivision. The outer call to bind(divide(a, c)){ ac -> ...} has an OptionIF value produced from the expression divide(a, c). Should this be a Some value, then the function literal is called and its formal parameter ac is bound to the result from the Some value. In the inner call bind(divide(b, c)){ bc -> ...} the inner function literal is called with the formal parameter bc bound to the Some value produced from divide(b, c). If the two calls to divide both deliver Some values then a final Some result is produced carrying the pair we seek. If a None value is delivered by either call to divide then a None value is the final result.

This simplification is also present in the two following examples. Often we make lookups of a map data structure, a database or a web service and receive an optional response. In some scenarios we take the result of a first lookup and use it to perform a second lookup. Example 8a is an application based on a set of products differentiated by a unique code. The products are organized by country, city, supplier and code. A product stock is realized by overlapping maps.

The immutable MapIF<K, V> trait and its lookUpKey member function provide the implementation. The function getProductFrom aims to deliver a Product given the country, city, supplier and code, and the product stock:

fun getProductFrom(country: String, ...,
productsByCountry: MapIF<String, MapIF<String, MapIF<String, MapIF<String, Product>>>>): OptionIF<Product>

The product, if it exists, is obtained by making repeated lookUpKey function calls down through the nested maps. If anyone fails than we bail out with None<Product>.

Example 8a: Product searching

package example8a

import kotlin.test.*
import com.adt.kotlin.data.immutable.option.*
import com.adt.kotlin.data.immutable.map.*

data class Product(val code: String, val name: String)

fun getProductFrom(country: String, city: String, supplier: String, code: String, productsByCountry: MapIF<String, MapIF<String, MapIF<String, MapIF<String, Product>>>>): OptionIF<Product> {
    val productsByCity: OptionIF<MapIF<String, MapIF<String, MapIF<String, Product>>>> = productsByCountry.lookUpKey(country)
    if (productsByCity.isDefined()) {
        val productsBySupplier: OptionIF<MapIF<String, MapIF<String, Product>>> = productsByCity.get().lookUpKey(city)
        if (productsBySupplier.isDefined()) {
            val productsByCode: OptionIF<MapIF<String, Product>> = productsBySupplier.get().lookUpKey(supplier)
            if (productsByCode.isDefined()) {
                return productsByCode.get().lookUpKey(code)
            } else
                return None<Product>()
        } else
            return None<Product>()
    } else
        return None<Product>()
}

// By country, by city, by supplier and by code
val productsByCountry: MapIF<String, MapIF<String, MapIF<String, MapIF<String, Product>>>> =
        fromSequence(
                "USA" to fromSequence(
                        "San Francisco" to fromSequence(
                                "Graham" to fromSequence(
                                        "SH" to Product("SH", "Shiraz"),
                                        "ZI" to Product("ZI", "Zinfandel")
                                )
                        )
                ),
                "France" to fromSequence(
                        "Bordeaux" to fromSequence(
                                "Jacques" to fromSequence(
                                        "SE" to Product("SE", "Saint Emilion"),
                                        "ME" to Product("ME", "Medoc")
                                )
                        ),
                        "Beaune" to fromSequence(
                                "Marcel" to fromSequence(
                                        "AC" to Product("AC", "Aloxe-Corton"),
                                        "ME" to Product("ME", "Mersault"),
                                        "PO" to Product("PO", "Pommard"),
                                        "SA" to Product("SA", "Savigny"),
                                        "VO" to Product("VO", "Volnay")
                                )
                        )
                )
        )

fun main(args: Array<String>) {
    assertEquals(Some(Product("PO", "Pommard")), getProductFrom("France", "Beaune", "Marcel", "PO", productsByCountry))
    assertEquals(Some(Product("SH", "Shiraz")), getProductFrom("USA", "San Francisco", "Graham", "SH", productsByCountry))
    assertEquals(None<Product>(), getProductFrom("France", "Beaune", "Marcel", "ZZ", productsByCountry))

}

The implementation of function getProductFrom just does not look great. It looks ugly and not code you want to be associated with in your place of work.

However, since our OptionIF<T> is monadic, we can sequence the lookUpKey calls much more gracefully. The implementation of the function getProductFrom in Example 8b is now much simpler and is reminiscent of the bindDivision function from Example 7.

Example 8b: Product searching

package example8b

import kotlin.test.*
import com.adt.kotlin.data.immutable.option.*
import com.adt.kotlin.data.immutable.map.*

data class Product(val code: String, val name: String)

fun getProductFrom(country: String, city: String, supplier: String, code: String, productsByCountry: MapIF<String, MapIF<String, MapIF<String, MapIF<String, Product>>>>): OptionIF<Product> {
    return bind(productsByCountry.lookUpKey(country)) {productsByCity ->
        bind(productsByCity.lookUpKey(city)){productsBySupplier ->
            bind(productsBySupplier.lookUpKey(supplier)){productsByCode ->
                productsByCode.lookUpKey(code)
            }
        }
    }
}

// By country, by city, by supplier and by code
val productsByCountry: MapIF<String, MapIF<String, MapIF<String, MapIF<String, Product>>>> = ...

fun main(args: Array<String>) {
    assertEquals(Some(Product("PO", "Pommard")), getProductFrom("France", "Beaune", "Marcel", "PO", productsByCountry))
    assertEquals(Some(Product("SH", "Shiraz")), getProductFrom("USA", "San Francisco", "Graham", "SH", productsByCountry))
    assertEquals(None<Product>(), getProductFrom("France", "Beaune", "Marcel", "ZZ", productsByCountry))
}

Alongside the OptionIF<T> trait and its concrete classes None<T> and Some<T> there are a number of package level utility functions that make working with options very easy and natural. The sequenceM function combines a list of monadic options into one option monad that has a list of the results of those options inside it:

fun <T> sequenceM(bs: ListIF<OptionIF<T>>): OptionIF<ListIF<T>>

Example 9 demonstrates how this might be used. Consider we have a MapIF<String, Int> for the frequency distribution of words in a document, and a ListIF<String> of words whose total occurrences we wish to obtain.

Example 9: Utility function sequenceM

package example9

import kotlin.test.*
import com.adt.kotlin.data.immutable.option.*
import com.adt.kotlin.data.immutable.list.*
import com.adt.kotlin.data.immutable.map.*

val frequencies: MapIF<String, Int> = fromSequence(
        "software" to 5,
        "engineering" to 3,
        "kotlin" to 9,
        "object" to 8,
        "oriented" to 3,
        "functional" to 3,
        "programming" to 20
)
val words: ListIF<String> = fromSequence("object", "functional")

fun getWordFrequencies(words: ListIF<String>, frequencies: MapIF<String, Int>): ListIF<OptionIF<Int>> =
        words.map{(word: String) -> frequencies.lookUpKey(word)}

fun distributions(frequency: ListIF<OptionIF<Int>>): Int {
    fun ListIF<Int>.sum(): Int = this.foldLeft(0){(res: Int) -> {(elem: Int) -> res + elem}}
    val freq: OptionIF<ListIF<Int>> = sequenceM(frequency)
    return freq.getOrElse(emptyList<Int>()).sum()
}

fun main(args: Array<String>) {
    val wordFrequencies: ListIF<OptionIF<Int>> = getWordFrequencies(words, frequencies)
    val dist: Int = distributions(wordFrequencies)
    assertEquals(11, dist)
}

Given the words and the frequencies the function getWordFrequencies maps each word into a ListIF of OptionIF<Int> through application of the lookUpKey member function. The function distributions then finds the total occurences in the ListIF<Int> (wrapped in an OptionIF) obtained from sequenceM. Note that if any of the OptionIF<Int> in the ListIF passed to sequenceM is a None<Int> then a None<ListIF<Int>> is returned.

The OptionIF<T> provides a type for representing optional values. It also acted as a vehicle for demonstrating powerful abstractions that can hide mundane implementation details. Using higher order abstractions such as higher order functions, monads, etc. we can simplify the implementation of function bodies. 

These observations have inspired me to reconsider how I implement function logic. I aim to reduce the complexity of function bodies by reducing or removing my use of control structures such as if statements nested in while statements, representative of much of my existing imperative code. By presenting function bodies as simple sequential actions they are much easier to write and much easier to reason about their correctness. Functions that are much more trustworthy. Functions such as bindDivision and distributions are simple illustrations of what I seek to achieve.

Kotlin: An Option type #1

This pair of blogs introduces the Kotlin Option type that allows the programmer to specify where something is present or absent. It can be used in place of null to denote absence of a result. The Option type offers more than a new data type: more powerful abstractions, such as higher order functions, that hide many of the details of mundane operations such as mapping a function across a data type. We get to focus on the what, not the how making our code more declarative: incentivizing us to make our code blocks simpler.

Probably all Java developers have experienced a NullPointerException. Usually this occurs because some function returns it when not expected and when not dealing with that possibility in your client code. The value null is also used to represent the absence of a value such as when performing the member function get on a Map.

Kotlin, of course, allows you to work safely with null. The null-safe operator for accessing properties is foo?.bar?.baz will not throw an exception if either foo or its bar property is null. Instead, it returns null as its result.

An alternative approach that seeks to reduce the need for null is to provide a type for representing optional values, i.e. values that may be present or not: the OptionIF<T> trait. By stating that a value may or mat not be present on the type level, you and other developers are required by the compiler to deal with this possibility. Further, by providing various combinators we can chain together function calls on option values.

Kotlin OptionIF<T> is a container for zero or one element of a given type. An OptionIF<T> can be either a Some<T> wrapping a value of type T, or can be a None<T> which represents a missing value. You create an OptionIF<T> by instantiating the Some or None classes:

val name: OptionIF<String> = Some("Ken Barclay")
val absentName: OptionIF<String> = None<String>()

Given an instance of OptionIF<T> and the need to do something with it, how is this done? One way would be to check if a value is present by means of the isDefined member function, and if that is the case obtain the value with the get member function. This is shown in Example 1.

Example 1: Accessing options

package example1

import com.adt.kotlin.data.immutable.option.*

fun main(args: Array<String>) {
    val op: OptionIF<Int> = Some(5)
    if (op.isDefined())
        println("op: ${op.get()}")  // => op: 5
}

Deliberately, I have chosen to include types explicitly as an aid to the reader. Of course, Kotlin's type inferencing would allow me to omit some and, in turn, make the code more compact.

The most common way to take optional values apart is through a pattern match. Example 2 introduces the show function which pattern matches on the OptionIF parameter and for a Some instance the member function get is used to retrieve the enclosed value.

Example 2: Pattern matching options

package example2

import com.adt.kotlin.data.immutable.option.*

fun show(op: OptionIF<String>) {
    when (op) {
        is Some<*> -> println(op.get())
        else -> println("Missing")
    }
}

fun main(args: Array<String>) {
    val name: OptionIF<String> = Some("Ken Barclay")
    val absentName: OptionIF<String> = None<String>()

    show(name)              // => Ken Barclay
    show(absentName)    // => Missing
}

If you think this is clunky and expect something more elegant from Kotlin OptionIF<T> you are correct. If you use the member function get, you may forget about checking with isDefined leading to a runtime exception, and this scenario is no different from using null. You should avoid using options this way. One simple improvement we can make to these use cases is provided by the getOrElse member function as shown in Example 3.

Example 3: Provide a default

package example3

import com.adt.kotlin.data.immutable.option.*

fun main(args: Array<String>) {
    val name: OptionIF<String> = Some("Ken Barclay")
    val absentName: OptionIF<String> = None<String>()

    println(name.getOrElse("Missing"))              // => Ken Barclay
    println(absentName.getOrElse("Missing"))    // => Missing

}

I suggested that we consider an option as a collection of zero or one elements. Consequently it is provided with many of the behaviors we associate with containers such as filtering, mapping and folding. Example 4 illustrates transforming an OptionIF<String> into an OptionIF<Int>. When you map an OptionIF<String> that is a None<String> then you get a None<Int>.

Example 4: Mapping

package example4

import com.adt.kotlin.data.immutable.option.*

fun main(args: Array<String>) {
    val name: OptionIF<String> = Some("Ken Barclay")
    val absentName: OptionIF<String> = None<String>()

    println(name.map{(str: String) -> str.length()}.getOrElse(0))         // => 11
    println(absentName.map{str -> str.length()}.getOrElse(0))           // => 0
}

The member function map is a higher order function, accepting a transformer function as parameter. Using customizable higher order functions allows us to think about solutions differently. Function map allows us to apply a generic operation to the data type and means we can focus on the result.

A somewhat more elaborate illustration is given in Example 5 which implements a repository of users. We need to be able to find a user by their unique id. A request made with a non-existent id suggests a return type of OptionIF<User>.

Example 5: User repository

package example5

import com.adt.kotlin.data.immutable.option.*

class User(val id: Int, val firstName: String, val lastName: String, val age: Int)

class UserRepository {

    fun findById(id: Int): OptionIF<User> {

        return if (users.containsKey(id)) {

            val user: User = users.get(id)!!

            Some(user)

        } else

            None<User>()

    }

// ---------- properties ----------------------------------

    val users: Map<Int, User> = hashMapOf(

            1 to User(1, "Ken", "Barclay", 25),

            2 to User(2, "John", "Savage", 31)

    )

}

fun main(args: Array<String>) {

    val repository: UserRepository = UserRepository()

    val user: OptionIF<User> = repository.findById(1)

    val userName: OptionIF<String> = user.map{u -> "${u.firstName} ${u.lastName}"}

    if (userName.isDefined())

        println("User: ${userName.get()}")      // => User: Ken Barclay

}

Our dummy implementation uses a HashMap. Perhaps we might develop a Map<K, V> implementation with a lookUpKey member function that returns an OptionIF<V>.

In the follow-on blog I will consider some more advanced use-cases with OptionIF<T>. I aim to show how more powerful abstractions over the OptionIF<T> type can reduce the complexity of functions, encouraging us to cede control to these abstractions and remove the need to code each atomic step in an algorithm.