Functional Composition

One language feature I’m a big fan of is the ability to compose functions.

A great step on the functional programming journey comes when you realise that most of the problems we are solving are just a series of functions applied one after the other. If we are just chaining functions together, do we really need to bother passing the variables between them? This is the essence of composition - combining functions together without involving variables.

I’ll be focussing on Scala, but it’s worth having a quick look at how other languages handle composition - I think Scala could learn a thing or two.

What Is It?

When we compose two functions, we create a new function which applies one function to the result of the other. If I have one function a -> b which takes an a and gives a b, and another b -> c which takes a b and gives a c, I should be able to combine them into one function a -> c which takes an a and gives a c. No middle man.

Here’s how we do it in F#, with an example which doubles, then squares, then adds one to a number:

let addOne x = x + 1
let square x = x * x
let double x = x * 2
let allThree = addOne << square << double

// allThree 10 = 401

This is very similar to how we could write it in haskell:

addOne = (+) 1
square x = x * x
double = (*) 2
allThree = addOne . square . double

-- allThree 10 = 401

In F#, the << is our composition function. In haskell (the undisputed king of composition), function composition is such an integral part of using the language, it is given the prized . operator. Both languages take the mathematical approach of applying the right function first (as in left(right(x))), with other functions available for forward composition (>> in F#).

Scala gives us two different functions for composing backwards and forwards, called compose and andThen. While these names make perfect logical sense, I find them both annoyingly long and wish we had a shorter option.

If you’re like me, you will have jumped straight into the Scala REPL after learning about this, and stumbled.

Why Doesn’t This Work?

def addOne(x: Int): Int = x + 1
def square(x: Int): Int = x * x
def double(x: Int): Int = x * 2
def allThree = addOne compose square compose double

// error: missing argument list for method addOne

The full compiler error we get here is actually very helpful:

Unapplied methods are only converted to functions when a function type is expected. You can make this conversion explicit by writing addOne _ or addOne(_) instead of addOne.

If we try again, following this advice, we get:

def allThree = (addOne _) compose (square _) compose (double _)
// allThree(10) = 401

It works, just not quite as well as I had hoped. What’s with the ugly underscores and brackets? And what does the compiler mean by “unapplied methods are only converted to functions when a function type is expected”?

It turns out we’ve failed to make a distinction important to the scala compiler: methods and functions are not the same. I don’t have a good enough understanding to dive into this here, so if you want to learn more, have look at Jim McBeath’s blog on the subject.

To summarise, the methods we defined earlier, using def, are linked with the class in which they are defined. Functions are different. They are completely self-contained, and we define them like this:

val f = ((x: Int) => x + 1)
val g = ((x: Int) => x * x)
val h = ((x: Int) => x * 2)
val fgh = f compose g compose h

// fgh(10) = 401

We can make more sense of the earlier error message now. We had tried to pass our methods without any arguments applied (hence “unapplied methods”) as functions, but the compiler did not know to expect a function type, so it would not compile.

This suggests that if we explicitly state that we require a function type, we should be able to pass our methods as functions:

// Assign a method to a function
val fAddOne: Int => Int = addOne
// compiles!

We can also manually translate a method into a function using this syntax:

// Side note: I find this syntax absolutely baffling.
// Why an underscore?!
val myFunction = myMethod _

This is what was happening in the allThree example above - the underscores after the method names are indicating that they should be passed as functions.

But surely, the compose method takes a function as a parameter, and so the compiler should know to perform the conversion?

Not quite… unlike haskell and F#, where the compose function is defined standalone, taking two functions as parameters, Scala’s compose is defined on the Function1 trait.

When we define a function, we are creating an instance which implements Function1 under the hood.

This means we need to start with a function, and use the function’s compose method to join it with others. The compiler should be able to convert methods passed to compose into functions:

// Compiler will convert methods square and double to functions.
def allThreeA = (addOne _) compose square compose double
def allThreeB = fAddOne compose square compose double
// Remember that the infix notation hides the fact that "compose"
// is itself a method, belonging to the Function1 trait
def allThreeC = fAddOne.compose(square).compose(double)

A Compose Example

I’ve gone way off track, whoops. I find composition to be particularly useful when mapping over things - here’s a contrived blog example, probably not useful in real life, but hopefully gets the point across.

Let’s say we have a list of integers to which we want to apply various combinations of our functions from earlier. First of all, we need to convert all our methods to functions - I’ll explicitly declare them first this time.

// We need functions, not methods.
val fAddOne: Int => Int = addOne _
val fSquare: Int => Int = square _
val fDouble: Int => Int = double _

// A range of ints
val ints = 1 to 10

// Lets do a bunch of different combinations of functions to them.

// Just double them:
val doubled = ints.map(fDouble)
// Vector(2, 4, 6, 8, 10, 12, 14, 16, 18, 20)

// Square, then double, then add one:
val sqDubOne = ints.map(fAddOne compose fDouble compose fSquare)
// Vector(3, 9, 19, 33, 51, 73, 99, 129, 163, 201)

I think this is pretty cool, I just really wish there was a shorter alternative to writing compose or andThen each time. Especially in the world of aggressive scalafmt configurations, where every character is precious.

A Shorter Alternative

Maybe we can define our own compose function to work like the haskell/F# version?

compose is only nice to use when we can make use of the infix notation, and infix is only available for methods with a single parameter - presumably this is exactly why the existing compose function is defined on the Function1 trait. We could define our own trait with a << member to wrap the first function (f), but we would just end up re-writing Function1. For the record, I ended up with this:

// Trying to mimic F#?
def <<[A,B,C](f: B => C, g: A => B): A => C = f.compose(g)

// Yuck, I wish I had never tried.
def allThreeD = <<(addOne, <<(square, double))

Don’t give up! There actually is a quite elegant solution*.

Cats Arrow

The excellent cats library provides a type class called Arrow for working with composable types, however, just like EitherT (the subject of my previous blog post), I think Arrow suffers from some fairly incomprehensible documentation.

In the earlier example, I explicitly converted each method to a function in order compose them. Instead of doing this, we can convert them to Arrow instances:

// Import the Arrow type class.
import cats.arrow.Arrow
// Import implicit values.
import cats.implicits._
val aAddOne = Arrow[Function1].lift(addOne)
val aSquare = Arrow[Function1].lift(square)
val aDouble = Arrow[Function1].lift(double)

The first import is the Arrow type class, then we need an implicit instance of Arrow for Function1. This, along with a bunch of other implicits, is grabbed by import cats.implicits._ - I couldn’t work out how to only import the instance for Function1, so if you know, please get in touch. Importing absolutely everything in one statement makes me feel uneasy…

Anyway, we use Arrow.lift to wrap our methods in arrows, and by specifying Function1 as a type parameter we have told the compiler to treat our methods as functions. Arrows give us the >>> and <<< functions for forward and backward composition:

val aDoubleSquareAddOne1 = ints.map(aAddOne <<< aSquare <<< aDouble)
// Vector(5, 17, 37, 65, 101, 145, 197, 257, 325, 401)

val aDoubleSquareAddOne2 = ints.map(aDouble >>> aSquare >>> aAddOne)
// Vector(5, 17, 37, 65, 101, 145, 197, 257, 325, 401)

As one final bonus: unlike with compose, <<< and >>> are functions which take two arrows as parameters, and, as long as we have an implicit instance of Arrow for Function1 in scope, the compiler can automatically convert our functions to arrows. We don’t actually need to explicitly call Arrow.lift (just remember to import the implicits).

val bonus = ints.map(fSquare <<< double <<< addOne)
//Vector(16, 36, 64, 100, 144, 196, 256, 324, 400, 484)

We are even able to pass our methods (double and addOne defined way back at the top), as long as the first term the compiler hits is a function!

That’s all from me - I’ve barely scratched the surface of what you can do with Arrows (have a look at the documentation for proof), I’ve glossed over some Scala quirks with functions and methods, and type classes in Scala still behave annoyingly like magic to me. But I hope you found this useful anyway. Thanks for reading.

---

Edit (Thursday 27th December)

*Thanks to github user raquo for pointing out that I could use an implicit value class to implement a custom infix compose function without Arrow:

implicit class Compose[A,B](val self: Function1[A,B]) extends AnyVal {
  // Backward composition
  def <+[C](g: Function1[C,A]): Function1[C,B] = self.compose(g)
  // Forward composition
  def +>[C](g: Function1[B,C]): Function1[A,C] = self.andThen(g)
}

// We can use the methods on functions (or methods,
// if the compiler has enough type information).
val edit1 = fAddOne <+ double <+ double
val edit2 = fDouble +> (x => x * x * x)

The implicit class Compose wraps a Function1 and extends it with two new methods. As long as Compose is in scope, we will be able to call the new methods on any Function1 instances.

The extends AnyVal part makes this a value class, which optimises the way the code is used at runtime - I won’t go into them here but they are super useful, if you don’t know what they are, it’s worth reading up!

I also forgot to mention that self contained code examples for everything I have written about can be found here along with the source code for this blog.