Chapter 2. Category Theory and Patterns

Two Kinds of Patterns

A software design pattern is a reusable solution to a commonly occurring problem within a given context in software design.1 Software patterns mean that we do not have to start from scratch, everytime we write code, and they were made well known in the Gang of Four software patterns book.2 If you ask functional programmers about patterns, they may say that patterns are not particulary relevant in functional programming. When they say this, they probably have in mind the traditional, gang of four patterns mentioned here. But there is another set of structures, commonly used by functional programmers that they simply may not think of as patterns. These structures come from a branch of mathematics called Category theory. I choose to call these functional patterns and will investigate them next.

Category Theory Based Patterns

I like to think of these patterns as hard-core functional programming patterns. By this I mean to suggest that hard-core functional programmers use these idioms liberally in their code. In a sense, along with immutability, referential transparency and higher order functions, these patterns form the main content of what it means for code to be functional. What are some examples of category theory based patterns? Things like Functor, Monoid and Monad are some examples. Now where do these patterns come from? They come from an abstract but very useful branch of mathematics called category theory. Now we could just introduce these patterns as they are without any reference to category theory. But I think you may appreciate and find useful the origin of these patterns. And who knows, you might just find you like category theory as a subject in its own right. So what is Category Theory and how did it come about?

In the 1940s, Saunders Mac Lane and Samuel Eilenberg were discussing a lecture one of them gave. They both came to the same conclusion, together, that the subjects each was working on, one in algebra and one in topology, were actually instances of the same phenomenon. After fleshing out their ideas, they realized they had discovered a new subject. Thus was born category theory!

They cowrote a book called ’Categories for the Working Mathematician’ which became a big source for future development in the subject. Then in 1990, the purely functional programming language Haskell was created. Many ideas were taken from category theory in creating Haskell. Some of these concepts have found their way into other functional and partly functional programming languages, such as Scala, F# and Java. Another way functional capabilities were incorporated was through software libraries.

Now let us look at the definition of a category.

Objects and Morphisms

The basic definition of category theory involves two concepts, objects3 and morphisms. Objects can be anything: sets, numbers, matrices, just to name a few. A category also needs morphisms. A morphism can only be defined in the context of two objects from the category. Let us suppose that A and B are objects from a category C. Then a morphism is an arrow from A to B. We write it like this:

AB

But what does an arrow mean exactly? Well, it connects object A to object B. Where the arrow starts and where the arrow ends is what’s most important, and this relationship is the morphism. People tend to think of this arrow as a function, in part because the above diagram makes it look like a function, and in most cases it is a function. But there are categories where the morphisms are not functions.4 For our purposes, we can think of a morphism between A and B as a function from A to B, possibly with some conditions on the functions. Now if f is a morphism from A to B, then A is called the domain of f and B is called the codomain of f. This corresponds to the language used for functions.5

The category Set

Let us start with the category of all sets. That is, the objects are all sets. What are the morphisms? Consider two objects A and B from the category. What are the morphisms from A to B? Simply all functions from A to B. In this case, there are no conditions on the functions. Every function from A to B is a morphism. So the category Set is the category whose objects are sets and morphisms are functions from A to B, for all pairs of sets, A and B. Now just to be clear, you may have heard of the term range, of a function. Why does the definition of morphism specify a codomain and not a range? For functions, range is the set of all things in B that are actually mapped to by some element of A. The codomain contains the range but doesn’t necessarily have to equal it.6 The following example shows two objects in the category Set and two morphisms with domain A and codomain B.

Let A = {1,2,3,4} and B = {'a','b','c','d','e'}.

These are two perfectly good sets so they are objects in the category Set. Let us now define two morphisms from A to B.

Morphism f from A to B:

For all x in A, f(x) = ‘a’. This could be called a constant morphism.

Morphism g from A to B:

g(1) = ‘a’

g(2) = ‘b’

g(3) = ‘c’

g(4) = ‘d’

The above two functions from A to B are two morphisms in the category Set. Notice that there is no element of A that is mapped to the element ‘e’ in B. This is fine. B is the codomain and not the range. Note that this is a very large category. It contains all sets and all functions from A to B.

Before we look at some more examples, there are a couple of things about morphisms we have to say. First, morphisms compose. What does this mean?

Suppose f:AB is a morphism and g:BC is a morphism.

Then there must exist a morphism h satisfying:

h(x) = g(f(x))

We denote h by the expression gf and we say g composed with f. If the composition does not exist, then what we were considering was not a category. In every category, morphisms must compose.

There is one other property morphisms must have in order to have a category: For each object A in the category, there must exist a morphism idA:AA with the property that for any morphism f: A → B and morphism g: A → B in the category, we have:

fidA=f and idBg=g

This may look mysterious but it is just the category theory way of saying that idA is the identity function on A. Category theorists tend to think not in terms of points, but rather in terms of composition of functions. The above expression is how you express the identity function in category theory in terms of composition. Instead of saying identity morphism takes every point in the object to itself (because we don’t think about the points), you say that when you compose the identity morphism with another morphism, you get the original morphism back. This is actually a deep point. Much of category theory is about expressing mathematical concepts through the notion of composition.

Let’s look at some more examples. We will need something called a semigroup, which you may have come across in a course on abstract algebra. It is really quite simple. A semigroup has two main parts, a set of elements, (could be any non-empty set) and a binary operation on the set. A binary operation, like multiplication for whole numbers, or union for two sets, takes two things and returns a third thing. There is one condition that must hold. The binary operation must be associative. We will denote the binary operation by *.

* is associative means that for all x,y and z, we have:
x*(y*z)=(x*y)*z

So a semigroup is a non-empty set with an associative binary operation on it.

Example 1: Let the set be all whole numbers and let the operation be multiplication.

First notice that when we multiply two numbers together, we get another whole number. This is necessary for a semigroup. When you combine two elements in a semigroup with the binary operation, you’d better get something that is again in the semigroup.7 We won’t prove it here but multiplication on whole numbers is associative. We all learned that in school. So all whole numbers plus multiplication form a semigroup.

Example 2: Let the set be all three by three matrices of real numbers. The operation will be multiplication of matrices. One can show this is associative. It just so happens that matrix multiplication is not commutative. A*B is not necessarily equal to B*A. But commutativity is not a requirement for something to be a semigroup; associativity is necessary.

I’ve shown you two examples of semigroups, but suppose we want to study all semigroups. In this case, we could study the category of semigroups. This category is called Semigroup and the objects are (obviously) all semigroups. What are the morphisms? This is a bit more involved. We might want to say that the morphisms are functions from one semigroup to another semigroup, but this would not be sufficient. Category theory is all about structure and finding similar structures in seemingly different objects, so what structure does a semigroup have? The structure is determined by the multiplication operation.

Note

(In a semigroup, we often call the binary operation multiplication, even if it is not necessarily the usual multiplication of numbers).

So the notion of morphism in this case, has to somehow capture the multiplicative structure of the semigroup. In the following example, I’ll show you how this works.

Let S1 and S2 be two objects in the category Semigroup.

A function h from S1 to S2 is a morphism if for all x, y in S1, we have:

h(x*y)=h(x)*h(y)

What this essentially is saying is that the two semigroups have similar multiplicative structure. It says if you want to know where h maps x*y, just look at where h maps x and where h maps y and then multiply them together in S2. You can think of the morphism as renaming the object it maps. In this case, x in S1 corresponds to h(x) in S2. And y in S1 corresponds to h(y) in S2. h being a morphism means that x*y corresponds to h(x)*h(y). It is like an alternate universe in which every entity in the original universe has a corresponding entity in the alternate universe.

We can talk about the semigroup comprised of whole numbers with multiplication, the semigroup of 3x3 matrices of real numbers with matrix multiplication. But we can also study the category of ALL semigroups.

What does all of this have to do with functional programming?

The category Scal

When it comes down to it, even though much of functional programming theory comes to us from category theory, often through the programming language Haskell, we are really only interested in one particular category. Let us describe this category. First, select a programming language. In theory, it can be any programming language with types. We will choose Scala, because it is particularly suited to functional constructions and because much of Scala code is sufficiently clear that it al most resembles pseudocode. I call this category Scal8.

The objects in the category Scal are the set of all types of Scala. Not only simple types like String, Int, Boolean but also List[String], Map[Int,Double] and any type we can build up from basic ones. We could also include user defined types like User, Account etc. but we will stick to built in types and types that can be built up from them. Let me also say here that in theory, we could look at the category for any programming language. We are working with the category Scal but we could, if we wanted to, work with a category based on, say, Java. In this case, the objects would be types in the Java language and morphisms from type A to type B would be functions from objects of type A to objects of type B.

Morphisms

Now if we take two types, say String and Int, how should we define a morphism between them? Simply define a morphism from String to Int to be any function which takes a String and returns an Int. So an example of a morphism between these two types would be the length function. It takes a string, say “abc” and returns an Int, in this case, 3. Now let’s give an example of the composition of two morphisms. We know that in any category, if there is a morphism f:AB and a morphism g:BC, then there must be a morphism h:AC with h=gf. Let’s take two morphisms that line up the right way and see what their composition is.

f:StringInt is defined by f(s)=s.length

g:IntInt is defined by g(n)=n*n.

So f is the length function and g is the square function. What does their composition look like?

gf(s)=(s.length)(s.length)

So we have our category Scal where the objects are types and for two types A and B, the morphisms are functions that take an A and return a B.

Note

Once you have selected a programming language, Scala, in this case, all the category theory that is applied to functional programming deals with this one category Scal, where the objects are Scala’s types and the morphisms from A to B are functions that take an object of type A and return an object of type B.

Functors

Functor is a funny word. It sounds like function and it is, indeed, a function. But it is a very special kind of function. Before we define it, let’s look at some examples in Scala that correspond to Functors. Some functors in Scala are List, Option and Future.9 These examples have two things in common. First, they are generic types, meaning that they take other types as parameters. You can’t just have a List in Scala. You can have List[String], List[Int] or List[User], for example. List[String] is not a functor. It is a type. But List by itself, is a functor. Same for the other two examples. The second thing they have in common is that they all have a map function. Let’s see an example:

Scala

val lst = List(1,2,3,4) 1
lst.map(n => n*n)       2
//returns List(1,4,9,16)
1

Create a list of four numbers.

2

List is a functor so it has a map function We will see where map comes from in Category theory later in the chapter.

Now let’s define functor. I first need to specify two categories C1 and C2.

Then a functor F from C1 to C2 is a function from the first category to the second category which satisfies the following properties.

  1. F takes objects in C1 to objects in C2. (Just like List takes String to List[String])

  2. F takes morphisms in C1 to morphisms in C2. (What List does to a morphism is trickier. It involves the map function and we will treat this below.)

  3. F(fg)=F(f)F(g) whenever the morphism domains and codomains of f and g line up.

This condition basically means that the two categories C1 and C2 have similar structure with respect to morphisms. The idea to keep in mind when considering functors is that they measure how similar two categories are.

Now we said earlier that the category we will be interested in is Scal.

Note

Don’t we need two categories to define a functor? Actually no. A functor can go from a category to itself. Such a functor is called an endofunctor. So all the functors we will be considering, in the category Scal, will be endofunctors.

Example 1 The List type constructor in Scala. (Notice I didn’t say type). What’s a type constructor? List is not a type in its own right. It needs to take a type parameter before it becomes a bonafide type. We can have a List of Strings, a list of Ints etc. Once we pick a type parameter, say String, then we get the type List[String]. So List by itself is called a type constructor. What are some other examples like this in Scala? Option and Future to name a few.

In the category Scal, the above are examples of functors. List, Option and Future. They are functors from the category Scal to itself. Remember, we called such a functor an endofunctor. So List, Option and Future are examples of endofunctors, and all endofunctors are functors.

What does a functor do to a morphism?

First of all, List takes objects of Scal to objects of Scal. For example, List takes the object String to the object List[String]. Secondly, List also takes morphisms to morphisms. How does this work? Let us consider the two morphisms length and square. length is a morphism from String to Int and square is a morphism from Int to Int. So their composition squarelength is a morphism from String to Int. It takes a string and spits out the square of the string’s length. (a bit contrived, I know, but it illustrates composition of morphisms). So we understand how List takes String to List[String] but how does List act on the morphisms? What is List(length)? This looks odd. We are not accustomed to taking the list of a function.10 What can this mean? Since length goes from String to Int, list(length) must go from List[String] to List[Int]. Can you think of any function, possibly with another name, that maps List[String] to List[Int]? If you said map, you are right. In Scala, we would write this:

Scala

List("abc", "defgh").map(_.length) //== List(3,5)

This can be confusing so lets be very clear. In Scala, certain types have a map function defined. (We will see that these are precisely the functors). So given a functor, there is this map function in the background. And when we want to know what the functor does to a morphism, we need to use the map function in a certain way. We expressed this above with length but let us see what this looks like in the general case.

Consider the morphism f:AB, where A and B are two Scala types.
(i.e. two objects in the category Scal)

And let F:ScalScal be a functor from the category Scal to itself.

We write what F does to an object A as F[A] (think List[A] or Future[A] etc)

And to the morphism f, how do we write what F does?

If fa is an element of F[A], and f:AB is a morphism

we write fa.map(f). This function that takes fa to fa.map(f) is F(f).

In Scala, we don’t think of this function as, List(length),but rather as the map function. There are actually many map functions, one for each functor. In Scala, we think of this as just one map function, which can be applied to any container like data structure. But in Category Theory, the map function is what you get when you apply a functor to a morphism.

So this leads us to another, and more common way, of looking at functors. A functor is simply an interface (or trait in Scala) that implements the map method. We could even have called functor Mappable. And as we mentioned above, on a higher level of abstraction, a functor is a way of measuring how similar two categories are. Or in the case of endofunctors on the category Scal, a functor relates the category Scal to a part of Scal.

I have now explained some of the major players in category theory: the category, objects in the category, morphisms and functors. The reason I chose Scal as the category to investigate is that functional constructions and idioms are more natural in Scala than some of the other popular languages.11 In addition, the constructions in Scala are so natural, they often almost look like pseudocode, which makes it easier to give examples to a multilingual audience.

As we have seen, there are two ways of looking at a functor. We can represent functor as a trait (or interface) that implements the map method or we can think of it the way we think of it in category theory. From this perspective, a functor is a function from the types of Scala to the types of Scala and it is also a function from morphisms in the category Scal to other morphisms in Scal. In particular, if A and B are two scala types, and f is a morphism from A to B, then F(f) is a morphism from F[A] to F[B]. We could think of F as providing a context for two types and a morphism between them. We start off working in A and in B and end up working in F[A] and F[B]. So we have contextualized A and B. If I want to know what represents the morphism f in the context F, we look at the morphism F(f) from F[A] to F[B]. What is this morphism? Well if fa is an element of F[A], then

F(f) takes fa to fa.map(f).

Remember, that every Functor has a map method associated with it, so we can always carry out the above expression. Let me give an example of the above. I can use the functor List. In this example, A = Int and B = Int. F = List and let the morphism
square :AB be the square function.

Then F[A] = List[Int] and F[B] = List[Int] too.
What is F(square). That is to say, what is List(square)? Remember, for this we need the map function that comes along with List (as it does with every functor). So we have:

F(square)(fa)=fa.map(f) or List(square)(fa)=fa.map(square).

This gives us:

List(square)(List(1,2,3,4))=List(1,2,3,4).map(square)=List(1,4,9,16)

Now we said that there are three properties a functor from category C to category D must satisfy.

1) A functor F takes objects in C to objects in D. In the case of the category Scal, this means F takes Scala types to Scala types.

2) F takes morphisms in C to morphisms in D.

3) A composition property, seen below:

F(fg)=F(f)F(g) where f and g are morphisms.

Let us check this property for the functor List and two morphisms length and square.12 So here length is a morphism from String to Int and square is a morphism from Int to Int.

Plugging in the values, I have to show:

List(squarelength)=List(square)List(length)

Now the expression on the left takes an object of type List[String] to an object of type List[Int] For example:

List(squarelength)(List(hello,universe))=

List(hello,universe).map(squarelength)=

List((squarelength)(hello),(squarelength)(universe))=

List(square(5),square(8))=List(25,64)

Now lets evaluate List(square)List(length).

(List(square)oList(length))(List(hello,universe))=

List(square)(List(length)(List(hello,universe)))=

List(square)(List(hello,universe).map(length)=

List(square)(List(5,8)=List(5,8).map(square)=List(25,64)

So the two sides are equal. What we have shown, in this particular case, is in fact, always true. For any functor F and two morphisms f and g, we always have:

F(fg)=F(f)F(g)

So for example, this will hold for other functors such as Option and Future. Once we know something is a functor, we know we can compose morphisms in this way. Why do we care?

The Patterns

The pattern Functor

Now that we have some idea of what a functor is, let us see how this pattern can be useful. Functors are useful for two reasons:

1)They always have a map function.

2)They can always be composed.

In the following example, I will show you how composing two functors can be useful.

Suppose we have a list of options, say:

Scala

val listOfOptions = List(Some(8), None, Some(2))

If you are unfamiliar with Some and None, see chapter two. Suppose we want to add 1 to 8 and 2. Most languages don’t provide functor constructions out of the box. Even Scala, which is fairly functional, doesn’t have this capability. But there is a library called Cats13, which provides category theory constructs, as first class objects, as it were. First, let’s look at the trait Functor, which comes with Cats.

Scala

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

We can see the map function, which every functor has. But what is F[_]?

F[_] is Scala’s way of expressing a type constructor, So the F, here, is what we are thinking of as the functor. Now remember what we are trying to show. We want to illustrate how composition of functors, which you always have, is useful. So back to our example of listOfOptions.

The definition of the trait Functor in the scala library Cats, is much simplified for our example. One method it comes with is compose. So in order to add one to the numbers in the options, we can do the following.

Scala

Functor[List].compose[Option].map(listOption)(_ + 1)

We have a list of options of ints and we want to map over the Ints. So the above expression lets us compose List and Option to get a new functor, and then use that new functor’s map method to map over the ints with the anonymous function _ + 1, which is just Scala’s way of writing an anonymous function that adds one. We started with:

val listOfOptions = List(Some(8), None, Some(2))

and ended up with:

val listOfOptions = List(Some(9), None, Some(3))

Notice that alot of meaning is packed into the above expression.

This is a good example of the power of composition of functors for functional programming.

Monoids

As I mentioned earlier in the chapter, a semigroup is a set with an associative operation on it. If a semigroup has an identify element, which means an element e, in the semigroup, with the property that: e*x=x*e=x for all elements x the semigroup, the semigroup is called a monoid.

In the following examples, I’ll show you some examples of monoids.

Example 1

Let M be the set of all non-negative whole numbers. Along with the operation addition, this is a semigroup. But notice that 0 is in the set M. We know that if we add 0 to any non-negative whole number, on the left or right, you get the original whole number back.

Note

We say left side or right side because not all semigroups are commutative. Its not always true, in a semigroup, that a*b=b*a.

In the case of non-negative whole numbers, addition is commutative. So saying left side and right side in the definition is unnecessary. So this is a monoid. We can write it like this (N, + , 0).

Example 2

Let M be the set of all 2x2 integer matrices with matrix multiplication. With the identity matrix, the one with ones on the diagonal and zeros off the diagonal, this is a monoid. Note that matrix multiplilcation is not commutative in general but if you multiply the identity matrix on the left or right of a given matrix, you get that matrix back again.

Now how are monoids useful in functional programming?

Well let us start with a simple example. We want a function that adds up a bunch of numbers. Let’s write this code in Java in a common, imperative style. We might do something obvious like:

Java

int sum(List<Integer> lst) {
        int result = 0;
        for (int i=0; i<lst.size(); i++) {
            result += lst.get(i);
        }
        return result;
    }

This code computes the sum of a list of integers. Let’s analyze it from a functional perspective. First, notice how it mutates state. The value of result continually changes throughout the program. So does the value of i. Let us try to write a functional version of this function that does not mutate state and also that uses an abstraction like monoid to express the sum with a higher level of abstraction. There is a function in functional programming called foldLeft (There is also a foldRight. You will see this function with various names depending on the programming languages. For example, foldLeft, foldl, fold, foldRight, foldr and fold). FoldLeft essentially comes out of the concept of a monoid.

Consider the following monoid: the set of integers with addition as the operation and 0 as the identity element. In any monoid we can create the foldLeft function. (or foldRight, but I won’t keep repeating this). We combine the identity with the first element of the monoid. Then we take the result of that and combine it on the left (respectively right) with the next element in the monoid. We do this until there are no more elements. We can describe this as follows: We are given a binary operation, that is, one that combines two elements. And fold applies the operation pairwise to get the combination of all the elements. Of course, in a commutative monoid, foldLeft is equal to foldRight. In Java, there is a similar function called reduce. Let’s see an example.

Java

Integer sumAll(List<Integer>lst) {
    return lst.stream().reduce(0, Integer::sum);
}

In Scala, we have:

Scala

def sumAll(Lst: List[Integer]):
    return lst.foldLeft(0)(_+_)

In Scala, foldLeft is a method in the List[Int] class and _ + _ is an anonymous function. FoldLeft can be used in many situations. For every monoid in a category, there is a foldLeft function. For example strings with concatenation or booleans with and. Monoids can get complex but no matter how complex it is, there is always a foldLeft function you can use. This illustrates how we can get a useful function, foldLeft, in this case, that comes directly from the caegorical notion of monoid. foldLeft is a vast generalization of adding up a bunch of numbers, concatenating a bunch of strings, or anding together a bunch of boolean expressions. Any monoid has a foldLeft (or foldRight) method, though, as I said, they may be named slightly differently in different languages.

Next we will look at natural transformations. Our goal is to get to monads, see where they come from and how they relate to functional programming.

Natural Transformations

To keep things simple, we will not go into all the technical details that make up the definition of natural transformations.14 My goal here is to give some idea of what a monad is, in the context of category theory, and more importantly, to make clear how they are useful in functional programming. If you wish, you can skip what follows, if you are not interested in the theoretical underpinnings of the monad. Then I will look at monads from a more practical, programming perspective. We need natural transformations in order to define monads. It just so happens that there is a way of thinking about natural transformations that is, well, natural. Functors, as we know, are functions from one category to another category (for example, from Scal to Scal). But we can change our perspective and build a new category where the objects of the new categories are the functors from the original category. Let us confine ourselves to endofunctors. Let us denote by End(C), the set of all functors from C to C, for some category C.

Now we want these functors to be the objects in a new category, and to do so, we need morphisms. That is, we need functions between endofunctors that satisfy the rules for morphisms. Natural transformations in the category C correspond to morphisms in this new category of endofunctors. What properties will these morphisms have?

Let E1, E2 and E3 be three endomorphisms of C. That is, they are three objects of End(C).
Let us further suppose we have two morphisms f and g where
f:E1E2 and g:E2E3.
Then by the definition of morphism, there exist the composition
gf:E1E3.
And this composition is associative. These morphisms, in End(C) are what we call natural transformations in the original category C. There is another definition of them, which you would ordinarily see in a category theory book, but that is a bit more involved. Thinking of them as morphisms in the category of endofunctors is more straightforward. In other words, we start with a category C, form the category End(C) and the morphisms of End(C) are natural transformations in C. Now how do we get from here to monads?

The trick is to bring in the concept of monoid again. Pick any endomorphism M in End(C). It turns out that M can be given the structure of a monoid. So we have a monoid (M, *, e) in the category End(C). We have a monoid in the category of endofunctors. This is a monad. A monoid in the category of endofunctors is how monads appear in category theory.

Note

Remember, every monad is a monoid but not every monoid is a monad. A monad is a monoid with some extra structure, which we defined above.

Now the road from a simple category to a monoid in the category of endofunctors is a long one. I just wanted to give you some feel for what is involved. There are ways of treating monads that are more practical and useful. In fact, there is a way to get from the * operation of the monoid to a function called flatMap and to get from the identity e in the monoid to a function called unit. And these two functions will provide us with a more practical way of describing monads.

Now a monad is a monoid and it is also a functor. As a functor, it has a map method (like all functors) and as a monad it also has a flatMap method.

Monads

We have hopefully gotten some idea of where monads come from. But what about monads from a practical perspective? Do we need to deal with endofunctors whenever we want to use a monad? And how are monads useful? It turns out that there is a much simpler description of monads in the category Scal (or any other category associated with a programming language). This simpler description has to do with the functions flatMap and unit.

flatMap and unit

In Scala, flatMap and unit are two functions you may have seen before. They have the following signature:

Scala

trait Monad[M[_]] {
      def flatMap[A](ma: M[A])(f: A => M[B]): M[B]
      def unit[A](a: A): M[A]
}

How should you think about monads? There is a mystery about them and based on my description of where they come from in category theory, this is not surprising. The definition of monad in a category theory is complex. There are many moving parts. But if we think of the above trait, it becomes easier. The best way to think about monads, from a functional programming perspective is that it provides a context for an object. We can also think of it as adding additional structure to an object.

Let’s start with unit, since this is simpler than flatMap. Unit takes an element of type A and puts it into the context M[A], where M is the monad above. So for example if M is Option, and we start with the string “abc”, we get the object Some(“abc”). And this has type Option[String]. It’s not quite right to say that Some(“abc”) is a string but we want to say something like this. Well we can say this is a String in the context of Option. We have Optionized the String. Or we can say we have added additional structure.

Now what about flatMap? Well let’s first consider the function map. That is simpler. So we have something like:

Let ma be of type M[A]. Suppose we have a function f:AB. Then ma.map(f) will give us a value of type M[B] . map will basically take the value ma out of its context M[A], apply f to it, get a value of type B and then wrap it in the context to get a value of type M[B].

But suppose now we have ma again, a value of type M[A], but now we have f:A M[B]. This happens alot. M might be Option or List, for example. If we try map, we get: ma.map(f). If you think this through, you will see map returns a value of type M[M[B]]. And this is probably not what we want. This is where flatMap comes into play. flatMap maps f over ma but then it flattens the result.

Let ma be of type M[A]. Let f:A M[B].
Then ma.flatMap(f) will return a value of type M[B], not M[M[B]] .

Let’s see an example of this:

Scala

class User(fname: String {
      def firstName: String  = firstName
}

def getUser(id: Int): Option[User]

val users = List(1,2,3).flatMap(id => getUser(id))

If we used map here instead of flatMap, we would have ended up with a List of options of users. flatMap maps and then flattens, In this example, flattening means taking the users out of the options. In general, flatMap is useful for chaining together functions that involve monads.

Incidentally, you only need flatMap and unit to have a monad. If you have these two, you can get map as follows:

Scala

m map g = m flatMap (x => unit(g(x)))

So we can say a monad is a trait (or interface of some kind depending on the programming language) that implements two methods. flatMap and unit. Also, every monad is also a functor. So it must have a map function. And the above expression shows how to get it from flatMap and unit.

To fully understand monad as it is in category theory would require more work. I hope you have gotten a feel for the complexity involved in constructing a monad on the one hand and the more straightforward programming approach where we model a monad as an interface or trait that implements flatMap and unit.

Also, when somebody asks you what a monad is, you can answer It is a monoid in the category of endofunctors and have, at least, a bit of an idea what that means.

Conclusion

You have learned what a category is, what the category Scal is, and some examples of how to apply functors, natural transformations, monoids and monads to your code. I will present more examples in the course of the book. It is important to emphasize here that it is not absolutely necessary to learn category theory before you learn about constructions like functors and monads and how to apply them to your code, but I believe knowing where these constructions come from will give more context and perhaps suggest novel ways of applying them to your code.

1 https://en.wikipedia.org/wiki/Software_design_pattern

2 https://www.amazon.com/Design-Patterns-Object-Oriented-Addison-Wesley-Professional-ebook/dp/B000SEIBB8

3 Let us make clear here that objects, in this context, are distinct from objects in object oriented programming.

4 As an example of this, consider the natural numbers. There is an arrow from m to n if m n. We get composition from transitivity of and we get identity arrows from reflexivity. i.e. n n for all n.

5 See chapter 2.

6 See chapter 2.

7 So for example, Negative numbers with multiplication couldn’t form a semigroup because when you multiply two negative numbers, you don’t get a nother negative number.

8 I call this category Scal because of the well established category Hask associated with the Haskell language.

9 For more familiarity with these concepts, see chapter 2.

10 Unless its a list of functions. In this example, we do not mean a list of functions. We are applying List to the function as a functor.

11 Opinion clearly labeled as such.

12 This part is a bit formula heavy. Feel free to skip it if its not your thing.

13 https://typelevel.org/cats

14 For more information on natural transformations, see https://en.wikipedia.org/wiki/Natural_transformation. Natural transformations are complex.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
54.243.2.41