Contextual programming

An introduction on functional programming, functors and monads

Functional programming is a paradigm focusing on the practice of composing programs using functions. As opposed to imperative programming languages, which focus on changes in state, most functional programming languages try to avoid mutable state.

When functions/programs only focus on immutable data transformations, so called purity can be reached. As pure functions don’t perform side effects when executed, global state won’t be mutated. When a function also doesn’t depend on state which can be mutated by other processes, you can expect that the input for a function will always result in the same output. This property of a function, often referred to as referential transparency, results in the fact that the the function can be replaced by its computed value without changing the behaviour of the program.

Purity and referential transparency help developers tremendously while writing safer and easier to maintain code.

This strong focus on functions, immutability and its restrictions may give you a bit off a setback when starting with a functional programming language; it may pull you a bit out of your comfort zone as the lack of mutability forces you to be more creative to solve even familiar problems.

Nevertheless, functional programming languages often help you to solve problems in a much pragmatical way as you normally would do in imperative and object oriented programming languages. When working with data collections, streaming data or asynchronous process flows, higher kinds of expressiveness is often desired and needed. Functional programming languages help to deliver this expressiveness by treating functions as first class citizens. As opposed to most imperative or object oriented programming languages, you can use functions in the same way as all other types or variables. This makes it possible to create functions returning new functions, or functions which take other functions as input arguments.

Functions which take or return new functions are called higher-order functions and are the fundamentals of most higher concepts implemented in functional languages. It can be mind-boggling at first, but it enables you to write functions which take, for instance, a list of functions and return a composed version of all functions passed.

Mapping

When new to functional programming languages, functional syntax can be quite daunting at first. Not all programming languages with FP concepts follow the path, but a large part of the more strict FP languages have syntaxes and mechanics inspired by the concepts of lambda calculus and category theory.

When you apply the concepts of category theory, the study of collections of objects and arrows, to computer science: objects (or concepts) can be treated as types like a String, Int or List and all other other available types within your programming environment. An arrow is, often called a “mutation” in theory, converts one object into another (although the term arrow is also a used for other concepts in some functional languages). When implementing an arrow within a programming language, this mutation can be interpreted as a function.

Syntax

Let’s look closer to the concept of objects and arrows by implementing a function which returns the length of a String:

def length(s: String): Int = s.length

The above function accepts a String as an argument and returns a value of Int. Technically, this means that we are converting or transforming a String into a Int with some added functionality. Therefore, the type of the above function can be defined as:

String ⇒ Int or String maps to Int

Because functions are first class citizens in Scala, we can also rewrite the function and use it as a variable. The syntax used makes the type signature a bit more clear:

val length = (s: String) ⇒ s.length

With this in mind, the function-type syntax in a functional programming language like Scala looks a lot more natural. When we encounter a function with a type signature of List[Int] ⇒ Int, we can immediately derive what the purpose of the function is: a function which accepts a List with zero or more numbers which maps it into a new number.

Higher ordered functions

Let’s look at an example of a higher ordered function; a function which accepts or returns one or more functions. Let’s define a function mapToStringList which accepts a List of Int and a function of Int ⇒ String, eventually returning a List of String:

def mapToStringList(l: List[Int], f: Int ⇒ String): List[String]

While the implementation of the function would probably use recursion (a technique often used in functional languages) to apply the function to every Int in the List, converting each Int to a String and returning a new List[String] with the converted values. A look at the type signature would already give you a lot of information about the transformations happening on a type level.

The type signature of this function would naturally be a bit more complex than the previous ones; instead of accepting one argument, we now have a function which accepts two arguments. With a type definition like:

(List[Int], Int ⇒ String) ⇒ List[String]

So what about a function returning a new function? Let’s define a function which takes two integers (min andmax) returning a function which takes a Int eventually returning a Boolean. The function returned will basically take a Int and calculates if the supplied number is in range of the initial two:

val isInRangeOf = 
(min: Int, max: Int) ⇒ (x: Int) ⇒ x > min && x < max

Which ends up with having the following type signature:

(Int, Int) ⇒ Int ⇒ Boolean

Let’s show how we can use our new function:

val newFunction = isInRangeOf(20,30)
newFunction: Int ⇒ Boolean = <function1>
newFunction(22)
res0: Boolean = true
isInRangeF(40,45)(50)
res1: Boolean = false

As you can see in the example, applying a tuple of two Int (min and max) returns a new function with a signature of Int maps toBoolean. We can assign this function to a new variable, or immediately use it by passing an argument to the return of the first function.

By applying functions to arguments, it’s possible to map values of types into other values of other types. Naturally, it’s also possible to map values into the same type, but with a different value:

val addTwo = (x: Int) ⇒ x + 2
addTwo: Int ⇒ Int = <function1>

Function currying

While you could say that the isInRangeOf is a function which maps two numbers into a function taking a single number. You could also state that the function is a function which takes both a tuple of two numbers and a single number to eventually map both into an eventual number.

Int ⇒ Int ⇒ Int

As a more simple example, looking at the above signature, we could say that the type signature either takes a Int to produce a Int ⇒ Int or just that two successive applications of a Int produce an Int.

val multiply = (a: Int) ⇒ (b: Int) ⇒ a * b
multiply:
Int => (Int => Int) = <function1>
multiply(3)(2)
res0: Int = 6
multiply(3)
res1: Int => Int = <function1>
res1(2)
res2: Int = 6

The idea of passing arguments not in a tupled form, but in a form of closures is often referred as currying.

Like shown in the above block, function currying enables you to use functions as prototypes of other functions. Without going into further detail about function currying, it can be a very powerful way to create reusable code.

Functors

Looking back at our mapToStringList function, we were applying the function to every item we had in our List. You can understand that since List can be treated as some kind of container for other types, mapping functions over the content of aList is something you want to do more often.

To tackle this, the List type in Scala implements a higher ordered function called map (semi pseudo):

class List[A] {
def map[B](f: A ⇒ B): List[B]
}

Without going into details on how the type system and how type inference in Scala works. You can use potential background into generics to assume that a definition like List[A] is a type List with a, so called, parameterized type A. Inserting a Int as a type parameter will basically result in a List[Int].
The same type parameter can be used in a function: map[B]. This generic behaviour enables us to define a single function which can be used on different types.
In case of a List[Int]. An application of a function of (x: Int) ⇒ x.toString to the map function of the list, will result in the following inferred map function:
def map(f: Int ⇒ String): List[String]

You can use this map function to create a new List, containing the mapped values:

val a: List[Int] = List(1, 2, 3, 4, 5, 6)
a.map(x ⇒ (x + 2) toString)
res0:
List[String] = List(3, 4, 5, 6, 7, 8)

Contexts

Not only the List type implements this map functionality, most iterable types like Set, Vector orMap implement the same kind of map functionality. However, several other shaped types also follow this kind of behaviour:

  • Option[A]: a type which lets you safely use potentially existing values;
  • Future[A]: a type which lets you use not yet available values (as in delayed values, eventually resolved by threads);
  • Try[A]: a type which lets you safely use potentially unsafe and exception throwing values.

We can state that this mapping behaviour is implemented by a special class of types. In this, the word class shouldn’t be interpreted as the class language construct. Interpret the word class as we do outside of programming languages; like a class of animals. The implementation of the map function and its behaviour is specified in the so called Functor type class.

trait Functor[F[_]] {
def map[B](f: A ⇒ B): F[B]
}

All Functors, types which implement the map functionality (and often other currently not important functions), apply the passed function to their own context. Initially, the idea of context or even body can be a bit vague. To get a feeling on what this context is, how it works and how to detect one in the future, we’ll go through the List, Option andFuture types and describe their context and what this map functionality does to their contexts.

List

When we look at a iterable type like List from a higher level, we can describe the context of a List type as a: context of zero to a infinite number of values.

When we use the map function to apply a passed function (like a Int ⇒ String) over the context of List, we apply the function to the zero or infinite number of values the List contains, creating a new List with the new values.

Option

The Option type in Scala makes it possible to use potentially available values. Instead of checking for null values in an if statement, the programmer can check with isDefined if the value is defined or not.

The Option type is implemented by two other types: None and Some[T], by using techniques like pattern matching, the Option type makes it possible to take actions depending on if there is a value available or not.

When looking at Option from the perspective of the Functor type class, we can define the context of Option as a: context with a potentially existing value.

Mapping a function over this context, makes it able to apply the function on the potentially existing value. This enables us to go from a Option[A] to Option[B]. Mapping the new value into a Some[B] when it exists and into a None when the value doesn't exist.

Future

The Future type, enables you to use eventually resolved values in a type-safe manner. This enables the developer to easily work with asynchronous results without the use of excessive callbacks.

If we are on the right track, this may feel repetitive. But we can define the context of Future as a: context with a eventually resolved value.

Mapping a function over this context, makes you able to apply the function to the eventually resolved value. Going from a Future[A] to a Future[B] only when and after the value is resolved.

Vegas baby!

So as we can see with the map function: what happens in context, stays in context. Mapping a function over a Option[T] applies the function to the value only within the context but will never change the outer Option type. Let’s go through some examples (in Scala) to show how these Options are used:

val email: Option[String] = request.headers.get("email")
val emailLength: Option[Int] = email.map(_.length)

As you see in the above example, the Option type doesn’t change. The functions only the maps the value into a new value. In a way, the context of the Option[String] also stays the same; we only change its inner shape and value into a new Int value.

We now know that all types implementing the functor type class should follow the same behaviour, so using the Future type:

val userFut: Future[User] = db.fetch("user@domain.com")
val emailFut: Future[String] = userFut.map(_.email)
val res: String = Await.result(emailFut, 1 second)

Should look more then comparable to the Option example. Once again, we change its internal shape and value by applying the function, but don’t change its context: we still wait on the same original value to resolve on which the function is applied.

So how does this knowledge about the Functor help the day-to-day programmer? With the ideas about purity and referential transparency in mind, we now know that a correct implementation of the Functor type-class and its accompanied map function will always show the same expected behaviour; never changing its outer type and always applying the function towards its inner context. When you see the map function and know how the context of the inner type behaves, you can also immediately derive how the map function itself will behave.

Flattening

But what if the applied function returns a new context? Let’s describe a situation where such a event might happen:

val userFut: Future[User] = db.user.fetch(“user@domain.com”)
val orgFut: Future[Future[Organisation]] = userFut.map(x ⇒ db.organisation.fetch(x.organisationId))

We first try to fetch a user from a database, returning a Future with the eventual User value in its context. To get the organisation object for the specific user, we map a function onto its context returning a Future on a Organisation. When we would wait for the first context to resolve, it would return a new context on which we would have to wait sequentially:

val fut: Future[Organisation] = Await.result(orgFut, 1 second)
val org: Organisation = Await.result(org, 1 second)

Contexts within contexts (within contexts) of the same shape do not make sense if you want to use its functionality sequentially (or imperatively). In a sense, we want to flatten the contexts together as a stack. Making it able to chain contexts sequentially and returning the last context and its value.

Monads

This “context flattening” behaviour is implemented by the Monad type class. A lot of types which implement the Functortype class, also implement the Monad class to use multiple contexts in sequence.

Let’s take a look how the Monad type class is implemented by the Future type:

class Future[A] {
def flatMap[B](f: A ⇒ Future[B]): Future[B]
}

Just like the map function was added by implementing the Functor type class, the Monad type class is implemented by adding the flatMap function. The type signature of the function immediately shows its possibilities. Instead of passing aA ⇒ B function, we pass a function of A ⇒ Future[B]: a function returning a new context.

trait Monad[F[_]] {
def flatMap[B](f: A ⇒ F[B]): F[B]
}

Let’s use the example of the User and the Organisation to show how we can fix the issue using the Monad functionality:

val userFut: Future[User] = db.user.fetch("user@domain.com")
val orgFut: Future[Organisation] =
userFut.flatMap(x ⇒ db.organisation.fetch(x.organisationId))
val org: Organisation = Await.result(orgFut, 1 second)

By flattening the context of a eventual user with a context of a eventual organisation, we gain a combined (sequentially resolved) context on a eventual organisation. This behaviour is again, the same on all other types which implement theMonad type class:

val email: Option[String] = request.headers.get("email")val domain: Option[String] =
email.flatMap(_.split("@")
.tail.headOption)
val domainLength: Option[Int] = domain.map(_.length)

Using multiple Monads sequentially can result in difficult to read code:

db.user.fetch(“user@domain.com”).flatMap { 
u ⇒ db.organisation.fetch(u.organizationId).flatMap { o ⇒
db.city.fetch(o.cityId) flatMap { c =>
db.country.fetch(c.countryId)
}
}
}

Luckily, Scala enables us to use some synthetic sugar which not only makes Monads a lot easier to use, but also helps to make it’s sequential behaviour more apparent:

for {
user <- db.user.fetch("user@domain.com")
org <- db.organisation.fetch(user.organizationId)
city <- db.city.fetch(org.cityId)
country <- db.country.fetch(city.countryId)
} yield country

Practice makes perfect

This introduction should give you some understanding on functional programming, Functors and Monads. For the larger part of your day-to-day programming you can forget about these often shunned words, but the potential intuition you have gained towards the map and flatMap functions will scale over a lot of programming languages and concepts.

Real understanding and mastering come with practice. Understanding the fundamentals help to identify the concepts when you encounter them, but the real difficulty lies in how to construct the concepts yourself. There are a lot of libraries adding more strict FP types and functionality to the Scala language. If you want to know more, reading documentation and code from Cats (https://github.com/typelevel/cats/) project is a good start.