The Either Monad Design Pattern and Automatic Function Memoization in Kotlin

Learn about the Either monad and automatic function memoization in this tutorial by Samuel Urbanowicz, an experienced software engineer skilled in mobile applications and backend development.

The concept of Monad is one of the most fundamental functional programming design patterns. You can consider a Monad as an encapsulation for a data type that adds a specific functionality or provides custom handlers for different states of the encapsulated object. One of the most commonly used monads is a Maybe monad. The Maybe monad is supposed to provide information about the enclosed property presence. It returns an instance of the wrapped type whenever it’s available. Java 8 introduced the Optional<T> class, which implements the Maybe concept. It’s a great way to avoid operating on null values.

The Either Monad Design Pattern

However, apart from acquiring information about unavailable states, you would often like to be able to provide some additional information. For example, if the server returns an empty response, it would be useful to get an error code or a message instead of an empty response string. This is a scenario for another type of Monad, usually called Either, which this tutorial will focus on.

How to do it…

  1. Declare Either as a sealed class 
    sealed class Either<out E, out V>
  2. Add two subclasses of Either, representing Error and Value: 
    sealed class Either<out L, out R> {
data class Left<out L>(val left: L) : Either<L, Nothing>()
data class Right<out R>(val right: R) : Either<Nothing, R>()
}
  3. Add factory functions to conveniently instantiate Either: 
    sealed class Either<out L, out R> {
data class Left<out L>(val left: L) : Either<L, Nothing>()
data class Right<out R>(val right: R) : Either<Nothing, R>()

companion object {
fun <R> right(value: R): Either<Nothing, R> = 
         Either.Right(value)
fun <L> left(value: L): Either<L, Nothing> = 
         Either.Left(value)
    }
}

How it works…

In order to make use of the Either class and benefit from the Either.right() and Either.left() methods, you can implement a getEither() function, which will try to perform an operation passed to it as a parameter. If the operation succeeds, it will return the Either.Right instance holding the result of the operation; otherwise, it will return Either.Left, holding a thrown exception instance:

fun <V&gt; getEither(action: () -&gt; V): Either<Exception, V&gt; =
try { Either.right(action()) } catch (e: Exception) { Either.left(e) }

By convention, you can use the Either.Right type to provide a default value and Either.Left to handle any possible edge cases.

There’s more…

One essential functional programming feature the Either Monad can provide is the ability to apply functions to its values. You can simply extend the Either class with the fold() function, which can take two functions as the parameters. The first function should be applied to the Either.Left type and the second should be applied to Either.Right:

sealed class Either<out L, out R&gt; {
data class Left<out L&gt;(val left: L) : Either<L, Nothing&gt;()
data class Right<out R&gt;(val right: R) : Either<Nothing, R&gt;()

fun <T&gt; fold(leftOp: (L) -&gt; T, rightOp: (R) -&gt; T): T = when (this) {
is Left -&gt; leftOp(this.left)
is Right -&gt; rightOp(this.right)
    }

  //...
}

The fold() function will return a value from either the leftOp or rightOp function, whichever is used. The usage of the fold() function can be illustrated with a server-request parsing example.

Suppose you have the following types declared:

data class Response(val json: JsonObject)
data class ErrorResponse(val code: Int, val message: String)

You also have a function responsible for delivering a backend response:

fun someGetRequest(): Either<ErrorResponse, Response&gt; = //..

You can use the fold() function to handle the returned value in the right way:

someGetRequest().fold({
showErrorInfo(it.message)
}, {
parseAndDisplayResults(it.json)
})

You can also extend the Either class with other useful functions, like the ones available in the standard library for data-processing operations—map, filter, and exists.

Automatic functions memoization

Memoization is a technique used to optimize the execution speed of a program by caching the results of expensive function calls and reusing their ready values when required again. Although memoization causes an obvious trade-off between memory usage and computation time, it’s often crucial to extracting the desired performance. It can help to optimize recursive functions that call themselves multiple times with the same parameter values. Memoization can easily be added internally to a function implementation. However, in this recipe, you’ll create a general-purpose, reusable memoization mechanism that could be applied to any function.

How to do it…

  1. Declare a Memoizer class responsible for caching the results: 
    class Memoizer<P, R> private constructor() {

private val map = ConcurrentHashMap<P, R>()

private fun doMemoize(function: (P) -> R):
        (P) -> R = { param: P ->
map.computeIfAbsent(param) { param: P ->
function(param)
}
            }

companion object {
fun <T, U> memoize(function: (T) -> U): (T) -> U =
                Memoizer<T, U>().doMemoize(function)
    }
}
  2. Provide a memoized() extension function for the (P) -> R function type: 
    fun <P, R> ((P) -> R).memoized(): (P) -> R = Memoizer.memoize<P, R>(this)

How it works…

The memoize() function takes an instance of a one-argument function as its argument. The Memoizer class contains the ConcurrentHashmap<P, R> instance, which is used to cache the function’s return values. The map stores functions passed to memoize() as arguments as the keys, and it puts their return values as its values.

First, the memoize() function looks up the value for a specific parameter of the function passed as an argument. If the value is present in the map, it is returned. Otherwise, the function is executed and its result is returned by memoize() and put into the map. This is achieved using the handy inline fun <K, V> ConcurrentMap<K, V>.computeIfAbsent(key: K, defaultValue: () -> V): V extension function provided by the standard library.

Additionally, you can provide an extension function, memoized(), for the Function1 type, which will allow you to apply the memoize() function directly to the function references.

Note that the under-the-hood functions in Kotlin are compiled to the FunctionN interface instances in the Java bytecode, where N corresponds to the number of function arguments. Thanks to this, you can declare an extension function for a function. For example, in order to add an extension function for a function taking two arguments, (P, Q) -> R, you need to define an extension as fun <P, Q, R> Function2<P, Q, R>.myExtension(): MyReturnType.

Now, take a look at how you can benefit from the memoized() function in action. Consider a function that computes the factorial of an integer recursively:

fun factorial(n: Int): Long = if (n == 1) n.toLong() else n * factorial(n - 1)

You can apply the memoized() extension function to enable caching of the results:

val cachedFactorial = ::factorial.memoized()
println(" Execution time: " + measureNanoTime { cachedFactorial(12) } + " ns")
println(" Execution time: " + measureNanoTime { cachedFactorial(13) } + " ns")

The above code snippet gives the following output on a standard computer:

Execution time: 1547274 ns
Execution time: 24690 ns

As you can see, even though the second computation requires a higher number of recursive calls of the factorial() function, it takes much less time than the first computation.

There’s more…

You can implement similar automatic memoization implementations for other functions that take more than one argument. In order to declare an extension function for a function taking N arguments, you’d have to implement an extension function for the FunctionN type.