Build your own Either in Kotlin

Recently I have spent some time delving into Kotlin, I quickly noticed Jetbrains have decided not to include some useful monads that you find in Scala’s standard library, namely Option, Try and Either.  Although the need for an Optional type is somewhat offset by Kotlin’s nullable type (?), it was a surprise the others are omitted as they are incredibly useful when writing functional code. Jetbrains have heavily promoted Kotlin on Android, so perhaps they wanted to keep the language lightweight to continue appealing to this platform and drive adoption.

When to use Either?

Either is a typeclass that wraps the return of 2 possible values, generalised as Left and Right.  An example might be the result of a coin toss, Heads and Tails.  If you wanted a return type for a function coinToss() then it could be represented by Either.   Another more common use of Either is when you need to return an error condition with some contextual information, for example given a:

data class InvalidNameError(val message: String, val failedRegex: List<String>)

you can define:

fun validateName(name: String): Either<InvalidNameError, String>

The returned right hand side denotes a successfully validated name, and the left hand side an error if validation failed. Typically convention says you should use the right hand branch for happy path and the left branch for error conditions.
You may be thinking what is the point in using Either as an error container over throwing an exception.  Using exceptions to denote this kind of logic introduces problems of its own.  The error is no longer a value, as the control flow of the application is broken by the thrown exception, we are now reliant on the error being handled in an arbitrary place in the stack.   Exceptions will usually be more heavyweight than a data class as they contain details of the stack, not to mention any associated stack operations that occur.  From a clients perspective we lose the explicitness of the resulting error that can be raised.  All of these are undesirable side effects, in functional codebases, exceptions are best left for exceptional cases (or omitted entirely where possible).

Creating your own Either

First we define our type class with parameters to represent both left and right, along with 2 data classes that wrap our left and right values.  This allows us to construct our Either instances for any types.

sealed class Either<L,R>

data class Right(val rightValue: R) : Either()

data class Left(val leftValue: L) : Either()

map

Now we can write a map function in terms of our type class objectives, in order to be able to compose a new Either with an arbitrary function we need to define how a left and right instance will be handled.  As we stated earlier, the Right hand side is used to denote the happy path, therefore it makes sense to define our map function to run on the right hand value.  Our map function:

fun  map(fn: (R) -> N): Either = when (this) {
    is Right -> Right(fn(rightValue))
    is Left -> this as Either
}

The N type parameter denotes the new Right hand-side type after  fn has been applied.  For cases where you call map and the current value of the Either is a Left (non happy path), then the map function cannot be applied as there is no Right value. As we know the current instance is already a Left, rather than create a new Left, we can safely cast the current instance to an Either as an optimisation.

flatMap

Implementation of flatMap is simpler than map in this case as fn already returns an Either.  Therefore we just run the function against our right hand value.  The left hand branch uses the same logic as above for map.

fun  flatMap(fn: (R) -> Either): Either = when (this) {
    is Right -> fn(rightValue)
    is Left -> this as Either
}

L and R accessors

In order to access the underlying values we can provide getters for both left and right branches of the Either, an exception is thrown if the underlying type is not the expected value:

fun left(): L = when (this) {
  is Left -> leftValue
  else ->
     throw NoSuchElementException("leftValue projection does not exist")
}

fun right(): R = when (this) {
  is Right -> rightValue
  else ->
     throw NoSuchElementException("rightValue projection does not exist")
}

L and R Covariance

One problem with our current implementation is we can’t assign our Either expression to a value of Either with a subtype type parameter, for example take the model Cat extends Mammal, an Either[Error, Cat] could not be assigned to Either[Error,Mammal].  This is not desirable as it is generally a useful property to generalise on a particular interface type when writing generic code.  We can achieve this by making our type parameters covariant, the keyword in Kotlin to denote this is out as a suffix to the type parameter:

sealed class Either<out L, out R>

A further explanation of covariance and contra-variance in Kotlin can be found on here.

inline and crossinline

In Kotlin higher order functions as parameters can be marked inline to avoid object allocations (lambdas are instances of objects underneath on the JVM!). This will inline the code at the call site during compilation removing any performance penalties. In addition crossinline disables the ability to local return inside a lambda (something we should enforce as we have no guarantee of scope or context when the lambda is run, there is a detailed blog post here describing the differences.

In Action

Our final Either monad now looks like this (https://github.com/rama-nallamilli/mockee/blob/master/src/main/kotlin/org/mockee/func/Either.kt):

@Suppress("UNCHECKED_CAST")
sealed class Either<out L, out R> {

    inline fun <N> leftMap(crossinline fn: (L) -> N): Either<N, R> = when (this) {
        is Left -> Left(fn(leftValue))
        is Right -> this as Either<N, R>
    }

    inline fun <N> map(crossinline fn: (R) -> N): Either<L, N> = when (this) {
        is Right -> Right(fn(rightValue))
        is Left -> this as Either<L, N>
    }

    fun left(): L = when (this) {
        is Left -> leftValue
        else ->
            throw NoSuchElementException("leftValue projection does not exist")
    }

    fun right(): R = when (this) {
        is Right -> rightValue
        else ->
            throw NoSuchElementException("rightValue projection does not exist")
    }
}

@Suppress("UNCHECKED_CAST")
inline fun <L, R, N> Either<L, R>.flatMap(crossinline fn: (R) -> Either<L, N>): Either<L, N> = when (this) {
    is Right -> fn(rightValue)
    is Left -> this as Either<L, N>
}

data class Right<out L, out R>(val rightValue: R) : Either<L, R>()
data class Left<out L, out R>(val leftValue: L) : Either<L, R>()

And an example snippet of the code in action(https://github.com/rama-nallamilli/mockee/blob/master/src/main/kotlin/org/mockee/http/validator/DslDataValidator.kt):

    fun validateRequest(data: DslData): Either<InvalidMockRequest, MockRequest> {

        val validatedPath = validateInitialised(
                getter = { data.path },
                errorMsg = "missing url path required")

        val validatedStatusCode = validateInitialised(
                getter = { data.statusCode },
                errorMsg = "missing statusCode required")

        return validatedPath.flatMap { path ->
            validatedStatusCode.flatMap { statusCode ->
                Right<InvalidMockRequest, MockRequest>(
                        MockRequest(method = data.requestMethod.javaClass.simpleName,
                                status = statusCode,
                                url = path,
                                requestHeaders = data.requestHeaders,
                                responseHeaders = data.responseHeaders,
                                responseBody = data.stringBody
                        ))
            }
        }
    }

    private fun <T> validateInitialised(getter: () -> T,
                                        errorMsg: String): Either<InvalidMockRequest, T> {
        return try {
            Right(getter())
        } catch (e: UninitializedPropertyAccessException) {
            Left(InvalidMockRequest(errorMsg))
        }
    }

Arrow


Writing your own monads can be fun a exercise but if you want to start getting more serious with Functional programming then I would recommend checking out Arrow, a functional programming library for Kotlin. It contains all the common monad types (including Either) plus constructs to build your own monads. It also contains optics and recursion schemes which can be very useful.

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s