So you want to compose some functions

Dr. Lars Hupel

This post assumes basic experience with functional programming in Scala/Cats, Haskell or other languages.

The problem

The other day a colleague asked a question in our internal Scala channel. They were writing some Scala code and assembled a list of functions DomainType => Eval[DomainType]. This list represents a “pipeline” of sorts and they wanted to run all of them, one after the other. The Eval type comes from the Cats library and represents a lazily-evaluated computation. To keep things simple, let’s assume the functions had the type Int => Int.

The easiest solution would be a fold:

val funcs = List((x: Int) => x + 1, (x: Int) => x * 2)

def eval(x: Int): Int =
  funcs.foldLeft(x)((accum, f) => f(accum))

Let’s try this out:

@ eval(1)
res1: Int = 4

@ eval(4)
res2: Int = 10

Nice! Working as expected. Now we can just extend this to Eval (using flatMap) and call it a day, right? Well, no. We were looking for something elegant! The eval function has to do a manual fold. But us functional programmers are lazy. We want to (ab)use some more abstract machinery to turn this into a one-liner.

The problem (but abstract)

Let’s first hash out the types of the things we’re interested in.

We start with a list of functions with identical input and output type. We want to obtain a function with the same type.

That sounds an awful lot like a higher-order function. What’s its type signature?

def mystery[T](funcs: List[T => T]): T => T

Cool. But is the List really relevant? After all, if we know how to compose two functions, we can generalize that to an arbitrary amount of functions.

def mystery1[T](f: T => T, g: T => T): T => T

Something about that rings a bell. We’ll fetch our beloved algebra text book and look this up. What do we find?

A monoid is a triple (M, ∘, e) where M is a set, ∘ a binary operator and x ∈ M that satisfies the following properties:

1. ∘ is closed, that is, for all x, y ∈ M: x ∘ y ∈ M
2. e is the identity of ∘, that is, for all x ∈ M: x ∘ e = e ∘ x = x
3. ∘ is associative, that is, for all x, y, z ∈ M: (x ∘ y) ∘ z = x ∘ (y ∘ z)

Ah, right. Good old monoids!

Monoids in programming

Unable to follow? No problem. All of the above is how a mathematician would express the concept of a monoid. In Scala, we can use some more familiar terms:

trait Monoid[T] {
  def empty: T
  def combine(first: T, second: T): T
}

This definition conveniently uses words instead of symbols. But there’s a clear mapping between those concepts:

• the type parameter T corresponds to the set M,
• the empty method corresponds to the identity element e, and
• the combine function is the binary operator ∘.

Cats and other libraries provide these trait representations for use as type classes.

Before we get to the main issue of this post, let’s briefly discuss how to map the mathematical properties to the Monoid trait. The first one is a given, because the types already prescribe that combine returns a value of the same type. The second and third properties can be expressed in ScalaCheck and must be tested manually.

The function monoid

Cats already ships with a ton of monoid implementations. Let’s check if we can find one for our functions:

@ Monoid[Int => Int]
res3: Monoid[Int => Int] = cats.kernel.instances.FunctionInstances$$anon$3@498bfeec

That’s dandy. Conveniently, there’s also a pre-defined method on the Monoid trait that’s called combineAll and recursively applies combine to a list of things (in other words, it performs the folding for us):

@ val func = Monoid[Int => Int].combineAll(funcs)

@ func(1)
res4: Int = 4

@ func(2)
res5: Int = 7

Uh oh. That looks unexpected. Maybe it composed those functions the other way round? Well, no, because 7 is not the result of taking 2, doubling it (4) and adding 1 (5) either. What happened here?

Are monoids unique?

I hate to break it to you, but monoids are not unique. That means that for any given type, there may be more than one valid instantiation of the Monoid trait.

For starters, switching around the combine operation always makes for a valid monoid, if the original one was valid:

def swap[T](implicit MT: Monoid[T]): Monoid[T] = new Monoid[T] {
  def empty = MT.empty
  def combine(first: T, second: T) = MT.combine(second, first)
}

Does the order matter? Not for common arithmetic operations, but there are certainly monoids for which it does matter:

@ Monoid[List[Int]].combine(List(1), List(2))
res6: List[Int] = List(1, 2)

@ swap(Monoid[List[Int]]).combine(List(1), List(2))
res7: List[Int] = List(2, 1)

Concatenation of lists is certainly a monoid: the empty element is Nil and to combine two lists we just use :::.

The mathematicians have a particular name for this. If in an operation ∘, the order of arguments does not matter, the operation is called commutative. Formally: for all x, y: x ∘ y = y ∘ x.

If in a monoid, the operation is commutative, that monoid is called abelian (after the mathematician Niels Henrik Abel).

Long story short: for any non-abelian monoid, we can easily construct a different monoid by just flipping the order of arguments! (For abelian monoids, the swapping doesn’t change the operation.) In consequence that means that we can’t necessarily talk about “the list monoid” or “the monoid for type X”, because there might be more than one.

It appears that there is something similar going on for our functions.

Very much not unique

It gets worse. We can define multiple competing monoids for lots of structures, without resorting to tricks like swapping the arguments:

1. For Option, we can either return the first Some or, when encountering two Somes, combine the contained values.
2. For List, instead of concatenation, we can “zip” them together (discarding extra elements if one list is longer than the other) and then combine the elements.
3. For any ordered type, we have a monoid where combine returns the maximum (or minimum) of the two arguments (monoid formed by a lattice).
4. For any type at all, we can define a monoid that just returns an arbitary “neutral” value or always the first value or …

About those functions

Now, let’s investigate what the default function monoid from above does. Here’s a brief reminder:

@ val funcs = List((x: Int) => x + 1, (x: Int) => x * 2)
@ val func = Monoid[Int => Int].combineAll(funcs)

@ func(1)
res4: Int = 4

@ func(2)
res5: Int = 7

Got an idea?

The solution of this puzzle is as follows:

def functionMonoid[A, B](MB: Monoid[B]): Monoid[A => B] = new Monoid[A => B] {
  def empty: A => B = a => MB.empty
  def combine(f: A => B, g: A => B): A => B =
    a => MB.combine(f(a), g(a))
}

This construction is called pointwise. Again, there is a meaning behind the term point (it’s from category theory), but that’s besides the point here (pun intended).

All so-called pointwise operations on functions follow the same structure: they take a function argument x and then apply all functions on the same argument x and combine the results somehow. Here, it literally uses the combine method for the return type.

This also explains why this monoid for A => B only requires a monoid implementation for B, but not for A.

In languages with stronger type inference than Scala, like in Haskell, we can completely get rid of those type parameters. Some readers may find this clearer (if not, just ignore it):

instance Monoid b => Monoid (a -> b) where
    mempty x = mempty
    mconcat f g x = mconcat (f x) (g x)

Type inference will figure out that the mconcat on the right-hand side is the one for b, whereas the one on the left-hand side is the one for a -> b.

Frequently, functional programmers call such a construction like functionMonoid a lifting. The reason is that we take an existing structure (a monoid) over a type B and raise it into a new context (A => _).

def applicativeMonoid[F[_] : Applicative, A: Monoid]: Monoid[F[A]] = new Monoid[F[A]] {
  def empty = Applicative[F].pure(Monoid[A].empty)
  def combine(x: F[A], y: F[A]) =
    (x, y).mapN(_ |+| _)
}

@ val func = (applicativeMonoid: Monoid[Int => Int]).combineAll(funcs)

@ func(1)
res8: Int = 4

@ func(2)
res9: Int = 7

trait Semigroupal[F[_]] {
  def product[A, B](fa: F[A], fb: F[B]): F[(A, B)]
}

def empty[A]: F[A]

But clearly, this is not the monoid we are looking for.

Monoids that compose

Let’s get back to the original mystery function we posited above:

def mystery1[T](f: T => T, g: T => T): T => T

Notice that as opposed to the monoid we saw above, we don’t have A => B (i.e. different parameter and return type) but T => T (i.e. same parameter and return type).

Haskellers tend to call such functions endo, which stems from the mathematical term endofunctor. In my opinion, this naming is not entirely accurate, but let’s roll with it. We can define a monoid for this type as follows:

def endoMonoid[T]: Monoid[T => T] = new Monoid[T => T] {
  def empty = t => t
  def combine(f: T => T, g: T => T) = f andThen g
}

Let’s verify that this works:

@ val func = endoMonoid.combineAll(funcs)

@ func(1)
res10: Int = 4

@ func(4)
res11: Int = 10

Nice! Working as expected.

Before we move on to the final complication, namely the return value that’s wrapped in Eval, let me point out a very sad thing: this monoid is almost never abelian, because you can’t just flip the order of function composition. That means that you’ll have to be excrutiatingly careful when composing functions like this (not that that would be any different when using folds).

For the (frequent) use case of having a function that returns a value wrapped in a type constructor, Cats offers a convenient abstraction:

case class Kleisli[M[_], A, B](run: A => M[B])

It comes with compose functions and everything that employ the flatMap method of M. The name Kleisli comes from the mathematician Heinrich Kleisli.

We can also find a monoid instance for this, but it is slightly involved, as it goes through a bunch of other abstractions:

@ Kleisli.endoMonoidK[Eval].algebra[Int]
res12: Monoid[Kleisli[Eval, Int, Int]] = // ...

Now we just need to consider our actual list of lazy functions:

val lazyFuncs = List(Kleisli((x: Int) => Eval.later(x + 1)), Kleisli((x: Int) => Eval.later(x * 2)))
val func = Kleisli.endoMonoidK[Eval].algebra[Int].combineAll(lazyFuncs)

Let’s try this out:

@ func(1).value
res12: Int = 3

@ func(4).value
res13: Int = 9

Well, those have clearly been executed in the wrong order! I said careful!

@ val func = Kleisli.endoMonoidK[Eval].algebra[Int].combineAll(lazyFuncs.reverse)

@ func(1).value
res14: Int = 4

@ func(4).value
res15: Int = 10

Much better! Now, what do we learn from this?

Disambiguation

Choosing the correct monoid is hard. Unfortunately, all of the different monoids for a given type are standing in each other’s way. Type systems like Scala’s and Haskell’s however expect only at most one possible type class instance for a given type. That’s why classes like Kleisli exist, in order to somewhat artificially construct a distinct type that – while having the same capabilities as the original type – may have different instances. For endo functions like in this blog post, this is currently still missing in Cats.

What do we learn from this? Monoids are an ubiquitous and versatile structure in functional programming and we’d better double-check which one we have before doing anything with it.