Functor

The first evidence that these concepts are not so complex is given by the functor. Do you remember the Mapper type class seen in the previous section? That's a Functor. We called it Mapper just to arrive at this demystifying moment. So, you can now rewrite the Mapper type class and companion object as follows:

trait Functor[F[_]] {
  def map[A, B](fa: F[A])(f: A => B): F[B
}

object Functor {
  def apply[F[_]: Functor]: Functor[F] = implicitly[Functor[F]

  def map[A, B, F[_]: Functor](fa: F[A])(f: A => B): F[B] = Functor[F].map(fa)(f)

  implicit val optionFunctor = new Functor[Option] {
    override def map[A, B](fa: Option[A])(f: A => B): Option[B] = fa.map(f)
  }

  implicit val listFunctor = new Functor[List] {
    override def map[A, B](fa: List[A])(f: A => B): List[B] = fa.map(f)
  }
}

Using a functor you can apply a given function to a value that is inside a context. Examples of contexts are: Option, List, Try, Future, and so on.

For example, the Option type represents the context of an optional value that eschews null to handle the no value case. The List context is that of representing no value or, at least, one value. The Try type represents the context of a possible failure.

Future, on the other hand, represents the context where a value may be available in the future. For instance, suppose you have Some(42) and you want to:

1. Extract the value 42 outside of the context (Some)
2. Apply a function to it
3. Put the result inside the context again

Well, that's basically what a functor is for.

Also, you may have heard of the lift word associated with the functor concept. A functor lifts a simple function that goes from A to B to one that goes from F[A] to F[B], where F is the functor, e.g. List or Option. Figure 10.1 illustrates lift, which is just the effect of map.

Actually, you could have written the map method of Functor, equivalently, as follows:

trait Functor[F[_]] {
  def map[A, B](f: A => B): F[A] => F[B
}
object Functor {
  def apply[F[_]: Functor]: Functor[F] = implicitly[Functor[F]

  def map[A, B, F[_] : Functor](f: A => B): F[A] => F[B] = fa =>
    Functor[F].map(f)(fa)

  // …
}

Can you see now why they say that, through a functor, you can lift a function of type A => B to one of type F[A] => F[B]? Again, lift, another buzzword demystified. The latter is the signature used in Haskell, by the way. The problem with this signature in Scala is that its type inference is not as good as Haskell's. Easy up to now, isn't it? This is not the full story, though.

In order for something to be a functor, it should satisfy a couple of laws. In formulating and elaborating the laws, let's use the latter map function signature, because it makes the reasoning easier to follow. However, in real life, you'd stick to the previous signature because of the type inference problem aforementioned. Let's see these laws then.

Given fa: F[A] and the identity function defined as follows:

def identity[A](a: A): A = a

The following laws must hold (in pseudo-code):

Law I:  map(identity)(fa) = fa
Law II: map(f compose g)(fa) = map(f)(map(g)(fa))

The first law states that if you map the identity function over a functor, the returned functor should be the same as the original one. The second law states that if you have two functions, f and g, the result of mapping their composition over fa must be the same as mapping g to fa obtaining, say, fb and then mapping f to fb.

If you had to read Law I as a question, it would be: “What's the function that applied to fa gives back fa unmodified?” If you thought of the identity function you guessed it. So, this means that a potential functor satisfies the first law if and only if:

map(identity) = identity

You can easily verify that this is true both for Option and List. For Option it means that, for example:

Some(42).map(identity) == Some(42)
None.map(identity) == None

This is the same reasoning for List. So they respect the first law. Now the second. For Option it means:

Some(42).map(f compose g) == Some(42).map(g).map(f)
None.map(f compose g) == None.map(g).map(f)

The second law is also respected—by List too. You can say there exists a functor instance for both Option and List.

Note that the compiler cannot enforce these laws, so you have to test them out yourself to ensure the functorness. However, if you use functors written by others, you don't even need to worry about these laws, since they should have done it on their side. For example, popular libraries such as scalaz (https://github.com/scalaz/scalaz) and cats (https://github.com/non/cats) make sure that every functor instance satisfies the aforementioned laws.

Now that we have demystified the functor concept let's proceed with the applicative functor.

Applicative Functor

Before introducing the Applicative Functor (simply Applicative from now on) we want to expose the problem it resolves.

Using a functor you can apply a given function to a value that is inside a context: Option, List, Try, Future, and so on. Now, what if the function you want to apply is within a context as well? An example will make this clear.

Suppose you want to write a very trivial method, based on string interpretation, that returns a function to be applied to an Int value. For instance, something like the following:

def interpret(str: String): Option[Int => Int] = str.toLowerCase match {
  case "incr" => Some(_ + 1)
  case "decr" => Some(_ - 1)
  case "square" => Some(x => x * x)
  case "halve" => Some(x => x / 2)
  case _ => None
}

The interpret method takes a String and returns an Option[Int => Int]. If the command is not recognized it returns None. Pretty fair.

It would be nice being able to apply the function returned by interpret, which is inside the Option, to a value wrapped in an Option too. Of course, as a result, we still want an Option. Stated differently, given:

val func: Option[Int => Int] = interpret("incr")

val v: Option[Int] = Some(42)

We want to apply the wrapped function represented by func to the wrapped value represented by v. Applicative solves this type of problem. Here's the definition of the Applicative type class:

trait Applicative[F[_]] extends Functor[F] {
  def pure[A](a: A): F[A

  def ap[A, B](fa: F[A])(fab: F[A => B]): F[B

  override def map[A, B](fa: F[A])(fab: A => B): F[B] = ap(fa)(pure(fab))
} 

The methods exposed are pure and ap. The first is needed to wrap a value into a context. The ap method, instead, is exactly what we needed to combine func and v from the previous example.

Moreover, Applicative extends Functor. Indeed, as you can see from the previous code, by providing pure and ap you can derive for free an implementation of the map method, required by the functor.

Now, let's provide the applicative instances for Option and List:

object Applicative {
  def apply[F[_]: Applicative]: Applicative[F] = implicitly[Applicative[F]

  def pure[A, F[_]: Applicative](a: A): F[A] = Applicative[F].pure(a)

  def ap[A, B, F[_]: Applicative](fa: F[A])(fab: F[A => B]): F[B] =
    Applicative[F].ap(fa)(fab)

  implicit val optionApplicative = new Applicative[Option] {
    override def pure[A](a: A): Option[A] = Option(a)

    override def ap[A, B](fa: Option[A])(fab: Option[A => B]): Option[B] = for {
      a <- fa
      f <- fab
    } yield f(a)
  }

  implicit val listApplicative = new Applicative[List] {
    override def pure[A](a: A): List[A] = List(a)

    override def ap[A, B](fa: List[A])(fab: List[A => B]): List[B] = for {
      a <- fa
      f <- fab
    } yield f(a)
  }
}

Remember to always follow the types.

Now you can finally combine func and v thanks to Applicative:

val func: Option[Int => Int] = interpret("incr")

val v: Option[Int] = Some(42)

val result: Option[Int] = ap(v)(func)

Applicative, like Functor and all other concepts coming from Category Theory, come with some laws that must be respected. For a matter of space, we won't cover the applicative laws here. For the moment, you don't need to worry about them either. At this stage of things, you'll use applicatives exposed by, say, scalaz or cats, as a user. When and if you need to write your own applicative instances, you can then dig deeper into the applicative laws.

Monad

The moment to talk about monads arrived. By now, however, you should already know that it is a type class with some laws to respect.

Prof. Eugenio Moggi, an Italian professor of computer science, was the first to describe the general use of monads to structure programs.

Monads can be seen as beefed up applicatives, much in the way applicatives can be seen as beefed up functors. Indeed, here is the definition of the Monad type class:

trait Monad[M[_]] extends Applicative[M] {
  def unit[A](a: A): M[A

  def flatMap[A, B](ma: M[A])(f: A => M[B]): M[B

  override def pure[A](a: A): M[A] = unit(a)

  override def ap[A, B](fa: M[A])(fab: M[A => B]): M[B] = flatMap(fab)(map(fa))
}

The primitives required by the Monad type class are unit and flatMap.

Once you have an implementation for unit and flatMap, you get for free, the implementation of pure and ap of the Applicative type class. Here is the Monad companion object that contains the implementation of Monad for Option and List:

object Monad {
  def apply[M[_] : Monad]: Monad[M] = implicitly[Monad[M]

  def flatMap[M[_] : Monad, A, B](ma: M[A])(f: A => M[B]): M[B] =
    Monad[M].flatMap(ma)(f)

  implicit val optionMonad = new Monad[Option] {
    override def unit[A](a: A): Option[A] = Option(a)

    override def flatMap[A, B](ma: Option[A])(f: A => Option[B]): Option[B] =
      ma.flatMap(f)
  }

  implicit val listMonad = new Monad[List] {
    override def unit[A](a: A): List[A] = List(a)

    override def flatMap[A, B](ma: List[A])(f: A => List[B]): List[B] =
       ma.flatMap(f)
  }
}

Both Option and List expose the flatMap method. Now let's have a look at an example. Suppose you have the following function and value:

val sqrt: Double => Option[Double] = { value =>
  val result = math.sqrt(value)

  if (result.toInt.toDouble == result) Some(result) else None
}

val perfectSquare: Option[Double] = Some(49)

The sqrt function takes a Double and, if it's a perfect square, returns the result of applying the square root to the number wrapped in a Some; otherwise it just returns None. You want to apply the sqrt function to the perfectSquare value.

Follow the types. You have an Option[Double] and a function Double => Option[Double]. The flatMap method has the following signature:

def flatMap[M[_] : Monad, A, B](ma: M[A])(f: A => M[B]): M[B]

Specifically, if you replace A and B with Double and M with Option you'll soon realize you have everything you need. Indeed:

val res: Option[Double] = flatMap(perfectSquare)(sqrt) // Some(7.0)

Again, monads have some laws that must be respected too, but we won't cover them here for space's sake. Moreover, you don't need to know them to exploit the already existent monad instances provided by scalaz and cats.

The concepts of functor, applicative, monad and many others, useful in the functional programming world, are taken very seriously by pretty famous libraries such as scalaz and cats. The latter is younger than scalaz, but better organized and documented. We recommend that you may start with cats and then, once you have mastered some concepts, take a look at the more mature scalaz library.

Semigroup

Another concept you may have heard of is the semigroup. It comes from mathematics.

A semigroup is an algebraic structure consisting of a set together with an associative binary operation. So, a semigroup involves a set S and a binary operation.

The following properties must hold for a semigroup:

• Closure: Given two elements of S and applying the binary operation to them, the result must also be in S.
• Associativity: When combining more than two elements of the set, it doesn't matter which pairwise combination you do first.

An example will make it clearer. Consider the set of integers along with the + binary operation. Does it form a semigroup? Yes. The closure law is satisfied since, by summing two integers, you get back an integer again. Also the associativity holds. Indeed, for example:

(4 + 10) + 2 = 4 + (10 + 2)

In order to see how these mathematical structures can be of help in your day-by-day coding sessions, let's introduce the monoid, which is just a beefed up semigroup.

Monoid

A semigroup with the identity element is called a monoid. Here's the formal identity element definition:

Identity element: There exists an element e in S such that for every element a in S, e • a = a • e = a.

Again, does the set of integers along with the + operation form a monoid? You've already seen that it forms a semigroup. If you can find the identity element then it's also a monoid. For the plus operation, the identity element, or the neutral element, is the zero. Indeed:

x + 0 = 0 + x = x, for all x being an integer.

Note that the set of integers with the * operation forms a monoid too. In this case the neutral element is the unit. Indeed:

x * 1 = 1 * x = x, for all x being an integer

OK, enough math; let's get back to coding and see how these mathematical concepts can make your code cleaner and more elegant.

First, let's capture the semigroup and monoid concepts:

trait Semigroup[A] {
  def append(a1: A, a2: A): A
}
trait Monoid[A] extends Semigroup[A] {
  def zero: A
}

Now, suppose that you want to abstract the concept of summation. That is, given a List[A], you want to be able to sum all its elements. Scala already exposes the sum method on List, but, unfortunately, it works only with numbers. So the following attempts will work:

 scala> List(1, 2, 3).sum
res0: Int = 6

scala> List(3.14, 42.6, 3).sum
res1: Double = 48.74

However, if you try to use sum on a List[String] it won't work because there's no instance of the Numeric type class for String:

scala> List("hello", ", ", "world") .sum
<console>:8: error: could not find implicit value for parameter
num: Numeric[String
              List("hello", ", ", "world") .sum
                                            ^

Can you write a more generic sum method that will also work for strings? Yes, thanks to the monoid structure. Here is the method definition:

def sum[A](elements: List[A])(implicit M: Monoid[A]): A =
  elements.foldLeft(M.zero)(M.append)

Look how beautiful and elegant that is! As you already know, foldLeft expects an initial element of type A and a binary function of type (A, A) => A. That's what we are providing through the monoid structure.

In order to make it work for integers you just need to provide an implicit instance of Monoid[Int] in scope. For String, you implement Monoid[String] and make sure it's in scope, implicitly. Let's do it:

object Monoid {
  def apply[A: Monoid]: Monoid[A] = implicitly[Monoid[A]

  implicit val intMonoid = new Monoid[Int] {
    override def zero: Int = 0

    override def append(a1: Int, a2: Int): Int = a1 + a2
  }

  implicit val stringMonoid = new Monoid[String] {
    override def zero: String = ""

    override def append(a1: String, a2: String): String = a1 + a2
  }
}

As you can see, the implementation isn't fancy. The identity element for the String type is, naturally, the empty string.

Here's the sum method in action:

val intResult: Int = sum(List(1, 2, 3))
val stringResult: String = sum(List("hello", ", ", "world"))

println(intResult)
println(stringResult)

The output is:

6
hello, world

It seems to work like a charm. Now, suppose you want your sum function to work with Option types too. Do you need to change anything from the previous code? No, you don't. You just need to provide an implementation of Monoid[Option[A]]:

implicit def optionMonoid[A: Semigroup]: Monoid[Option[A]] =
new Monoid[Option[A]] {
  def zero: Option[A] = None

  def append(f1: Option[A], f2: Option[A]): Option[A] = (f1, f2) match {
    case (Some(a1), Some(a2)) => Some(Semigroup[A].append(a1, a2))
    case (Some(a1), None) => f1
    case (None, Some(a2)) => f2
    case (None, None) => None
  }
}

What follows is an example of its use:

val optionResult: Option[String] =
  sum(List(Some("hello"), Some(", "), None, Some("world")))

println(optionResult)

The output is:

Some(hello, world)

Now some words about one interesting part of the implementation. Notice that we require an implementation of Semigroup for A so that you can use it to append the two values of type A when both values are of type Some.

You might wonder why we require it to be a Semigroup and not a Monoid. The reason is that you only need the append method, and it's a good development practice to use the least powerful abstraction that will get the job done. This makes your code more reusable. Furthermore, there could be plausible implementations of Semigroup for some types, but not valid Monoid implementations since the zero might not make any sense in some contexts. Similarly, if your method can get away with an applicative, don't require a monad as evidence.