Advanced FP for the Enterprise Bee: Traverse

Garth Gilmour

Follow

Jan 8 · 6 min read

Introduction

This article is the first in a series, where we introduce advanced FP concepts via Kotlin. The intended audience is Enterprise Developers like myself, the Worker Bees of our industry.

I’m going to focus on practical applications (be they ever so humble) and postpone the theory till it’s essential. Late evaluation is very FP after all…

In this article I would like to set the stage for the series, and then make a start by introducing Traverse. All the code shown is available via this public repository.

Setting the Stage

What do marathon running, music, martial arts and programming all have in common? They all have ‘exit points’ where large numbers of participants drop out. Typically exit points occur when a meaningful goal has been met, but the distance to the next is intimidating.

For example lots of people start running to get fit, but quit once they reach a particular level. I’m sure you know someone who ran a single marathon and then hung up their trainers.

In coding exit points exist in individual languages, such as Scala’s Cliffs Of Insanity. But they also apply to programming styles in general. Lambda Conf published a Ladder of Functional Programming to document levels of attainment in FP. This is as intimidating as it is informative, so I would propose adding a few more rungs to make the climb less fraught.

Personally I categorise the levels of learning within FP as follows:

1. Lambdas and the core operators (filter, map and forEach)
2. The standard FP Toolkit (flatMap, reduce, partition etc…)
3. Custom higher order functions, currying and partial invocation
4. Functional types and composition (Option, Either, Validated etc…)
5. Here be Dragons…

Many folks (quite rightly) stop when they have learned all they need for their current project. I’m going to assume that you are somewhere around levels 3 or 4, and interested in learning more. But you’re a practical coder, unwilling to tolerate a tsunami of theory. So we begin with a very useful operator you probably haven’t heard of.

Introducing Traverse

Let’s say you have a colleague, who has recently been on a Kotlin course with an [ahem] highly skilled and friendly instructor. As part of this they were exposed to the Arrow framework and its functional data types. One day you come across this in the codebase:

Apparently your colleague, in an attempt to be helpful, has wrapped up the getProperty method so that it returns an Either. Should the property exist we get back a Right containing the result, otherwise it’s a Left containing an error message.

Todays work requires that you fetch the values of three properties, so you write a Spike to try it out:

These are the results you get:

[Right(test1.txt), Right(test2.txt), Right(test3.txt)]
[Right(test1.txt), Left(No JVM property: false), Right(test3.txt)]

Clearly a List of Either is an annoyance. There are operators, such as all, any, filter and partition, that you could use to process Left and Right values. But it’s still going to be gnarly code.

It occurs to you that this is the opposite of what you need. Ideally you would like a function that gave you one of these:

• A Right containing a list of results
• A Left containing an error message

This is the service provided by traverse.

Traverse in Action

Here’s an implementation that does what we want:

We take a list of property names and traverse, rather than map, over them. This has the effect of switching the types around. Should everything work what is returned will be a Right<List> rather than a List<Right>.

Since the result of the call is now an Either we can fold over it. We pass in two lambdas or functions, the first to be called on failure and the second on success. The easy way to remember this is that the right input handles the right result.

Let’s try it out to make sure:

This is the resulting output. As you can see it’s exactly what we need:

Results are:
 test1.txt
 test2.txt
 test3.txt
No JVM property: false
No JVM property: false
No JVM property: false

Investigating Our Success

Huzzah! So the purpose of traverse is to invert the types we are working with.

We use traverse when:

• We are iterating over a list of values
• We need to apply an action to each value
• The action returns a Foo container
• We want a Foo<List>, not a List<Foo>

In this case the action is propertyViaJVM and the container is Either. A call to map would give us a List<Either>, whereas a call to traverse gives us the (more useful)inversion of Either<List>.

If you look at the code a little more closely you will see there are two magical aspects. As promised we are focusing on application rather than theory, so for the moment let’s just say that:

• The Applicative passed as the first argument to traverse enables it to invert the types. There needs to be a specific Applicative for each type.
• The calls to fix are necessary to perform type conversions. Behind the scenes Arrow is emulating something called Higher Kinded Types.

The next two articles in this series will cover these topics in detail. But we already know enough to move on to more complex examples.

Traverse and Files

Let’s say our functional friend is also in charge of the code to retrieve values from a properties file:

Here we’re using the Java Streams API to read the appropriate value from the given file. Again it’s an Either being returned. Should all go well it will be a Right holding the property value. If the file cannot be read, or the property does not exist, it will be a Left containing an error message.

Once again we need to read the value of three properties. Now we know the secret we can jump directly to traverse.

Notice that the code is almost the same as before. We just need to manage a file name as well. Let’s check it works:

Here’s the output:

Results are:
 test1.txt
 test2.txt
 test3.txt
No property called false
No property called false
No property called false
No file called false.properties

Once again traverse has made our lives simpler, and enabled us to handle errors gracefully.

Enter the Monad

Because Either is a Monad we can compose calls together in a very neat way.

Imagine that our task has four interdependent steps, as follows:

1. We need to access the values of three JVM properties
2. The value of each of these properties will itself be a key used in a properties file
3. The values held in the properties file are names of text files containing data
4. We want to read and output all the data

This sounds like a lot of work. But based on what we’ve done so far it’s not too hard. First we need a function to attempt to read all the lines from a file:

Then we can bring together everything we have done so far:

This time we use the either function to join together findViaJVM, findViaFile and readEverything. Underneath the hood suspending functions are being using to implement Monadic composition, but that’s a subject for another article. For now it’s enough that it works.

To prove that here’s a sample main method. Note that because either is suspending both demoTraverse and main need to be as well.

The names are a tribute to 1970’s cop shows. Here’s the content of the properties file:

cagney.lacy=test1.txt
starsky.hutch=test2.txt
hart.hart=test3.txt

When we run main it successfully finds the files are prints out the contents.

That’s quite a distance we have covered! Worth taking a moment to down a caffeinated beverage and celebrate our awesomeness…

Switching to Validated

In all our code so far we have been using the Either type to represent a result or an error message. This is perfectly legitimate, but the Validated type is intended for precisely this purpose. So we could rewrite our existing code to use it instead.

For example, here’s our refactored propertyViaJVM method:

The demoTraverse method barely changes. But note that when we create the Applicative we must also pass in a Semigroup for strings. This is because the Validated type will provide the additional service of concatenating all the error messages we encounter.

The wider point is that we can use traverse with any monadic type. Another great example would be performing several network operations, and obtaining a Future<List> rather than a List<Future>. As no one seems to agree on HTTP Clients these days I leave that one as the dreaded exercise for the reader…

Conclusions

Hopefully this article has added traverse to your FP arsenal, and wetted your appetite to know how else FP can simplify your code. That’s what I intend to cover. But before that we need to consolidate what has been achieved so far.

During this article we have used Applicatives, Semigroups and Higher Kinded Types, without properly defining what they are. The next few articles in this series will address each of these. But if you would like to read ahead the Arrow Glosssary is a great place to start. See you next time…