47 Degrees joins forces with Xebia read more

The Traverse Typeclass: Use cases in Kotlin with Arrow

The Traverse Typeclass: Use cases in Kotlin with Arrow

The Arrow open source library was introduced to the ecosystem in 2018 and quickly became the best source for applying Functional Programming (FP) principles in Kotlin.

In an attempt to analyze how similar Kotlin with Arrow is to other languages, I decided to work on a few examples for the Traverse type class. We will review several common cases that may present themselves during the development of a program, like performing a series of IO operations, several asynchronous computations, or several changes to global variables, and how we can simplify them with Traverse.

For added clarification, the results of the computations are included after the examples under double slashes: “//”.

These examples are based on Arrow 0.9.0-SNAPSHOT.

Traverse

Traverse is a type class also known as Traversable and is used to perform traversals over a structure with an effect.

Let’s start by looking at an example where the side effects are modeled as data types. Side effects in Functional Programming are changes outside of the scope of the function, for example, performing an IO operation, modifying global variables, etc.

In Kotlin with Arrow, these aforementioned data types can be modeled as Option for missing values, Either and Validated for things that either provide a valid result or give an error, and IO, Async for asynchronous computations.

You’ll need these imports for the following examples:

import arrow.Kind
import arrow.core.*
import arrow.core.extensions.either.applicative.applicative
import arrow.core.extensions.either.applicativeError.catch
import arrow.core.extensions.option.applicative.applicative
import arrow.data.*
import arrow.data.extensions.list.foldable.sequence_
import arrow.data.extensions.list.foldable.traverse_
import arrow.data.extensions.list.traverse.sequence
import arrow.data.extensions.list.traverse.traverse
import arrow.data.extensions.nonemptylist.semigroup.semigroup
import arrow.data.extensions.validated.applicative.applicative
import arrow.effects.ForIO
import arrow.effects.IO
import arrow.effects.extensions.io.applicative.applicative
import arrow.effects.fix

Next, we will define some data classes and functions to show different use cases of traverse below:

sealed class SecurityError {
  data class RuntimeSecurityError(val cause: String) : SecurityError()
}

interface Credential
data class Profile(val id: String)
data class User(val id: String, val name: String)

parseInt: Function that will try to convert a String parameter s to an Int, if it succeeds it will return the number inside Some. If it fails, it will return None.

validateLogin: This function can either fail or be a successful operation when validating login credentials.

userInfo: This function can return a Profile asynchronously.

interface SideEffectingFunctions {
  fun parseInt(s: String): Option<Int> =
    Try { s.toInt() }.fold(ifFailure = { None }, ifSuccess = { v -> Some(v) })

  fun validateLogin(cred: Credential): Either<SecurityError, Unit>

  fun userInfo(user: User): IO<Profile>
}

As we can see, every function listed above only takes one parameter to perform its operation.

This is just a mock implementation of the previous interface, where we simulate the results of a side effect performed by an external system. We’ll make good use of it later.

object ValidEffects : SideEffectingFunctions {

  override fun validateLogin(cred: Credential): Either<SecurityError, Unit> =
    Either.right(Unit)

  override fun userInfo(user: User): IO<Profile> =
    IO { Profile(id = user.id) }  // assuming profile details successfully fetched

  fun savingProfiles(): IO<Unit> =
    IO.unit

}

We just defined results for our functions for the happy case, or in other words, when everything goes “right”. The next mock-up for our SideEffectingFunctions simulates the result when something goes “wrong”.

object ErrorEffects : SideEffectingFunctions {

  override fun validateLogin(cred: Credential): Either<SecurityError, Unit> =
    Either.left(SecurityError.RuntimeSecurityError("Invalid credentials"))

  override fun userInfo(user: User): IO<Profile> =
    IO.raiseError(Throwable("Error retrieving profile"))

}

If we need to extract the profile information for a List of Users we can create a function that reuses the userInfo function defined previously.

fun profilesFor(users: List<User>): List<IO<Profile>> =
  users.map(ValidEffects::userInfo)

Notice how we are returning a List of deferred computations. It would be nice if we could aggregate the results and return the List of Profile under a single IO, something like IO<List<Profile>>.

To make this transformation possible, we use the Traverse type class.

Traverse is defined with the following signature:

interface Traverse : Functor, Foldable { fun <G, A, B> Kind<F, A>.traverse(AP: Applicative, f: (A) -> Kind<G, B>): Kind<G, Kind<F, B>> }

For our example, F would be List (the initial container) and G would be the data type representing the side effect: Option, Either or IO.

So, if we have a List<User> (for the profiles we want to obtain) and a function User -> IO<Profile>, we can transform with traverse and instead of obtaining a List<IO<Profile>>, all the results will be aggregated into a single IO<List<Profile>>.

In this case, traverse can go over the collection, apply the function, and aggregate the resulting values (with side effects) in a List.

Basically, F is some context which may contain a value. We are using List in the example, but there are also Traverse implementations for Option, Either, and Validated.

Let’s take a look at another example for further clarification:

fun parseIntEither(s: String): Either<NumberFormatException, Int> =
  catch(
    { NumberFormatException("Error converting $s to Int") },
    { s.toInt() }
  )

fun parseIntValidated(s: String): ValidatedNel<NumberFormatException, Int> =
  Validated.fromEither(parseIntEither(s)).toValidatedNel()

Here’s an example of what these functions do:

parseIntEither("1")
// Right(1)
parseIntEither("jimmy")
// Left(a=java.lang.NumberFormatException: Error converting jimmy to Int)

We can use these two functions to traverse a collection containing strings, converting them to integers, and accumulating the errors with Either or Validated. Here are a few examples of a list with map and traverse for Either:

val listOfValidNumbers =
  listOf("1", "2", "3")
val listOfInvalidNumbers =
  listOf("1", "jimmy", "peter")

listOfValidNumbers.map(::parseIntEither)
//ListK(list=[Right(b=1), Right(b=2), Right(b=3)])

listOfValidNumbers.traverse(Either.applicative(), ::parseIntEither)
// Right(b=ListK(list=[1, 2, 3]))

listOfInvalidNumbers.traverse(Either.applicative(), ::parseIntEither)
//Left(a=java.lang.NumberFormatException: Error converting jimmy to Int)

Here are two examples of the list with traverse for Validated:

listOfValidNumbers.traverse(ValidatedNel.applicative(Nel.semigroup<NumberFormatException>()), ::parseIntValidated)
//Valid(a=ListK(list=[1, 2, 3]))

listOfInvalidNumbers.traverse(ValidatedNel.applicative(Nel.semigroup<NumberFormatException>()), ::parseIntValidated)
//Invalid(e=NonEmptyList(all=[java.lang.NumberFormatException: Error converting jimmy to Int, java.lang.NumberFormatException: Error converting peter to Int]))

When we’re traversing a list with Validated, we are using an Applicative instance of ValidatedNel, and for that we need to provide a “proof” that the non-empty-list (Nel) is a Semigroup. The Applicative typeclass instance for ValidatedNel allows us to run independent computations. The Semigroup typeclass instance allows us to combine elements of the same type, in this case, it helps ValidatedNel with the task of accumulating the errors.

If you want to see another example, visit: 1/n - How do I … in FP : Validation by Emmanuel Nhan.

sequence

When we want to traverse a collection where the elements already contain an effect, for example, List<Option<A>>, we may want to convert it to Option<List<A>> to work more smoothly. We can do this by traversing the list and applying the ::identity transformation function to each element.

val listofOptionalNumbers: List<Option<Int>> =
  listOf(Option(1), Option(2), Option(3))

listofOptionalNumbers.traverse(Option.applicative(), ::identity)
//Some(ListK(list=[1, 2, 3]))

Sequence is equivalent to traverse when applying identity.

val sequenceOptions = listofOptionalNumbers.sequence(Option.applicative())
//Some(ListK(list=[1, 2, 3]))

We could also use sequence on a list of Either.

val listOfEither: List<Either<NumberFormatException, Int>> =
  listOfValidNumbers.map(::parseIntEither)

listOfEither.sequence(Either.applicative())
//Right(b=ListK(list=[1, 2, 3]))

traverse_ and sequence_

Another usage for sequence is when we are traversing a list of data to which we apply an effectful function and don’t care about the returned values.

Continuing with our first example, imagine the saveProfile function that performs a side effect, saves a profile in a database, and returns Unit asynchronously.

fun saveProfile(user: User): IO<Unit> =
  ValidEffects.savingProfiles()

If we apply traverse, we will have an Asynchronous computation result with a List of Unit that we do not care about.

fun saveProfiles(users: List<User>): Kind<ForIO, Kind<ForListK, Unit>> =
  users.traverse(IO.applicative(), ::saveProfile)

Here, we prefer to have a Unit as a result since it conveys the same information.

Traversing solely for the sake of the effect (ignoring any values that may be produced, Unit or otherwise) is common, so Foldable (superclass of Traverse) provides traverse_ and sequence_ methods that do the same thing as traverse and sequence but ignores any value produced along the way, returning Unit at the end.

val listOfUsers = listOf(
  User("1","Jimmy"),
  User("2","Peter"),
  User("3","Rob")
)

val result: Kind<ForIO, Kind<ForListK, Unit>> =
  saveProfiles(listOfUsers)

result.fix().unsafeRunSync()
//ListK(list=[kotlin.Unit, kotlin.Unit, kotlin.Unit])

In the example above, the result will hold an asynchronous computation with a list of effectful results, a list of Unit.

result.fix().unsafeRunSync()) is just to force the computation of the asynchronous operation and see the result of the example.

That should return a ListK(list=[kotlin.Unit, kotlin.Unit, kotlin.Unit]).

Let’s see what we would get with traverse_:

val l = listOfUsers.traverse_(IO.applicative(), ::saveProfile)
l.fix().unsafeRunSync()
//kotlin.Unit

That should return kotlin.Unit.

Now, if we have a list already containing effects with results we do not care about: listOfAsyncResults, we can apply sequence_ to aggregate the result.

val listOfAsyncResults =
  listOfUsers.map(::saveProfile)
//[Pure(a=kotlin.Unit), Pure(a=kotlin.Unit), Pure(a=kotlin.Unit)]


val asyncResult =
  listOfAsyncResults.sequence_(IO.applicative())

asyncResult.fix().unsafeRunSync()) //if we decide to finally run the computations we see that we get Unit, that we can ignore.
//kotlin.Unit

So, instead of having a list of deferred computations we will have a single deferred computation as a result.

Conclusion

To summarize, we reviewed the Traverse type class and several use cases and patterns where it can be applied. We reviewed how to apply this concept with data types such as Option, Either or Validated when working with collections of effects that could go either “right” or “wrong”. Also, we saw how can we use sequence to work with collections that already contain these data types. We wrapped up with an example of how to use traverse_ and sequence_ when working with effects we don’t care about and how to aggregate them into a single Unit.

Resources:

The active development of Arrow is proudly sponsored by 47 Degrees, a Functional Programming consultancy with a focus on the Scala, Kotlin, and Swift Programming languages.

Ensure the success of your project

47 Degrees can work with you to help manage the risks of technology evolution, develop a team of top-tier engaged developers, improve productivity, lower maintenance cost, increase hardware utilization, and improve product quality; all while using the best technologies.