Explaining monads

If you have grasped the mathematical basics, and if you have understood what’s a monoid, you are ready to discover monads. Of course, we’ll continue to have fun with F#. There are tons of approaches trying to explain what monads are. Personally, I found out once I understood the problem they are solving, thus it will be the approach of this blog post. Again, the following code can be found online.

First compositions rule

Remember the function composition rule: “The result of each function is passed as the argument of the next, and the result of the last one is the result of the whole “.

It means that functions must be “pluggable” (the output of the first must be compatible with the input of the second).  But It also implies that we need a side effects free world. If one of the function can throw an error, there is no more composition because the result of my function (an exception is thrown) is not passed as the argument of the next, and the result of the last function will not be the result of the whole. Instead it breaks the runtime, and someone at a higher level (the caller) must deal with it.

Note that there is nothing to explicit the fact that isPositive function can fail in this code. It compiles as everything seems fine, but it can fail at runtime.

Sometimes vs Always

What if instead of thowing an error sometimes (if i >0), we always return a Result, which is either a success containing the value, or a failure?

I can wrap my result into something to defer the side effects. Of course it implies changing my signatures. My functions are no longer compatible, because a Result<int> cannot be used as the input by the isPositive function, it expects a simple int.

Bind to the rescue

What if I write a simple transformation function, that I can call bind. Its roles are:

  • In case of success: to wrap my simple int into a Result<int>, and to call the next function with the wrapped result
  • In case of failure: to return a failure, and not to call the next function, because after all, we don’t need to execute the next function if the previous one fails.

And now I can call this function between two incompatible functions and… Voilà! They are pluggable again!

My final composition will look like this, and this time it compiles.
Of course, you probably don’t want to create special functions to apply the bind. F# like many languages allow us to define a proper operator bind: >>= (it is the common sign for bind operator).

A more elegant composition will look like this:

I get rid of side effects, thus I can compose my functions.

Dude, you lost me.

No problem, take a breath and think about that:

  • I wanted to compose functions, but they have side effects
  • I wanted to get rid of side effects, thus I introduce the Result<T> instead of throwing an exception
  • My functions where no longer “pluggable”, thus I introduced a bind function to transform a simple type into a more complex Result<T> type.
  • We defined a new operator bind (>>=) to replace the explicit bind call
  • In the end I can have a nice composition, without the side effects

This can be resume by: we find a way to compose function, despite the side effects.

And where’s the monad?

Let’s decrypt the Wikipedia definition of a monad and see if something match:

“Monads allow developer to build pipelines that process data in a series of steps, in which each action is decorated with the additional processing rules provided by the monad.”

Sounds familiar?  In our case we had a pipeline (ToInt -> IsPositive -> ToString), and we decorated each step with the ability to convert from T to Result<T> (and to escape the pipeline in case of failure). You understand that we could have done other things in our bind function, such as Logging, Exception handling, IO management… We managed side effects in the bind used to compose the functions, instead of in the functions themselves.

“A monad is defined by a return operator that creates values, and a bind operator used to link the actions in the pipeline; this definition must follow a set of axioms called monad laws, which are needed for the composition of actions in the pipeline to work properly. The result of the last one is the result of the whole.”

I think we talked enough about the bind function. In our case, the return function is as simple as: return x -> x

Here are the monad’s laws: return acts approximately as a neutral element of bind, in that:

  • (return x) >>= f ≡ f x
  • m >>= return ≡ m

Binding two functions in succession is the same as binding one function that can be determined from them (in other words: bind is associative):

  • (m >>= f) >>= g ≡ m >>= (x -> (f x >>= g))

This is what these tests demonstrate:

Thus, the type we defined Result<T>, with the associated bind and return functions is a monad. The container alone is not a monad. The bind function alone is not a monad. But the container Result<T> with the bind function, because this function defines the identity function (i.e. a return function) when used with a neutral element, and because it is associative, is a monad.

Last words

Let’s finish the Wikipedia decryption:

“Purely functional programs can use monads to structure procedures that include sequenced operations like those found in structured programming. Many common programming concepts can be described in terms of a monad structure without losing the beneficial property of referential transparency, including side effects such as input/output, variable assignment, exception handling, parsing, nondeterminism, concurrency, continuations, or domain-specific languages. This allows these concepts to be defined in a purely functional manner, without major extensions to the language’s semantics.”

And because input/output, variable assignment, exception handling, parsing, nondeterminism, concurrency, continuations and DSL are very common IT problems, FP use monads a lot to manage them. I hope it is now clear for you how we used a monad to structure our chain of operation, and how we managed exception in a purely functional manner.

If so, you now understand what’s a monad, and why it is so useful, especially in FP. If not, please let me know and I’ll try to improve my explanations!

 

References: If you feel frustrated and want to go further, I recommand you the excellent Category Theory for Beginners, and the even better (but harder) Category Theory for Programmers.

 

Explaining Monoids

Let’s have some fun with F#. Through example, we will discover together what are monoids, and why they could be useful. All the following code can be found online.

Function composition example with integers

We now all agree about what’s function composition. We all know what are integers. So, let’s compose some functions using the set of integers.

As shown in this code, add and minus for the set of integers are functions defining a rule of combining two elements for the set of integers. These functions have two interesting properties: they are associative, and they behave as an identity function when the neutral element is one of the input.

As you can guess, the neutral element in this case is 0. You can trust me, or you can just run this code instead:

Let’s wrap up: the set of integers has a rule (add) for combining two elements of the set, this rule is associative and has a neutral element (0).

 

Function composition example with hours 

We can also agree on what are hours (positive integers between 1 and 24), so we could compose some functions using the set of hours.

As it happens, we can also defined add and minus operation on hours. It’s a bit more interesting now, because these operations use a modulo, it’s no longer a simple operation. We can still prove associativity and the existence of a neutral element for the set hours on operation add.

We can add to our knowledge that the set of hours has a rule (add) for combining two elements of the set, this rule is associative and  has a neutral element (24).
 

Monoid land

Monoids are a collection of things (a set) with a rule of combining two elements of this set together (this rule is called the internal law of composition). This composition law has to be associative, and to contain a neutral element (otherwise it is not a monoid, but it could be another mathematical structure like a magma or a semigroup that we won’t detail here, because they have less interest for a programmer).

Does it remember you something? You got it:

  • The integers set with the function add is a monoid, because add is a rule to combine two int together, add is associative, and add is an identity function when it is used with the neutral element of the set which is zero.
  • The hours set with the function add is a monoid, because add is a rule to combine two hours together, add is associative, and add is an identity function when it is used with the neutral element of the set which is 24.

We use simple examples here, but please understand that any law (function) defining the combination of two element of a set, that is associative and behave as an identity function when used with a neutral element, is a valid rule to define a monoid. No matter the name or the complexity of this function. Note also that we call monoid the set with the function. Integers are not monoids. But integers with the function add is a monoid. Hours with the function add is another monoid. You can’t define a monoid without its internal law of composition.

Parallel Monoid

The coolest thing about monoid is the associativity law. And the cool thing with associativity in programming is that it allows parallel streams. Why?
Because if (f°g)°h =f°(g°h), you don’t care which function is executed in which order. How convenient is that for parallel processing?
 

Monoids everywhere

Cyrille Martraire has a great talk to explain why you should look for monoids in your domain. By their very nature, you can assume they have a neutral element, they are composable and parallelizable (because they are associative), and they are based on a set of value objects. You say all that when you say that something is a monoid in your domain.

Monoids are powerful and deserve to be known, as you probably use them already without noticing their existence!

 

What’s composition?

You remember that Functional Programming (FP) is all about function composition? But what’s composition by the way? Let’s explain it here with a few other useful concepts for FP, and go one step further in monads understanding.

Integer composition

A composition of integer in mathematics is a way of writing N as the sum of a sequence strictly positive. Weak composition is for sequence positive or equal to zero. It means that every positive integer admits infinitely many weak compositions. 0 is also known as the neutral element for the set of integers.

Function composition

A function composition is when we apply a function (say f) to the result of another one (say g) to produce a third function (say h). We write it h=g°f. Intuitively, composing two functions is a chaining process in which the output of the inner function becomes the input of the outer function. This is in essence functional programming.

Identity Function

A function that returns exactly its input as the output without any alteration is also known as the identity function. There is a symetry between weak composition of integers and weak composition of functions, because an identity function is a neutral element for the set of functions. Like 0 for integers, it can help in several situations to allow more composition. Which is useful, because we want to compose everything!

Which functions are composable?

Two functions are composable if their Domain and Co-Domain are compatible. Let’s imagine two functions:

  • StringToInt : s (string) -> i (integer) StringToInt is a function mapping a string (Domain) with an integer (Co-Domain).
  • TwoTimes: i (integer) -> o (integer) TwoTimes is a function mapping an integer (Domain) with another integer (Co-Domain).

Can I imagine a composition TwoTimes>>StringToInt? No because TwoTimes output is an integer, and StringToInt input is a string. The Co-Domain of TwoTimes is not compatible with the Domain of StringToInt. But the Co-Domain of StringToInt is compatible with the Domain of TwoTimes. Thus, we could define a correct composition StringToInt>> TwoTimes. Most FP patterns are just a way to wrap data so that Domain and Co-Domain stay compatible, thus composable, despite side effects.

Composable functions properties

If functions are composable, they can be associative if the Domain and the Co-Domain are suitable. It means: g°f(x) = g(x)°f .
You know for example that addition is associative.
So if g is +5, f is +10 and if x is 3, we can write: 5+ (3+10) = (5+3) + 10 = 18.
Note that, if two functions have the same Domain and Co-Domain, they are composable, and associative. The composition of functions with the same Domain and Co-Domain are called transformations, because mathematicians like to give a name to everything (and for once it seems a logical name).

How powerful is function composition?

In a few words: it allows to express complex things in a simple form. In physics for example, Lorentz Transformations are very famous. Using a series of transformation, Lorentz showed that the speed of light is the same in all inertial reference frames. The invariance of light speed is one of the postulates of Einstein’s Special Relativity theory.

Of course we’re not Einstein, but expressing complex things in a simple form is definitely something interesting for software design.

 

Do you know what’s a function?

I’m so used to functions in my daily job as software programmer that I was sure to know what it is. As often I was wrong, let me tell you why.

Function and relation

I intuitively called a function anything in my code with an input and an output. I suspected that functions without input and/or output where a special kind of functions. But in truth, f: a->b defines a relation between a and b. The Domain is the set containing a, and the Co-Domain is the set containing b.  A relation maps an input from the Domain with an output in the Co-Domain. A relation can be:

Back to code

If a relation can map an element from the Domain with several elements in the Co-Domain, it is not a function. Do I code a lot of relation with different possible outputs for the same input? Yes, any function with side effects when a is an element of the Domain, can produce different output for the same input. They are not functions by the mathematical definition.

It also means that we can’t define a function without defining the Domain and the Co-Domain. If we change the Domain or the Co-Domain, a relation can be a function or not. A famous example is the SquareRoot relation because:

Sqrt : a (|R) -> b (|R) is not a function (indeed, sqrt(4) can be either 2 or – 2).

PositiveSqrt: a (|R+) -> b (|R+) is a function (a subset of squareRoot that return only the positive value)

Note as well that constraining the Domain and the Co-Domain can make the function more specific (injective, bijective, or both).

So what?

Ok my coding function are not mathematical function, why should I care? Let me ask a different question: why do mathematicians care to manipulate functions instead of relations? Because it’s easier to reason about.

In the same way, the more specific the relation is, the more predictable the code will be. If a relation can produce several outputs for the same inputs, the code is not predictable. It means that my relation depends of a more global context, and thus I can’t reason at the function scale without taking this context into account. On the other hand when my relation is a function (usually called pure function in FP, ie without side effects) my code is predictable, and I can think at a function scale without considering the global context.

It is really powerful, because It doesn’t really matter how smart you are if you have the ability to split a complex problem into simple ones.

 
IP Blocking Protection is enabled by IP Address Blocker from LionScripts.com.