Kotlin: Property Based Testing

Kotlin: Property Based Testing

In this blog we introduce property based testing, how it works, show where it might fit into your testing strategy, and walk you through building property based tests with the custom KwikCheck testing framework. In the follow-on blog we look at property based testing of immutable and persistent data structures and property based testing of stateful systems.

In traditional unit testing, you run your code with specific inputs and check that you get the expected outputs. This means you need to anticipate possible problematic inputs in advance. In the following illustration we unit test a newly developed sort function by trying it with a list of mixed values; a list where the values are already in sort order; a list with duplicates present; a singleton list and an empty list. With the correct results produced we declare our function correct.

sort([4, 2, 7, 3, 1]) == [1, 2, 3, 4, 7]
sort([1, 2, 3, 4, 7]) == [1, 2, 3, 4, 7]
sort([4, 2, 7, 2, 1]) == [1, 2, 2, 4, 7]
sort([7]) == [7]
sort([]) == []

One of the challenges of traditional unit testing is that it represents example based testing. Each unit test essentially establishes specific input data points, runs the code under test, and then checks the output. Writing many of these tests does not mean we will account for all possible behaviors. As the complexity of our software grows so does the probability that we will fail to account for a key scenario.

Property-based testing is a technique where your tests describe the properties and behavior you expect your code to have, and the testing framework tries to find inputs that violate those expectations. Rather than testing a function against specific inputs we try to reason about its behavior over a range of inputs.

Test properties are presented as logical propositions. For example, the stack data type is our standard last-in-first-out data store. Operation push injects a new element on to the stack top, while operation top delivers the item at the stack top. For all stack st and all element el the following proposition is a statement that affirms or denies the predicate:

top(push(el, st)) == el

We test this property embedded in a Unit test framework. The forAll function accepts a generator that produces a randomized stack containing randomized integer values, and a generator that delivers randomized integer values. The generated stack and the generated integer are captured in the lambda parameter to forAll as st and el respectively. Function prop expects a predicate for our logical proposition and wraps it into a Property instance. Function check then runs the test and delivers a CheckResult value which, since we are using a Unit test harness, we can complete with an assert.

@Test fun stackOperation() {
    val property = forAll(genStack(genInt), genInt) { st, el ->
        prop(st.push(el).top() == el)
    }
    val checkResult: CheckResult = property.check()
    //assertTrue(checkResult.isPassed())
    println(checkResult.summary())
}

However, for the purpose of this blog, it is more convenient to print the result from the function summary:

OK, passed 100 tests

which informs us that 100 (the default) tests were generated and that the property holds.

Property-based testing was popularized by the Haskell library QuickCheck. You specify properties of your code that should hold regardless of input. QuickCheck then randomly generates the input data to try to find a case for which the property fails. This form of testing became known as property based testing and is actually the principal form of testing in the Haskell ecosystem.

The KwikCheck test framework for Kotlin (as described here) is modeled after the QuickCheck framework. Property-based testing is generative testing. You do not supply specific example inputs with expected outputs as with unit tests. Instead, you define properties about the code and use the generative-testing engine to create randomized inputs to ensure the defined properties are correct. KwikCheck allows us to express these properties and generate the randomized inputs.

Automated test generation means, if you've got a function that operates on a particular input, you specify a property (or several properties) about that function, and then generators will give you variations on the input data to test the function, the edge cases, etc., and tell you whether the property holds. You can use the default generators for known types provided by KwikCheck, or define your own.

Test properties are presented as logical propositions. Examples include:

!P || !Q == !(P && Q)

(S1 + S2).endsWith(S2)

L.reverse().reverse() == L

L1.reverse().zip(L2.reverse()) == L1.zip(L2).reverse()     // UNTRUE

The first example is De Morgan's law which relates conjunctions and disjunctions of propositions through negation (where P and Q are boolean values). The second example claims that the concatenation of the strings S1 and S2 will end with the string S2. The third example specifies that if we reverse a list L then reverse the result it will deliver the original list. The fourth example, while untrue, can look correct especially if unit tested with a few examples. It involves zipping and reversing two lists.

Here is how KwikCheck expresses the second example above:

@Test fun endsWithOperation() {

    val genStr1: Gen<String> = genString

    val genStr2: Gen<String> = genString

    val prop: Property = forAll(genStr1, genStr2){str1, str2 ->

        prop((str1 + str2).endsWith(str2))

    }

    val checkResult: CheckResult = prop.check()

    println(checkResult.summary())

}

with the output:

OK, passed 100 tests

Here is the fourth example above:

@Test fun reverseZipOperation() {
    val genInt: Gen<Int> = choose(1, 10)
    val genIntList: Gen<List<Int>> = genList(genInt)
    val genAlpha: Gen<Char> = genAlphaUpperChar
    val genAlphaList: Gen<List<Char>> = genList(genAlpha)

    val property = forAll(genIntList, genAlphaList) { xs, ys ->
        prop(xs.reverse().zip(ys.reverse()) == xs.zip(ys).reverse())
    }
    val checkResult: CheckResult = property.check()
    println(checkResult.summary())
}

It is, of course, a failing test and KwikCheck displays the counter-example:

Falsified after 4 passed tests with (<[10]>, <[C, R]>)

which informs us that four generated tests were initially successful but when tested with the two lists shown the property failed. The example is using the immutable and persistent List class from the custom library KData noted at the end of this article.

Properties which are simple equations are conveniently represented by booleans. Many laws, however, only hold under certain conditions. KwikCheck provides an implication combinator to represent such conditionals. In the following the law that if m <= n then the max(m, n) is n:

@Test fun conditionalOperation() {
    val property = forAll(genInt, genInt){m, n ->
        (m <= n) implies prop(max(m, n) == n)
    }
    val checkResult: CheckResult = property.check()
    println(checkResult.summary())
}

The output is:

OK, passed 100 tests (105 discarded)

and reveals the condition was not met on 105 occasions.

We can also combine existing properties into new ones using the and and or combinators. In the following we incorrectly define function mul. Three separate properties are combined to test the result from applying function mul.

@Test fun combiningOperation() {

    fun mul(m: Int, n: Int): Int = m + n    // ERROR

    val property = forAll(choose(1, 10), choose(101, 110)){m, n ->

        val res = mul(m, n)

        prop(res >= m) and prop(res >= n) and prop(res < m + n)

    }

    val checkResult: CheckResult = property.check()

    println(checkResult.summary())

}

This fails immediately with m = 3 and n = 108:

Falsified after 0 passed tests with (3, 108)

Complex properties with many conditions can make it difficult to decide exactly what is wrong when a property fails. The next example repeats the previous example, labeling the individual properties. The output reveals the first test fails because the result does not sum.

@Test fun labellingOperation() {

    fun mul(m: Int, n: Int): Int = m + n    // ERROR

    val property = forAll(choose(1, 10), choose(101, 110)){m, n ->

        val res = mul(m, n)

        prop(res >= m).label("res >= m") and

                prop(res >= n).label("res >= n") and

                prop(res < m + n).label("result not sum")

    }

    val checkResult: CheckResult = property.check()

    println(checkResult.summary())

}

Output:

Falsified after 0 passed tests with (7, 109)

Labels of failing property: result not sum

KwikCheck supports collecting statistics about the test data that has been generated during property evaluation. This is useful for inspecting test case generation and ensuring all cases are tested and not simply trivial ones. The next example operates on an ordered list and the property we check is that if the list is ordered then the insert function maintains that ordering.

@Test fun collectSortedListOperation() {

    fun insert(n: Int, list: List<Int>): List<Int> =

        when (list) {

            is List.Nil -> ListF.singleton(n)

            is List.Cons -> if (n < list.head())

                ListF.cons(n, list)

            else

                ListF.cons(list.head(), insert(n, list.tail()))

        }   // insert

    fun isOrdered(list: List<Int>): Boolean =

        if (list.isEmpty())

            true

        else

            list.zip(list.drop(1)).forAll{pr -> (pr.first <= pr.second)}

    val property = forAll(genInt, genList(genInt)){n, list ->

        isOrdered(list) implies prop(isOrdered(insert(n, list))).collect(list.size())

    }

    val checkResult: CheckResult = property.check(maxDiscarded = 10000)

    println(checkResult.summary())

}

Here, the property is not tested with large lists since they are all randomly generated. Lists of size 0, 1, 2, 3 and 4 have been tested. The output suggests we need a special List generator that generates large ordered lists.

OK, passed 100 tests (3340 discarded)

Collected test data:

42% 0

31% 1

19% 2

7% 3

1% 4

The classify combinator does not change the meaning of a property but classifies some of the test cases. Here, those lists with size greater than 5 are classified as large and the others classified as small.

@Test fun classifyReverseListOperation() {

    val property = forAll(genList(genInt)) {list->

        prop(list.reverse().reverse() == list).classify(list.size() > 5, "large", "small")

    }

    val checkResult: CheckResult = property.check(maxDiscarded = 10000)

    println(checkResult.summary())

}

The output is:

OK, passed 100 tests

Collected test data:

73% large

27% small

The core of the KwikCheck library comprises the classes Gen<A> and Property. The class Gen<A> is the generator class for values of type A. The class Property represents an algebraic property that may be checked for its truth. Its most important member function is check which delivers a result.

Interestingly both the Gen and Property classes are immutable and have a single (different) function for their representation. Most member functions for these classes return a new instance with a composed function for its representation. The implementation functions for both Gen and Property do not execute until called by check in Property. Both classes use function representations in order to be lazy.

With KwikCheck you specify properties of your code that should hold regardless of input. KwikCheck then randomly generates the input data to try to find a case for which the property fails. In the following example we claim (incorrectly) that the largest example in a list of integers is the item at the front of the list.

@Test fun failingLargestOperation() {
    fun largest(list: List<Int>): Int = list.head()

    val property = forAll(genList(1, genInt)) { list ->
        prop(largest(list) == list.sort { a, b -> a.compareTo(b) }.last())
    }
    val checkResult: CheckResult = property.check()
    println(checkResult.summary())
}

with the output:

Falsified after 6 passed tests with <[3, 5, 0]>

We then correct this in the next example with a correct definition for function largest.

@Test fun successfulLargestOperation() {
    fun largest(list: List<Int>): Int {
        fun biggest(list: List<Int>, big: Int): Int =
            when (list) {
                is Nil -> big
                is Cons -> if (list.head() > big)
                    biggest(list.tail(), list.head())
                else
                    biggest(list.tail(), big)
            }   // biggest

        return biggest(list.tail(), list.head())
    }   // largest

    val property = forAll(genList(1, genInt)) { list ->
        prop(largest(list) == list.sort { a, b -> a.compareTo(b) }.last())
    }
    val checkResult: CheckResult = property.check()
    println(checkResult.summary())
}

with the output:

OK, passed 100 tests

KwikCheck randomly generates the input data to try to find a case for which the property fails. When such a case is found, we can request it tries to find a minimal test case by shrinking the input data. This minimal test case is then reported for easy inspection. It will try to find smaller inputs that also violate the property, in order to give the developer a clearer message about the nature of the failure. The List class member function removeDuplicates removes duplicates from a list retaining the first of each occurrence. In this example we claim that removing all duplicates returns the same list which, of course, is false:

@Test fun failingRemoveDuplicatesOperation() {
    val genIntList: Gen<List<Int>> = genList(genInt)
    val property = forAll(genIntList) {list ->
        prop(list.removeDuplicates() == list)
    }
    val checkResult: CheckResult = property.check()
    println(checkResult.summary())
}

with the output:

Falsified after 6 passed tests with <[3, 4, -4, 3, 3, -2]>

While large inputs may produce the errors, KwikCheck will attempt to shrink the input sequence to the smallest possible that will reproduce the error. The smaller the input, the easier it is to fix. The next example repeats the same false claim but requests that the list should be shrunk to a more manageable size.

@Test fun shrinkingRemoveDuplicatesOperation() {
    val genIntList: Gen<List<Int>> = genList(genInt)
    val shrinkIntList: Shrink<List<Int>> = shrinkList(shrinkInt)
    val property = forAll(genIntList, shrinkIntList) { list ->
        prop(list.removeDuplicates() == list)
    }
    val checkResult: CheckResult = property.check()
    println(checkResult.summary())
}

with output:

Falsified after 8 passed tests with <[0, 0]>

where it is now clear if we remove one of the duplicates the resulting list cannot be the same as this list with two zeros.

KwikCheck supports defining custom shrinking functions. We define a function that returns a Shrink<A> instance. The shrink factory method is used for this purpose. It expects a single function parameter with an A for its argument and returns a List<A>. An example is the library function shrinkPair:

fun <A, B> shrinkPair(sa: Shrink<A>, sb: Shrink<B>): Shrink<Pair<A, B>> =
    shrink{pair: Pair<A, B> ->
        sa.shrink(pair.first).map{a: A -> Pair(a, pair.second)}.append(sb.shrink(pair.second).map{b: B -> Pair(pair.first, b)})
    }

KwikCheck supports creating custom generators. The following example declares the domain model class Account representing a bank account with account number and account balance. The class is immutable and both member functions deliver new instances. Function credit increases the balance by the amount. Function debit only reduces the balance provided it does not become negative.

@Test fun domainModelGeneratorOperation() {
    class Account(val number: String, val balance: Int) {

        fun credit(amount: Int): Account = Account(number, balance + amount)

        fun debit(amount: Int): Account = Account(number, if (balance >= amount) balance - amount else balance)

    }

    val genAccount: Gen<Account> = genAlphaNumStr.bind{number ->
        genPosInt.bind{balance ->
            value(Account(number, balance))
        }
    }
    val property = forAll(genAccount, genPosInt) { account, amount ->
        prop(account.debit(amount).balance >= 0)
    }
    val checkResult: CheckResult = property.check()
    println(checkResult.summary())
}

with output:

OK, passed 100 tests

The property we are checking is that all debit operations leave the balance positive. We establish the value binding genAccount for a generator Gen<Account> that delivers a random Account instance. It is common to implement such generators using the monadic features of the Gen class. Using the generator genAlphaNumStr we bind what it delivers to the lambda parameter number. Similarly, using the genPosInt generator we bind what it delivers to the lambda parameter balance. Using these two random values we produce the required random Account.

Case Study

A common business use-case is validating a user login or a user registration. In the latter we might require the user to provide a name and an age. Both values might be supplied by entering values into text fields that populate a Form class:

data class Form(val name: String, val age: Int)

The validation logic is provided by the function:

fun validateForm(form: Form): ValidationNel<Error, User>

which accepts a Form as parameter and returns a ValidationNel value. The ValidationNel type is an alias for the class Validation:

typealias ValidationNel<E, A> = Validation<NonEmptyList<E>, A>

where the type parameter E represents failure and the type parameter A represents a successfully validated value. Failures are accumulated into a NonEmptyList when combining multiple Validation values using an applicative style.

If the Form is valid function validateForm returns a User object:

data class User(val name: String, val age: Int)

If the Form is invalid validateForm returns a non-empty list of Error values:

sealed class Error {
    data class NameTooLong(val text: String) : Error()
    data class NameTooShort(val text: String) : Error()
    data class AgeTooLow(val num: Int) : Error()
    data class AgeTooHigh(val num: Int) : Error()
}   // Error

To develop some property tests we will need to generate a random form. In the first test we produce a valid form by generating a valid name and a valid age. A valid user name is an alphanumeric string of 3 to 30 characters. A valid age is an integer between 18 and 100 inclusive.

val genValidName: Gen<String> = genAlphaNumStr(3, 30)
val genValidAge: Gen<Int> = choose(18, 100)
val genValidForm: Gen<Form> = form fmap genValidName ap genValidAge

An applicative style (see both the Option and Validation blogs) is used to generate the valid form from the valid name and valid age and where form is a curried variant of the Form class constructor:

val form: (String) -> (Int) -> Form = { name -> { age -> Form(name, age) }}

The test on valid data is:

val property = forAll(genValidForm){form ->
    val validation: ValidationNel<Error, User> = validateForm(form)
    prop(validation.isSuccess())
}
val checkResult: CheckResult = property.check()
println(checkResult.summary())

producing the usual OK, passed 100 tests.

We might also run tests with incorrect data. For example we might produce a form with an incorrect user name:

val genInvalidName: Gen<String> = genAlphaNumStr(50)

val genInvalidNameForm: Gen<Form> = form fmap genInvalidName ap genValidAge

Here the user name is any string of length 0 up to length 50. Both extremes are outwith our legal limits of 3 to 30 inclusive and function validateForm will fail.

val property = forAll(genInvalidNameForm){form ->

    val validation: ValidationNel<Error, User> = validateForm(form)

    val ok: Boolean = when (validation) {

        is FailureNel<Error, User> ->

            (validation.value.size() == 1) && isNameError(validation.value.head())

        is SuccessNel<Error, User> -> true

    }

    prop(ok)

}

val checkResult: CheckResult = property.check()

println(checkResult.summary())

The proposition we check is determined by the ok value. If the validation is a SuccessNel then the property is true. If the validation is a FailureNel then we assert the NonEmptyList has size 1 and that single entry is a name error:

fun isNameError(error: Error): Boolean =

    when (error) {

        is Error.NameTooLong -> true

        is Error.NameTooShort -> true

        else -> false

    }

A test on a form with a valid name but an invalid age follows the same pattern.

In the next test we provide a form with both the name and the age invalid:

val property = forAll(genInvalidNameAgeForm){form ->

    val validation: ValidationNel<Error, User> = validateForm(form)

    val ok: Boolean = when (validation) {

        is FailureNel<Error, User> ->

            (validation.value.size() <= 2) && validation.value.forAll{error -> isNameError(error) || isAgeError(error)}

        is SuccessNel<Error, User> -> true

    }

    prop(ok)

}

val checkResult: CheckResult = property.check()

println(checkResult.summary())

if the validation is a failure we may have accumulated one or two errors: a valid name but an invalid age; an invalid name but a valid age; or an invalid name and invalid age. If the validation is a FailureNel then we assert the list has size 1 or 2 and that the list elements are name or age errors.

A variation of this use case is one in which the users birth date is used instead of their age. The Form and the User have Calendar properties:

data class Form(val name: String, val birthDate: Calendar)

data class User(val name: String, val birthDate: Calendar)

The validation function is modified as:

fun validateForm(today: Calendar, form: Form): ValidationNel<Error, User> =

    user fmap validateName(form.name) ap validateAge(today, form.birthDate)

with today's date provided so we can validate the age from the birth date in the form.

The test appears below. Today's date is generated from the overloaded choose function with the start and end of the period. The randomly generated form is produced with a valid name and a valid birth date.

val property = forAll(choose(GregorianCalendar(1900, 1, 1), GregorianCalendar(2099, 12, 31))){today ->

    forAll(form fmap genValidName ap genValidBirthDate(today)){form ->

        val validation: ValidationNel<Error, User> = validateForm(today, form)

        prop(validation.isSuccess())

    }

}

val checkResult: CheckResult = property.check()

println(checkResult.summary())

To generate a valid birth date we must know today's date then generate a date that is 18 to 100 years earlier matching our initial requirements.

fun genValidBirthDate(today: Calendar): Gen<Calendar> =

    choose(18, 100).map{n ->

        val calendar: Calendar = today.clone() as Calendar

        val year: Int = calendar.get(YEAR)

        calendar.set(YEAR, year - n)

        calendar

    }   // genValidBirthDate

The KwikCheck sources are at []

The Dogs sources are at []

Ken Barclay

Kotlin: Option type

Kotlin: Option type

In this blog we consider how to deal with optional data - absent values that are not the result of an error. This might happen when a function returns null when not expected. A value of null is often used to represent an absent value. We can avoid using null by providing a type for representing optional values: the Option<A> class. The class is included in the custom library Dogs.

Kotlin treats null in a special way so that we may work safely with values that might be null. For instance, the null-safe operator for accessing properties foo?.bar?.baz will not throw an exception if either foo or its bar property is null, instead directly returning null.

Another approach to this problem is to provide a type for representing optional values. Values that may be present or absent are supported by the Option<A> sealed class. Option<A> is a container for an optional value of type A. If the value of type A is present, then the Option<A> is an instance of Some<A> containing the value of type A. If the value is absent, then the Option<A> is an instance of None.

You create an Option<String> for a given value by instantiating an instance of the Some class with the some factory function:

val greeting: Option<String> = some("Hello Ken")

If you know the value is absent, you assign the None object through the none factory function:

val goodbye: Option<String> = none()

The Option sealed class is shown below. It is an algebraic data type. The member function isEmpty returns true for None and false for instances of Some. The function filter returns the receiver if it is Some and the predicate applied to this value; otherwise, returns None. The function fold returns the result of applying the first function if the option is empty; otherwise return the second function applied to the wrapped value.

sealed class Option<A> {

    object None : Option<Nothing>()
    class Some<out A> internal constructor(val value: A) : Option<A>()

    abstract fun isEmpty(): Boolean

    fun contains(predicate: (A) -> Boolean): Boolean
    fun filter(predicate: (A) -> Boolean): Option<A> 
    fun <B> fold(none: () -> B, some: (A) -> B): B 
    fun <B> map(f: (A) -> B): Option<B> 

    fun <B> option(defaultValue: B, f: (A) -> B): B

    // ...

}   // Option

A number of contravariant functions are also defined as extension functions:

fun <A> Option<A>.getOrElse(defaultValue: A): A

The getOrElse function uses a default value in case an optional value is absent:

assertEquals(5,         some(5).getOrElse(99))

assertEquals(99,        none<Int>().getOrElse(99))

The option member function takes a default value and a function as parameters. If the receiver value is None then the defaultValue is returned. Otherwise, the function is applied to the value wrapped in the Some and returns the result. In the following the default value is zero and the increment is the transformer function.

assertEquals(0,     none<Int>().option(0){n -> 1 + n})

assertEquals(5,     some(4).option(0){n -> 1 + n})

The generic type parameter B used in the declaration for the option function is a simple Int type in the above example. However, it might be a more complex type such as a List type. This is shown in the next example:

assertEquals(ListF.empty(), none<Int>().option(ListF.empty()){n -> ListF.of(-n, n)})

assertEquals(ListF.of(-4, 4), some(4).option(ListF.empty()){n -> ListF.of(-n, n)})

The default is the empty List and the transformer parameter converts the value wrapped in a Some into a List of the value and its negative.

Of course, the type parameter B might be something more exotic such as a function type. In the following the default is the function isEven and the transformer is the curried binary function same. When the receiver is a Some it must wrap a String so that same can be called with the String. The resulting function expects an Int parameter and returns a Boolean that is true if the Int equals the string length.

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

val same: (String) -> (Int) -> Boolean = {str -> {n -> (str.length == n)}}

val op1: Option<String> = none()

val op2: Option<String> = some("ken")

val op3: Option<String> = some("immutable")

assertEquals(false, op1.option(::isEven, same)(3))

assertEquals(true, op2.option(::isEven, same)(3))

assertEquals(false, op2.option(::isEven, same)(4))

assertEquals(true, op3.option(::isEven, same)(9))

Observe how the Option type is declared as an abstract sealed class with two internal sub-types representing the absence and the presence of data. The absence of data is captured by the object None while the presence of data is represented by the subclass Some. The Some constructor is tagged as internal so values are only produced through the factory function some.

val op: Option<Int> = Some(5)         // cannot access Some constructor on right hand side

Pattern matching

Neither the object None nor the class Some are tagged as internal or private. That way the type names can be used in user-defined functions:

fun <A> contains(op: Option<A>, predicate: (A) -> Boolean): Boolean =

    when (op) {

        is Option.None -> false

        is Option.Some -> predicate(op.value)

    }   // contains

assertEquals(true,      contains(some(4)){n -> isEven(n)})

assertEquals(false,     contains(none<Int>()){n -> isEven(n)})

Selected Option operations

One important function of the Option class is the member function map. The function map applies the transforming function parameter converting an Option<A> into an Option<B>:

assertEquals(some(true),    some(4).map{n -> isEven(n)})

assertEquals(none(),        none<Int>().map{n -> isEven(n)})

The Option type is like a container with zero or one elements. The higher order function bind is used to make the Option class 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 example below 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 are not both exactly divisible by 6:

fun divide(num: Int, den: Int): Option<Int> =
    if (num % den != 0) none() else some(num / den)

fun division(a: Int, b: Int, c: Int): Option<Pair<Int, Int>> =
    divide(a, c).bind{ac -> divide(b, c).bind{bc -> some(Pair(ac, bc))}}

assertEquals(some(3), divide(12, 4))
assertEquals(none(), divide(12, 5))

assertEquals(some(Pair(2, 3)), division(18, 27, 9))
assertEquals(none(), division(18, 27, 6))

The monadic Option is supported by the bind (or flatMap) member function. Its signature is:

fun <B> bind(f: (A) -> Option<B>): Option<B>

A monad fails fast. If any of the Option values in a sequence of binds is a None then the result is a None. In function division if the function call divide(a, c) delivers a None then processing is complete and None is returned. This means that the function call divide(b, c) is short-circuited and never executed.

Our goal is to stop computation if an error (None) is obtained. In other words fail-fast. Sometime we may want to accumulate all errors, for example when validating user input, but this is a different problem and leads to a different solution discussed below.

The Option type is also a functor, supporting the extension function fmap which simply repeats the map function. The Option type then represents something that can be mapped over.

fun <A, B> Option<A>.fmap(f: (A) -> B): Option<B> = this.map(f)

The inclusion of function fmap gives rise to a number of useful utilities that can be defined by it. Function distribute, for example, is applied to a pair wrapped in an Option and distributes the values into a pair of Options:

fun <A, B> Option<Pair<A, B>>.distribute(): Pair<Option<A>, Option<B>>

Here is a simple illustration:

assertEquals(Pair(some("Ken"), some(25)),   some(Pair("Ken", 25)).distribute())

assertEquals(Pair(none(), none()),          none<Pair<String, Int>>().distribute())

Option composition

The immutable List class from the custom library supports the extension function sequenceOption that combines a List<Option<A>> into an Option<List<A>>. It delivers a Some<List<A>> if all the values in the original list are Some instances. If there is at least one None in the list then the function delivers a None. The signature for sequenceOption is:

fun <A> List<Option<A>>.sequenceOption(): Option<List<A>>

Composing the various Option functions we can sum the integer values in the list of Options:

assertEquals(
    10,
    ListF.of(some(1), some(2), some(3), some(4)).sequenceOption().map{list -> list.sum()}.getOrElse(0)
)

assertEquals(
    0,
    ListF.of(some(1), some(2), none(), some(4)).sequenceOption().map{list -> list.sum()}.getOrElse(0)
)

The Option type is also an applicative functor. When mapping functions over the Option functor with fmap we have provided a unary function for the mapping as in some(6).fmap{m: Int -> isEven(m)}. What do we get if we provide a curried binary function? For example, what type is some(6).fmap{m: Int -> {n: Int -> (m == n)}}? The answer is we get a unary function wrapped in an Option as shown for the value binding opF.

assertEquals(some(6),       some(5).fmap{m: Int -> m + 1})

val opF: Option<(Int) -> Boolean> = some(6).fmap{m: Int -> {n: Int -> (m == n)}}

assertEquals(some(11),      some(5).ap(some(6).fmap{m: Int -> {n: Int -> m + n}}))

assertEquals(some(11),      {m: Int -> {n: Int -> m + n}} fmap some(5) appliedOver some(6))

We cannot map a function wrapped in an Option over another Option. The Option type as an applicative functor includes the extension function ap:

fun <A, B> Option<A>.ap(f: Option<(A) -> B>): Option<B>

which applies the wrapped function to the receiver Option. This is shown in the assertion immediately  following the opF binding. The infix version of ap is known as appliedOver and lets us express our intention in an applicative style as shown in the final assertion.

Case Study

The final illustration demonstrates how to use an Option to change how we might use a Kotlin Map. In the listing the function get returns an Option when querying for a given key. The standard implementation of Map.get(key) returns null if the key is absent.

data class User(val name: String, val email: String)

fun <K, V> get(key: K, map: Map<K, V>): Option<V> {
    val v: V? = map.get(key)
    return if (v == null) none() else some(v)
}

val staff: Map<String, User> = mapOf(
    "ken" to User("KenB", "ken@gmail.com"),
    "john" to User("JohnS", "john@gMail.com"),
    "jessie" to User("JessieK", "jessie@gmail.com")
)

assertEquals(some(User("KenB", "ken@gmail.com")),   get("ken", staff))
assertEquals(some("ken@gmail.com"),                 get("ken", staff).bind{user -> some(user.email)})
assertEquals(none(),                                get("Irene", staff))

The code sample demonstrates how functions returning an Option can be composed. You do not have to test for None occurring and we do not risk throwing a NullPointerException.

Suppose we are using Option to work with the results of look ups in two Maps. If we simply need to  combine the results from two independent look ups we can use the applicative fmap2 function:

val departments: Map<String, String> = MapF.of( // department indexed by employee
    "Ken" to "Software",
    "John" to "Software",
    "Jessie" to "Database"
)
val salaries: Map<String, Int> = MapF.of(       // salaries indexed by employee
    "Ken" to 45000,
    "John" to 40000,
    "Jessie" to 45000
)

val op: Option<Pair<String, Int>> = fmap2(departments.lookUpKey("Jessie"), salaries.lookUpKey("Jessie")){
    dept, salary -> Pair(dept, salary)
}

assertEquals(some(Pair("Jessie", 45000)),    op)

Here we are performing two look ups but they are independent and we merely want to combine their results within the Option context. If we want the result of one look up to effect what look up we perform next then we need bind as shown next:

val ids: Map<String, Int> = MapF.of(
    "Ken" to 123,
    "John" to 456,
    "Jessie" to 789
)
val departments: Map<Int, String> = MapF.of(
    123 to "Software",
    456 to "Software",
    789 to "Database"
)
val salaries: Map<Int, Int> = MapF.of(
    123 to 45000,
    456 to 40000,
    789 to 45000
)

val op: Option<Pair<String, Int>> =
    ids.lookUpKey("Jessie").bind{id: Int ->
        fmap2(departments.lookUpKey(id), salaries.lookUpKey(id)) {
            dept, salary -> Pair(dept, salary)
        }
    }

assertEquals(some(Pair("Database", 45000)),     op)

Here ids is a Map between the employee name and employee id. To access Jessie's department and salary we first need to resolve Jessie's name to her id and then use this id to perform look ups in both departments and salaries.

Combining options

Adopting the Option type may seem to make existing code obsolete. An existing code base may include many functions that convert some type A into some type B. Working with the Option type might suggest that we need functions from Option<A> to Option<B>. We can easily adapt the existing code base by using the custom library function lift from the object declaration OptionF:

fun <A, B> lift(f: (A) -> B): (Option<A>) -> Option<B>

In the following liftLength lifts a function from a String to an Int into a function from an Option<String> to an Option<Int>. Similarly, liftParseOct lifts a function from a String to an Int into a function from an Option<String> to an Option<Int>. In this example we are lifting the parseOct function which parses a String to an Int with radix 8.

val liftLength: (Option<String>) -> Option<Int> = lift(String::length)

assertEquals(some(3), liftLength(some("ken")))

assertEquals(none(), liftLength(none()))

val parse: (Int) -> (String) -> Int = flip(C2(Integer::parseInt))

val parseOct: (String) -> Int = parse(8)

val liftParseOct: (Option<String>) -> Option<Int> = lift(parseOct)

assertEquals(some(7), liftParseOct(some("7")))

assertEquals(some(83), liftParseOct(some("123")))

To map a binary function over two Option values we use the fmap2 library function:

fun <A, B, C> fmap2(oa: Option<A>, ob: Option<B>, f: (A) -> (B) -> C): Option<C>

In the following we combine an Option<String> and an Option<Int> into an Option<Boolean> where the resulting Boolean is true if the Int and the String length are the same.

val opName: Option<String> = some("ken")

val opInt3: Option<Int> = some(3)

val opInt6: Option<Int> = some(6)

assertEquals(some(true), fmap2(opName, opInt3){str -> {n -> (str.length == n)}})

assertEquals(some(false), fmap2(opName, opInt6){str -> {n -> (str.length == n)}})

Composing Option instances is just the beginning. We will need to compose an Option type with some other type. For example, we may wish to convert a List<Option<A>> into an Option<List<A>> where the values in the result List that is wrapped in an Option are those values from the source List that were wrapped in Option. Usually, we want a Some<List<A>> if all the elements in the List are a Some<A>, and a None if one or more elements in the List are a None. The library function sequenceOption from ListF does just this:

assertEquals(some(ListF.of(1, 2, 3, 4)), ListF.of(some(1), some(2), some(3), some(4)).sequenceOption())

assertEquals(none(), ListF.of(some(1), some(2), none(), some(4)).sequenceOption())

assertEquals(none(), ListF.of(some(1), some(2), none(), none()).sequenceOption())

Effectful computations

Consider the class Account that might be used in a banking application. A function open will receive details of the account through its parameter list to create and initialize an Account. The return type of open is Account but how do we handle failure? We might choose to return null or throw an exception. However, we can better handle failure as effects that compose with other abstractions in our code. An effect adds capabilities to to a computation so that we do not have to use side effects. An effect is usually modeled as a type that wraps these additional capabilities around some type. Our Option<A> adds the capability of optionality to the type A. Hence the return type for the function open would be Option<Account>. We we see many more examples of this from our custom library.

The code for the Dogs library can be found at:

https://github.com/KenBarclay/TBA

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