Why Functional Programming? It’s the composition.

Published in

iHeartRadio Tech

14 min readJul 7, 2017

Divide and conquer has been a core strategy in software engineering. We decompose our systems into smaller modules with focused, simple functionalities and compose them back to provide richer features. In a complex modular system, developers regularly have to dedicate a significant portion of code and effort to such composition.

Needless to say, it provides fundamental benefits to be able to compose and decompose computation with ease. This is where Functional Programming (referred to as FP) mainly focuses on. For developers who wonder what difference FP makes, this blog post aims to give a taste of how it enables more natural composition. I am going to focus on one particular and yet common factor that makes computation composition cumbersome in imperative programming — effects.

Simple function composition

Let’s start with two Scala functions with the return type of one matching the input type of the other. That is, given

def f(a: A) : B

and

def g(b: B) : C

To compose them generically, we just call f first and then g.

def compose[A, B, C](f: A => B, g: B => C) : A => C =
   a => g(f(a))

Note here that we used a different Scala type notation for function: A => B.

Our compose function is a simple and universal way to compose any two functions with matching output and input types. However, in real-world applications, we don't get to use it very often because functionalities (modules) are rarely as pure as mathematic functions - they often return null, throws exceptions, being asynchronous, etc. These behaviors can be thought of as extra effects on top of the pure functions. Let's take a closer look at how these effects affect the composition.

For a function f that might return null, the composition code would have to look like this to avoid null point exception inside g:

val b = f(a)
if(b != null) g(b) else null

In the case where f might throw exceptions, we need to try-catch exceptions to avoid it blowing up the application. Our composition code would look something like this:

val b = try {
  f(a)
} catch e {
  print( "(╯°□°）╯︵ ┻━┻ " )
  null
}

Finally, when the f is asynchronous, it usually means that we have to pass in g as callbacks, the composition would probably look like:

f(a, callback = { b => 
  g(b) 
})

Indeed these manual effect handling compositions are very common and repetitive patterns in imperative programming code bases. They are verbose which makes the core business logic difficult to read; they have complex logic branches that make the program harder to reason with. They are also error-prone, e.g. if you miss a “null” check, it’s not checked by the compiler, it’s also hard to spot during code reviews. More importantly, these effects handling composition code is effect specific — if the effect changes, the composition code has to change accordingly. In other word, the composition is dependent on an implementation detail of modules, which, as we all know, is an enemy of modular design.

So, is there a simple and universal way to compose these functions?

Encode effects with types

We can make these effects explicit using types. For example, in the case of returning null, instead of simply specifying it in the documentation, we model it using the type Option which looks like

sealed abstract class Option[T]
case class Some[T](value: T) extends Option[T]
case object None extends Option[Nothing]

The type Option[T] can have two possible values: a Some(t) and a None. So instead of return a B, f returns an Option[B] to make the might-return-null effect explicit.

f: A => Option[B]

Let’s do the same with the throw-exceptions effect. We can return an Either[E, B] type - it's either the result B or some error E.

sealed abstract class Either[E, T]
case class Left[E, T](e: E) extends Either[E, T]
case class Right[E, T](t: T) extends Either[E, T]

Again the type Either[E, T]has two possible values, a Left(e) that represents an error of type E, or a Right(t) that represents the successful result. Now we can rewrite f as:

f: A => Either[E, B]

As for the asynchronous f, we just need a type that can add callbacks, and yes, that's Future[T].

f: A => Future[B]

As we demonstrated above, we can encode effects explicitly using types. Furthermore, by making them explicit, we made it possible to generalize them. Our functions now return an effect container type of B instead of a B, if we abstract out our effect container type as F[_], our composition problem can be generalized to the following formula:

Given a

val f: A => F[B]

and a

val g: B => C

how do we get a composed function:

val composed: A => F[C]

Note that we are preserving the effects, i.e. keeping F[C] as the result type of composed, which will be handled eventually but not during composition.

Handle effects in a generic way

Let’s try to write a new compose function that handles effect generically.

def composeF[A, B, C, F[_]](f: A => F[B], g: B => C): A => F[C]

To create this new A => F[C] function, first we have the input a: A, naturally we can apply it to f: A => F[B]

(a: A) => 
   val fb: F[B] = f(a)
   ...

We get a F[B], we need a F[C], but all we have is a g: B => C. Obviously, if we can convert a B => C to a F[B] => F[C] then the problem is solved, that is, we need the following function (let's call it lift).

def lift[F[_], A, B](f: A => B): F[A] => F[B]

So for whatever effect F[_], if we have an implementation of the above lift function, we can complete our composeF:

def composeF[A, B, C, F[_]](f: A => F[B], g: B => C): A => F[C] =
  (a: A) => lift(g)(f(a))

Let’s implement this lift for the effect container types mentioned above. For Option[_]

def lift[A, B](f: A => B): Option[A] => Option[B] =
  (oa: Option[A]) => 
    oa match {
      case Some(a) => Some(f(a))
      case None => None
    }

For Either[E, _]

def lift[A, B](f: A => B) : Either[E, A] => Either[E, B] =
   (oa: Either[A]) => 
      oa match {
         case Right(a) => Right(f(a))
         case Left(e) => Left(e)
      }

Both are trivial to implement. You might notice that it’s actually just a different but equivalent form of the better known mapmethod:

def map(fa: F[A])(f: A => B): F[B]

To show that they are equivalent, we can write lift in terms of map

def lift[A, B](f: A => B): F[A] => F[B] = 
   (fa: F[A]) => map(fa)(f)

Both Option[_] and Either[E, _] has a map defined in the class, Future[_] has one too:

class Future[A] {
  def map[B](f: A => B) : Future[B] = ...
}

Now we know that if we have a lift(or map) for our effect type F[_], we can easily compose A => F[B] and B => C. Option[_], Either[E, _], Future[_], List[_], we know quite some container types that has map and thus lift.

However, would any lift implementation work? Imagine we have a map for the Option[_] that returns a different b inside the Option than the original f would return for the same input. Or imagine we have a map for Either[E, _] that returns a Left(e) when the input is a Right(a)? Those obviously wouldn’t work for our composition. There seems to be a condition that map (or lift) has to satisfy to support sound composition. Maybe we can put this condition this way: if we see a function f: A => B as a relationship between A and B, we want our lift to return a function that kind of preserves that same relationship between the F[A] and F[B].

Being software engineers, it immediately comes to our mind that we need to write tests to check if implementations of liftsatisfies this condition. However, it seems that to assert that the result F[B] has the expected B inside, we need to peek inside the result F[B]. And to be able to peek inside the effect type F[_], we would need some specific knowledge of F[_]. This brings us back to the original problem - we want a universal way to compose functions, we abstracted out a step as liftbut now our test against it is still F[_] specific, that is, we still lack a way to specify a generic composition for effectual functions.

Is there a way to write tests for lift implementations that is effect type F[_] agnostic? It seems that we need to gain a deeper understanding of the conditions.

Category Theory

It’s time for category theory to enter the stage. Category theory studies morphisms between objects and the composition of them. It avoids involving direct knowledge in regards to the internals of the objects. This subject looks promising to us — we are looking for ways to compose effectual functions without the direct knowledge of the effect types.

Let’s start by making a connection between category theory and computer program computation. A category, as defined in the category theory, consists of objects and morphism between them that satisfy three conditions (called laws in category theory). One of them is demonstrated in the following diagram. Given f as a morphism from X to Y, g as a morphism from Y to Z, there must be a composed morphism g•f that is equivalent to applying f first and then g.

In other word, if one morphism’s end object is another morphism’s origin object, then the two morphisms must compose. This condition looks an awful lot like the function composition in the programming world — we can treat types as objects, and functions as morphisms between the types. Since functions compose, we do have the composed morphism g•f. In fact, types and functions as objects and morphisms also satisfy the other two conditions (the identity law and the associativity law) to form a category. The programming model of types and functions form a category. Now we have a new powerful tool at our disposal.

Functor

Is there something in category theory that can map to our F[_] with a lift function? Yes, it's called functor.

From the diagram, we can see two spaces: in the upper space, a f sits between x and y, and in the lower space, a corresponding F(f) between F(x) and F(y). There is a mapping between these two spaces. Our lift is just like the mapping between x => y and F(x) => F(y). In fact, the first space of f, x, y is a category, and it is proven in category theory that if the F(f), F(x), F(y) also forms a category, the structure of the f, x, y category is preserved in category of F(x), F(y) and F(f). We call this structure preserving mapping between the two categories, represented by F[_], a functor.

This is great news because we were searching for a way to test if a lift preserve the relationship while enabling composition. From category theory we now know that we just need to check if thelift(f), F[A], and F[B] forms a category. More importantly, in category theory, we never need to know what is inside the objects. In other word, we no longer need to look inside the F[A]or F[B] which are the objects.

How do we check if they form a category? Recall that to form a category; there are three laws to abide, we just need to check our lift and F[_] against them. In this post, we are going to take the composition law as an example.

The composition law says that if we have a f: A => B and g: B => C, there must be an equivalent composed g•f: A => C. So in our F space, we have a lift(f): F[A] => F[B] and lift(g): F[B] => F[C], since f and g compose, we also have a lift(g•f): F[A] => F[C]. To satisfy the composition condition, the lift(g) • lift(f) and lift(g•f) must be equivalent. We can write a test so that:

lift(g) • lift(f)  === lift(g•f)

There we have a law for our lift function, and it doesn't need to peek inside the content of effect type F[_] and hence is effect agnostic.

Yah! Thanks to category theory, we now have a universal way to check lift functions and thus a universal way to compose f: A => F[B] with g: B => C. However, this won't get us very far. It's more common that both f and g has effects. What we truly need is a universal way to compose f: A => F[B] and g: B => F[C].

Compose functions with effects

This time our composition function signature will be:

def composeM[A, B, C, M[_]](f: A => M[B], g: B => M[C]): A => M[C]

Note that to differentiate from the previous functor case, we used a different effect type name M[_]. To create this new A => M[C] function, we'll have an a: A as input and the first step we can do is to apply f

(a: A) => 
   val fb: M[B] = f(a)
   ...

Now we have a fb: M[B] and a g: B => M[C] left but g doesn't take a M[B]. Let's get some help from functor, using the lift function we can lift g to take M[B]

val fg: M[B] => M[M[C]] = lift(g)

The fg we get from lift takes M[B]s, but the return type is now a M[M[C]], because the lift puts on a layer of M[_] on both the input type and the return type. Nevertheless, let's pass the fb: M[B] we got from the first part in:

val mmc: M[M[C]] = fg(fb)

We get mmc: M[M[C]] but we need an M[C]. It seems that to complete the puzzle; we need a function can somehow collapse two nested M[_] into one, let's call it flatten.

def flatten[M[_], T](mmt: M[M[T]]): M[T]

Let’s write a flatten for Option[_]

def flatten[T](oot: Option[Option[T]]): Option[T] = oot match {
    case Some(Some(t)) => Some(t)
    case _ => None
}

The flatten for Either[_] is similar, I'll leave it as a reader exercise for readers.

Would any implementation of flatten work? The answer is again no. There is probably a set of conditions under which this flatten can guarantee the soundness of the generic composition of effectual functions. But it's rather hard to put your finger on it, isn't it?

Discovering Monad

You guessed it. This problem is already solved in category theory — there is a special category called kleisli category in which functions like f: A => M[B] compose through two transformations defined for the functor M[_]. One of them is precisely our flatten: M[M[A]] => M[A]. The other is A => M[A] .

These two transformations together with the functor M[_] is called a monad. Just like in the functor case, for the monad to actually form a kleisli category, it must satisfy the three category laws. Again, thanks to category theory, now we can write effect agnostic tests for our flattenimplementations to ensure the soundness of our composition. We are not going to the details of these tests in this post (they are readily available online).

Here is how we can define functor and monad in scala.

trait Functor[F[_]] {
  def lift[A, B](f: A => B): F[A] => F[B]
}trait Monad[F[_]] extends Functor[F] {
  def pure[A](a: A): F[A]
  def flatten[A](mma: F[F[A]]): F[A]
}

Then we can start to write the tests for them according to the laws specified in the category theory. However, as you might’ve guessed, there are already libraries such as cats and scalaz providing such definitions and law tests so that we don’t have to.

Let’s complete the composeM

def composeM[A, B, C, M[_]](f: A => M[B], g: B => M[C])(implicit M: Monad[_]): A => M[C] =
  (a: A) => {
     val fb: M[B] = f(a)
     val fg: M[B] => M[M[C]] = M.lift(g)
     M.flatten(fg(fb))
 }

Now we can generically compose any two effectual functions with a simple composeM(f, g), no manual effect handling needed.

Monadic composition in Scala

Finally, we proved that there is a universal way to compose functions with effects. We just need to encode the effect as a type that forms a monad. To form a monad, we need to implement lift and flatten and make sure they pass the law tests.

In FP, we often refer to this composition as monadic composition. The Scala language provides a convenient syntax sugar for it. It’s the familiar for loop syntax - to compose f: A => M[B] and g: B => M[C] you can write:

for {
     b <- f(a)
     c <- g(b)
   } yield c

This is a bit more verbose than the composeM but more flexible and sometimes more readable.

A realistic example of monadic composition

Enough theories. Let’s take a look at a realistic example to see how this universal composition improves our programs. In this example, we are writing a program that can send a “like” on a Facebook post on the user’s behalf. We have two modules at our disposal:

a UserService that validates a sessionToken and gets the user's Facebook access token
a FBService that finds the post by url and sends "like"s.

In an imperative programming code base, these two modules would probably be modeled as traits to hide any implementation details:

trait UserService {
  def validateUser(sessionToken: SessionToken): UserId
  def facebookToken(uid: UserId): FBToken 
}trait FBService {
  def findPost(url: Url): FBPost
  def sendLike(fbToken: FBToken, post: FBPost): Boolean  //return true if succeeds
}

Composing these methods into a send “like” feature sounds straightforward. However, all these methods return null if the result is not found, thus in the imperative programming paradigm, we have to deal with this might-return-null effect in our composition code. The composition would probably look like:

class Program(
  userService: UserService, 
  fbService: FBService) {
  def likePost(sessionToken: SessionToken, postUrl: Url): Boolean =        
  {
    val uid = userService.validateUser(sessionToken)
    if(uid == null)
      false
    else {  
      val token = userService.facebookToken(uid)
      if(token == null)
         false 
       else {
         val post = fbService.findPost(postUrl)
         if(post == null)
           false
         else
           fbService.sendLike(token, post) 
       }
    }   
  }
}

It’s rather unfortunate to have to write that many lines when all you do is to compose 4 methods. The business logic is buried in the effect handling code which is overly complex and error-prone. More importantly, this composition is effect specific. We are handling “might return null” effect here, but if we need to add another effect, e.g. making it asynchronous, we have to rewrite it with even more complex statements. These effect handling composition code is how we blow a straightforward business logic into hundreds or even thousands of lines of code.

In FP, we would model our modules with an abstract effect type F[_].

trait UserService[F[_]] {
  def validateUser(sessionToken: SessionToken): F[UserId]
  def facebookToken(uid: UserId): F[FBToken]
}trait FBService[F[_]] {
  def findPost(url: Url): F[FBPost]
  def sendLike(fbToken: FBToken, post: FBPost): F[Unit] 
}

We make our effect type abstract because as method implementations, it’s just an implementation detail.

Now, let’s write our program.

class Program[F[_] : Monad](
  userService: UserService[F],
  fbService: FBService[F]) {
  def likePost(sessionToken: SessionToken, postUrl: Url): F[Unit] = 
    for {
      uid     <- userService.validateUser(sessionToken)
      fbToken <- userService.facebookToken(uid)
      post    <- fbService.findPost(postUrl)
      _       <- fbService.sendLike(fbToken, post)
    } yield ()
}

Note here we used the context bound to specify that whatever concrete effect type F[_] is, it must be a Monad for us to use monadic composition.

With Monad, we achieved two things: first, the composition is as concise as can be and thus making the business logic crystal clear; more importantly we are effect agnostic. We can make our service return any F[_] (as long as it is still a Monad) and this composition code remains the same. This gives us a lot more flexibility when we need to add more effects to our program. For instance, if we need to make our program asynchronous, we just need to switch to an asynchronous DB library and an asynchronous HTTP client, the compositions code above remains the same.

Conclusion

In imperative programming, a great portion of the application code is the repetitive effect handling in compositions, which is cumbersome, error-prone, and very effect specific. This makes our application unnecessarily complex, obscure and rigid to effects. Functional programming, powered by category theory, provides ways to compose components with effects in a concise and effect agnostic way. Such easy compositions make our application significantly more flexible, robust, and easy to read and reason with.

Thank you for reading this long post. If you have any feedback, questions, please leave a comment, I will do my best to answer them.