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.