Functional PHP (2017)
Chapter 5. Functors, Applicatives, and Monads
The previous chapter introduced the first real functional techniques, such as function composition and currying. In this chapter, we will delve into more theoretical concepts again by presenting the concept of monads. There won't be a lot of practical application as we have a lot of ground to cover. However, Chapter 6, Real-life Monads will use everything we learn here to solve real issues.
You might already have heard the term monad. Usually, it is associated with a sense of dread by non functional programmers. Monads are usually described as hard to understand despite countless tutorials on the subject. The fact is, they are hard to understand and people writing those tutorials often forget how much time it took them to understand the idea correctly. This is a common pedagogic pitfall, probably much better described in this article at https://byorgey.wordpress.com/2009/01/12/abstraction-intuition-and-the-monad-tutorial-fallacy/.
You will probably not get everything the first time. Monads are a highly abstract concept and, even if the topic seems clear to you at the end of the chapter, you will probably stumble upon something later on that will baffle your intuition of what a monad really is.
I will try to do my best to explain things clearly, but if you find my explanations lacking, I added references to other material about the topic in the Further reading section at the end of this chapter. In this chapter, we will cover the following topics:
· Functors and related laws
· Applicative functors and related laws
· Monoids and related laws
· Monads and related laws
There will be a lot of theoretical content only with implementation of the concepts. Don't expect a lot of examples until Chapter 6, Real-life Monads.
Functors
Before speaking directly of monads, let us start at the beginning. In order to understand what a monad is, we need to introduce a few related concepts. The first one is functors.
To complicate matters a bit, the term functor is used in imperative programming to describe a function object, which is something totally different. In PHP, an object with the __invoke method, as we saw in Chapter 1, Functions as First Class Citizens, is such a function object.
However, in functional programming, a functor is a concept taken and adapted from the mathematical field of category theory. Details aren't that important for our purpose; it suffice it to say that a functor is a pattern allowing us to map a function to one or more values contained in a context. Also, in order for the definition to be as complete as possible, our functor must respect some laws, which we will describe and verify later.
We have already used map multiple times on collections, which makes them de facto functors. But if you remember correctly, we also named our method to apply a function to the value contained in Maybe in the same way. The reason is that functors can be seen as containers with a means to apply a function to the contained value.
In a sense, any class that implements the following interface could be called a Functor:
<?php
interface Functor
{
public function map(callable $f): Functor;
}
However, describing it like that is a bit reductive. A simple PHP array is also a functor (because the array_map function exists), as is anything implementing the Traversable interface as soon as you use the functional-php library and its map function.
Why such a fuss for such a simple idea? Because, although the idea is simple in itself, it allows us to reason about what is happening in a different light and possibly helps understand and refactor the code.
Also, the map function can do much more than blindly apply the given callable type, as is the case with an array. If you remember our Maybe type implementation, in the case of a value Nothing, the map function simply kept returning the Nothing value in order to allow for a simpler management of null values.
We could also imagine having much more complicated data structures in our functors, such as trees, where the function given to the map function is applied to all nodes.
Functors allow us to share a common interface, our map method or function, to perform a similar operation on a variety of data types while hiding the complexity of the implementation. As often with functional programming, the cognitive burden is reduced because you don't have multiple names for an identical operation. Function and method names such as "apply", "perform", and "walk" are often seen to describe the same thing for example.
Identity function
Our final concern is the two functor laws that come with the concept. But before introducing them, we need to take a small detour about the identity function, or often id. It is a really simple function that simply returns its parameter:
<?php
function id($value)
{
return $value;
}
Why would anyone need a function doing as little as this? First of all, we will need it later to prove the laws of the various abstractions presented in this chapter. But real-world applications also exist.
For example, when you are doing a fold with numbers, say summing them, you will use the initial value 0. The id function will have the same role when folding over functions. As a matter of fact, the compose function is implemented using the id function in the functional-php library.
Another use might be some function from another library that performs an operation you are interested in, but also calls a callback on the resulting data. If the callback is mandatory, but you don't want to do anything else to your data, just pass id and you will get them unaltered.
Let's use our new function to declare a property of our compose function for any function f, taking only one argument:
compose(id, f) == compose(f, id)
What this basically says is that, if you first apply the argument id then f, you will get the exact same result as when first applying f and then id. At this point, this should be evident to you. If not, I encourage you to revisit the last chapter until you clearly understand why this is the case.
Functor laws
Now that we have our identity function covered, let's get back to our laws. They are important for two reasons:
· They give us a set of constraints to guarantee the validity of our functors
· They allow us to perform refactoring that is proven correct
Without further ado, here they are:
1. map(id) == id
2. compose(map(f), map(g)) == map(compose(f, g))
The first law states that mapping the id function on the contained value is exactly the same as calling the id function directly on the functor itself. When this law holds, this guarantees us that our map function only applies the given function to the data without performing any other kind of treatment.
The second law states that first mapping the f function then the g one on our value is the same as first composing f and g together and then mapping the resulting function. Knowing this, we can perform all kinds of optimization. For example, instead of looping three times over our data for three different methods, we can compose them together and perform only one loop.
I can imagine not everything being crystal clear for you right now, so instead of wasting time trying to explain them further, let's verify if they hold for the array_map method. This will probably help you to get the gist of it; the following code expects the id function defined previously to be in scope :
<?php
$data = [1, 2, 3, 4];
var_dump(array_map('id', $data) === id($data));
// bool(true)
function add2($a)
{
return $a + 2;
}
function times10($a)
{
return $a * 10;
}
function composed($a) {
return add2(times10($a));
}
var_dump(
array_map('add2', array_map('times10', $data)) === array_map('composed', $data)
);
// bool(true)
The composition is performed manually; as in my opinion resorting to currying here would only have made things more complicated.
As we can see, both laws hold for the array_map method, which is a good sign because it means there is no hidden data processing done in the shadow and we can avoid looping two or more times on our array when only once is enough.
Let's try the same with our Maybe type defined earlier:
<?php
$just = Maybe::just(10);
$nothing = Maybe::nothing();
var_dump($just->map('id') == id($just));
// bool(true)
var_dump($nothing->map('id') === id($nothing));
// bool(true)
We had to switch to a non-strict equality for the $just case because we would have a result of false otherwise as PHP compares object instances and not their values. A Maybe type wraps the resulting value in a new object and PHP only performs internal value comparison in the case of a non-strict equality; the add2, times10, and composed functions defined above are expected to be in scope:
<?php
var_dump($just->map('times10')->map('add2') == $just->map('composed'));
// bool(true)
var_dump($nothing->map('times10')->map('add2') === $nothing->map('composed'));
// bool(true)
Great, our Maybe type implementation is a valid functor.
Identity functor
As we discussed in the section about the identity function, an identity functor also exists. It acts as a really simple functor that does nothing to the value besides holding it:
<?php
class IdentityFunctor implements Functor
{
private $value;
public function __construct($value)
{
$this->value = $value;
}
public function map(callable $f): Functor
{
return new static($f($this->value));
}
public function get()
{
return $this->value;
}
}
As with the identity function, the use for such a functor is not immediately evident. However, the idea is the same-you can use it when you have some function having a functor as a parameter, but you don't want to modify your actual value.
This should begin to make more sense in the following chapters of this book. In the meantime, we will use the identity functor to explain some more advanced concepts.
Closing words
Let me reiterate again that functors are a really simple abstraction to understand, but also a really powerful one. We've seen only two of them, but an infinity of data structures that can be transformed to functors really easily.
Any function or class that allows you to map a given function to one or more values held in a context can be considered a functor. Identity functors or arrays are simple example of such a context; other examples would be the Maybe and Either types we discussed earlier or any class having a map method that allows you to apply a function to the contained valued.
I cannot encourage you enough to try implementing this map pattern and verify whether both laws hold wherever you create a new class or data structure. This will allow you to have an easier understanding of what your code can perform and you will be able to perform optimization using composition with the guarantee that your refactoring is correct.
Applicative functors
Let's take an instance of our identity functor, holding some integer and a curryied version of an add function:
<?php
$add = curry(function(int $a, int $b) { return $a + $b; });
$id = new IdentityFunctor(5);
Now, what happens when we try to map the $add parameter on our functor? Consider the following code:
<?php
$hum = $id->map($add);
echo get_class($hum->get());
// Closure
As you may have guessed, our functor now contains a closure representing a partially applied add parameter with the value 5 as the first parameter. You can use the get method to retrieve the function and use it, but it is not really that useful.
Another possibility would be to map another function, taking our function as a parameter, and doing something with it:
<?php
$result = $hum->map(function(callable $f) {
return $f(10);
});
echo $result->get();
// 15
But I imagine we can all agree that this is not a really effective way to perform such an operation. What would be great is to be able to simply pass the value 10 or maybe another functor to $hum and achieve the same result.
Enters the applicative functor. As the name suggests, the idea is to apply functors. More precisely, to apply functors to other functors. In our case, we could apply $hum, which is a functor containing a function, to another functor containing the value 10 and obtain the value 15 we are after.
Let's create an extended version of our IdentityFunctor class to test our idea:
<?php
class IdentityFunctorExtended extends IdentityFunctor
{
public function apply(IdentityFunctorExtended $f)
{
return $f->map($this->get());
}
}
$applicative = (new IdentityFunctorExtended(5))->map($add);
$ten = new IdentityFunctorExtended(10);
echo $applicative->apply($ten)->get();
// 15
You can even create your Applicative class containing only your function and apply the values afterwards:
<?php
$five = new IdentityFunctorExtended(5);
$ten = new IdentityFunctorExtended(10);
$applicative = new IdentityFunctorExtended($add);
echo $applicative->apply($five)->apply($ten)->get();
// 15
The applicative abstraction
We are now able to use our IdentifyFunctor class as a curryied function holder. What if we could abstract this idea away and create something on top of the Functor class?
<?php
abstract class Applicative implements Functor
{
public abstract static function pure($value): Applicative;
public abstract function apply(Applicative $f): Applicative;
public function map(callable $f): Functor
{
return $this->pure($f)->apply($this);
}
}
As you can see, we created a new abstract class instead of an interface. The reason is because we can implement the map function using the pure and apply methods so it makes no sense to force everyone wanting to create an Applicative class to implement it.
The pure function is called so because anything stored inside an Applicative class is considered pure as there is no way to modify it directly. The term is taken from the Haskell implementation. Other implementations sometimes use the name unit instead. pure is used to create a new applicative from any callable.
The apply function applies the stored function to the given parameter. The parameter must be of the same type so that the implementation knows how to access the inner value. Sadly, the PHP type system does not allow us to enforce this rule and we must resign ourselves to defaulting to Applicative.
We have the same issue for the definition of map that has to keep the return type as Functor. We need to do this as the PHP type engine does not support a feature called return type covariance. If it did, we could specify a more specialized type (that is a child type) as a return value.
The map function is implemented using the aforementioned functions. First we encapsulate our callable using the pure method and we apply this new applicative on the actual value. Nothing really fancy.
Let's test our implementation:
<?php
$five = IdentityApplicative::pure(5);
$ten = IdentityApplicative::pure(10);
$applicative = IdentityApplicative::pure($add);
echo $applicative->apply($five)->apply($ten)->get();
// 15
$hello = IdentityApplicative::pure('Hello world!');
echo IdentityApplicative::pure('strtoupper')->apply($hello)->get();
// HELLO WORLD!
echo $hello->map('strtoupper')->get();
// HELLO WORLD!
Everything seems to work fine. We were even able to verify that our map implementation seems to be correct.
As with the functor, we can create the simplest of the Applicative class abstraction:
<?php
class IdentityApplicative extends Applicative
{
private $value;
protected function __construct($value)
{
$this->value = $value;
}
public static function pure($value): Applicative
{
return new static($value);
}
public function apply(Applicative $f): Applicative
{
return static::pure($this->get()($f->get()));
}
public function get()
{
return $this->value;
}
}
Applicative laws
The first important property of applicative is that they are closed under composition, meaning an applicative will return a new applicative of the same type. Also, the apply method takes an applicative of its own type. We cannot enforce this using the PHP type system, so you will need to be careful otherwise something might break at some point.
The following rules also need to be respected to have a proper applicative functor. We will first present them all in detail and then verify that they hold for our IdentityApplicative class later.
Map
pure(f)->apply == map(f)
Applying a function using an applicatives is the same as mapping this function over. This law simply tells us that we can use an applicative anywhere we used a functor before. We lose no power by switching to an applicative.
In fact, this is not really a law as it can be inferred from the following four laws. But as it is not at all evident, and in order to make things clearer, let's state it.
Identity
pure(id)->apply($x) == id($x)
Applying the identity function results in no change to the value. As with the identity law for functors, this ensure that the apply method does nothing but apply the function. No hidden transformation is happening behind our backs.
Homomorphism
pure(f)->apply($x) == pure(f($x))
Creating an applicative functor and applying it to a value has the same effect as first calling the function on the value and boxing it inside the functor afterwards.
This is an important law because our first motivation to dive into applicative is usage of the curryied function instead of unary functions. This law ensures that we can create our applicative at any stage instead of needing to box our function right away.
Interchange
pure(f)->apply($x) == pure(function($f) { $f($x); })->apply(f)
This one is a bit tricky. It states that applying a function on a value is the same as creating an applicative functor with a lifted value and applying it to the function. In this case, a lifted value is a closure around the value that will call the given function on it. The law guarantees that the pure function performs no modification besides boxing the given value.
Composition
pure(compose)->apply(f1)->apply(f2)->apply($x) == pure(f1)->apply(pure(f2)->apply($x))
A simpler version of this law could be written with pure(compose(f1, f2))->apply($x) on the left-hand side. It simply states, as the composition law for functors, that you can apply a composed version of two functions to your value or call them separately. This ensures that you can perform the same optimizations for functors.
Verifying that the laws hold
As we saw for functors, it is more than recommended to test whether your implementations hold for all laws. This can be a really tedious process, especially if you have four of them. So instead of performing the check manually, let's write a helper:
<?php
function check_applicative_laws(Applicative $f1, callable $f2, $x)
{
$identity = function($x) { return $x; };
$compose = function(callable $a) {
return function(callable $b) use($a) {
return function($x) use($a, $b) {
return $a($b($x));
};
};
};
$pure_x = $f1->pure($x);
$pure_f2 = $f1->pure($f2);
return [
'identity' =>
$f1->pure($identity)->apply($pure_x) ==
$pure_x,
'homomorphism' =>
$f1->pure($f2)->apply($pure_x) ==
$f1->pure($f2($x)),
'interchange' =>
$f1->apply($pure_x) ==
$f1->pure(function($f) use($x) { return $f($x); })->apply($f1),
'composition' =>
$f1->pure($compose)->apply($f1)->apply($pure_f2)->apply($pure_x) ==
$f1->apply($pure_f2->apply($pure_x)),
'map' =>
$pure_f2->apply($pure_x) ==
$pure_x->map($f2)
];
}
The identity and compose functions are declared inside the helper so that it is completely self-contained and you can use it in a variety of situations. Also the compose function from the functional-php library is not adapted as it is not curryied and it takes a variable number of arguments.
Also, in order to avoid having a lot of arguments, we take an instance of the Applicative class so we can have a first function and the type to check and then a callable and a value that will be lifted to the applicative and used whenever necessary.
This choice limits the functions we can use as the value must match the type of the parameter for both functions; the first function must also return a parameter of the same type. If this is too constraining for you, you can decide to extend the helper to take two more arguments, a second applicative and a lifted value, and use those when necessary.
Let's verify our IdentityApplicative class:
<?php
print_r(check_applicative_laws(
IdentityApplicative::pure('strtoupper'),
'trim',
' Hello World! '
));
// Array
// (
// [identity] => 1
// [homomorphism] => 1
// [interchange] => 1
// [composition] => 1
// [map] => 1
// )
Great, everything seems to be fine. If you want to use this helper, you need to choose functions that are compatible as you might encounter some error messages that lack clarity as we cannot ensure that the type of the return value for the first function matches the type of the first parameter for the second function.
Since this kind of automatic checking can greatly help, let us quickly write the same kind of function for functors:
<?php
function check_functor_laws(Functor $func, callable $f, callable $g)
{
$id = function($a) { return $a; };
$composed = function($a) use($f, $g) { return $g($f($a)); };
return [
'identity' => $func->map($id) == $id($func),
'composition' => $func->map($f)->map($g) == $func->map($composed)
];
}
And check our never tested IdentityFunctor with it:
<?php
print_r(check_functor_laws(
new IdentityFunctor(10),
function($a) { return $a * 10; },
function($a) { return $a + 2; }
));
// Array
// (
// [identity] => 1
// [composition] => 1
// )
Good, everything is fine.
Using applicatives
As we already saw, arrays are functors, because they have a map function. But a collection can also easily be an applicative. Let's implement a CollectionApplicative class:
<?php
class CollectionApplicative extends Applicative implements IteratorAggregate
{
private $values;
protected function __construct($values)
{
$this->values = $values;
}
public static function pure($values): Applicative
{
if($values instanceof Traversable) {
$values = iterator_to_array($values);
} else if(! is_array($values)) {
$values = [$values];
}
return new static($values);
}
public function apply(Applicative $data): Applicative
{
return $this->pure(array_reduce($this->values,
function($acc, callable $function) use($data) {
return array_merge($acc, array_map($function, $data->values) );
}, [])
);
}
public function getIterator() {
return new ArrayIterator($this->values);
}
}
As you can see, this is all fairly easy. To simplify our life we just wrap anything that is not a collection inside an array and we transform instances of the Traversable interface to a real array. This code would obviously need some improvement to be used in production, but it will suffice for our little demonstration:
<?php
print_r(iterator_to_array(CollectionApplicative::pure([
function($a) { return $a * 2; },
function($a) { return $a + 10; }
])->apply(CollectionApplicative::pure([1, 2, 3]))));
// Array
// (
// [0] => 2
// [1] => 4
// [2] => 6
// [3] => 11
// [4] => 12
// [5] => 13
// )
What is happening here? We have a list of functions in our applicative and we apply that to a list of numbers. The result is a new list with each function applied to each number.
This small example is not really useful, but the idea can be applied to anything. Imagine you have some kind of image gallery application where the user can upload some images. You also have various processing you want to make on those images:
· Limiting the size of the final image as the user tends to upload them too big
· Creating a thumbnail for the index page
· Creating a small version for mobile devices
The only thing you need to do is create an array of all your functions, an array of the uploaded images, and apply the same pattern we just did to our numbers. You can then use the group function from the functional-php library to regroup your images together:
<?php
use function Functional\group;
function limit_size($image) { return $image; }
function thumbnail($image) { return $image.'_tn'; }
function mobile($image) { return $image.'_small'; }
$images = CollectionApplicative::pure(['one', 'two', 'three']);
$process = CollectionApplicative::pure([
'limit_size', 'thumbnail', 'mobile'
]);
$transformed = group($process->apply($images), function($image, $index) {
return $index % 3;
});
We use the index in the transformed array to regroup the images together. Every third image is the limited one, every fourth the thumbnail, and finally we have the mobile version. The result can be seen as follows:
<?php
print_r($transformed);
// Array
// (
// [0] => Array
// (
// [0] => one
// [3] =>one_tn
// [6] =>one_small
// )
//
// [1] => Array
// (
// [1] => two
// [4] =>two_tn
// [7] =>two_small
// )
//
// [2] => Array
// (
// [2] => three
// [5] =>three_tn
// [8] =>three_small
// )
//
//)
You might be hungry for more at this stage, but you will need to be patient. Let's finish first with the theory in this chapter and we will soon see more potent examples in the next.
Monoids
Now that we have an understanding of applicative functors, we need to add one last piece to the puzzle before speaking about monads, the monoid. Once again, the concept is taken from the mathematical field of category theory.
A monoid is a combination of any type and a binary operation on this type with an associated identity element. For example, here are some combinations that you probably never expected were monoids:
· Integer number and the addition operation, the identity being 0 because$i + 0 == $i
· Integer number and the multiplication operation, the identity being 1 because$i * 1 == $i
· Arrays and the merge operation, the identity being the empty array because array_merge($a, []) == $a
· String and the concatenate operation, the identity being the empty string because $s . '' == $s
For the remainder of the chapter, let's call our operation op and the identity element id. The op call comes from operation or operator and is used in some Monoid implementation across multiple languages. Haskell uses the terms mempty and mappend to avoid clashes with other function names. Sometimes zero is used instead of id or identity.
A monoid must also respect a certain number of laws, two to be precise.
Identity law
$a op id == id op $a == $a
The first law ensures that the identity can be used on both sides of the operator. An identity element can work only when applied as the right-hand or left-hand side of the operator. This is, for example, the case for operations on matrices. In this case, we speak of left and right identity elements. In the case of a Monoid, we need a two-sided identity, or simply identity.
As for most identity laws, verifying it for a Monoid implementation ensures that we correctly apply the operator with no other side-effects.
Associativity law
($a op $b) op $c == $a op ($b op $c)
This law guarantees that we can regroup our call to the operator in any order we want, as long as some other operations are not interleaved. This is important because it allows us to reason about possible optimization with the insurance that the result will be the same.
Knowing that a sequence of operations is associative; you can also separate the sequence into multiple parts, distribute the computation across multiple threads, cores, or computers, and when all the intermediary results come in, apply the operation between them to get the final result.
Verifying that the laws hold
Let's verify those laws for the monoids we spoke about earlier. First, the integer addition:
<?php
$a = 10; $b = 20; $c = 30;
var_dump($a + 0 === $a);
// bool(true)
var_dump(0 + $a === $a);
// bool(true)
var_dump(($a + $b) + $c === $a + ($b + $c));
// bool(true)
Then, the integer multiplication:
<?php
var_dump($a * 1 === $a);
// bool(true)
var_dump(1 * $a === $a);
// bool(true)
var_dump(($a * $b) * $c === $a * ($b * $c));
// bool(true)
Then the array merge as follows:
<?php
$v1 = [1, 2, 3]; $v2 = [5]; $v3 = [10];
var_dump(array_merge($v1, []) === $v1);
// bool(true)
var_dump(array_merge([], $v1) === $v1);
// bool(true)
var_dump(
array_merge(array_merge($v1, $v2), $v3) ===
array_merge($v1, array_merge($v2, $v3))
);
// bool(true)
And finally, the string concatenation:
<?php
$s1 = "Hello"; $s2 = " World"; $s3 = "!";
var_dump($s1 . '' === $s1);
// bool(true)
var_dump('' . $s1 === $s1);
// bool(true)
var_dump(($s1 . $s2) . $s3 == $s1 . ($s2 . $s3));
// bool(true)
Great, all our monoids respect both laws.
What about subtraction or division? Are they also a monoid? It's pretty obvious that 0 is the identity of subtraction and 1 is the identity for division, but what about associativity?
Consider the following for checking the associativity of subtraction or division:
<?php
var_dump(($a - $b) - $c === $a - ($b - $c));
// bool(false)
var_dump(($a / $b) / $c === $a / ($b / $c));
// bool(false)
We clearly see that neither subtraction nor division is associative. When working with such abstraction, it is always important to test our assumption using the law. Otherwise a refactoring or calling some function expecting a Monoid could go really wrong. Obviously, the same applies for functors and applicatives.
What are monoids useful for?
Honestly, monoids themselves are not really useful, especially in PHP. Eventually, in a language where you can either declare new operators or redefine existing ones, you could ensure their associativity and the existence of an identity using monoids. But even so, there would be no real advantages.
Also, if the language could automatically distribute work done with operators that are part of a Monoid, it would be a great way to speed up lengthy computation. But I am not aware of any language, even academic ones, that are currently capable of doing so. Some languages perform operation reordering to improve efficiency, but that's about it. Obviously, PHP can't do any of that since the concept of monoid is not in the core.
Why bother then? Because monoids can be used with higher-order functions and some constructs that we will discover later can take full advantage of their laws. Also, since PHP does not allow us to use existing operators as functions, as is the case with Haskell, for example, we've had to define functions such as add before. Instead, we can define a Monoid class. It would have the same utility as our simple function with some nice properties added.
At the risk of sounding like a broken record, explicitly stating that an operation is a monoid reduces cognitive burden. When using a monoid, you have the assurance that the operation is associative and that it respects a two-sided identity.
A monoid implementation
PHP does not support generics, so we have no way to encode the type information of our Monoid formally. You will have to choose a self-explanatory name or document that is the type clearly.
Also, as we want our implementation to replace functions such as add, we need some additional methods on our class to allow for this usage. Let's see what we can do:
<?php
abstract class Monoid
{
public abstract static function id();
public abstract static function op($a, $b);
public static function concat(array $values)
{
$class = get_called_class();
return array_reduce($values, [$class, 'op'], [$class, 'id']());
}
public function __invoke(...$args)
{
switch(count($args)) {
case 0: throw new RuntimeException("Except at least 1 parameter");
case 1:
return function($b) use($args) {
return static::op($args[0], $b);
};
default:
return static::concat($args);
}
}
}
Obviously, we have our id and op functions declared abstract as those will be the specific parts for each of our monoids.
One of the main advantages of having a Monoid is easily being able to fold a collection of values having the type of the Monoid class. This is why we create the concat method as a helper to do exactly that.
Finally, we have an __invoke function so that our Monoid can be used like a normal function. The function is curryied in a specific way. If you pass more than one parameter on the first call, the concat method will be used to return a result immediately. Otherwise, with exactly one parameter, you will get a new function waiting for a second parameter.
Since we are at it, let's write a function to check the laws:
<?php
function check_monoid_laws(Monoid $m, $a, $b, $c)
{
return [
'left identity' => $m->op($m->id(), $a) == $a,
'right identity' => $m->op($a, $m->id()) == $a,
'associativity' =>
$m->op($m->op($a, $b), $c) ==
$m->op($a, $m->op($b, $c))
];
}
Our first monoids
Let's create monoids for the cases we've seen previously and demonstrate how we can use them:
<?php
class IntSum extends Monoid
{
public static function id() { return 0; }
public static function op($a, $b) { return $a + $b; }
}
class IntProduct extends Monoid
{
public static function id() { return 1; }
public static function op($a, $b) { return $a * $b; }
}
class StringConcat extends Monoid
{
public static function id() { return ''; }
public static function op($a, $b) { return $a.$b; }
}
class ArrayMerge extends Monoid
{
public static function id() { return []; }
public static function op($a, $b) { return array_merge($a, $b); }
}
Let's validate the laws on them:
<?php
print_r(check_monoid_laws(new IntSum(), 5, 10, 20));
// Array
// (
// [left identity] => 1
// [right identity] => 1
// [associativity] => 1
// )
print_r(check_monoid_laws(new IntProduct(), 5, 10, 20));
// Array
// (
// [left identity] => 1
// [right identity] => 1
// [associativity] => 1
// )
print_r(check_monoid_laws(new StringConcat(), "Hello ", "World", "!"));
// Array
// (
// [left identity] => 1
// [right identity] => 1
// [associativity] => 1
// )
print_r(check_monoid_laws(new ArrayMerge(), [1, 2, 3], [4, 5], [10]));
// Array
// (
// [left identity] => 1
// [right identity] => 1
// [associativity] => 1
// )
For the example, let's try to create a monoid for subtraction and check the laws:
<?php
class IntSubtraction extends Monoid
{
public static function id() { return 0; }
public static function op($a, $b) { return $a - $b; }
}
print_r(check_monoid_laws(new IntSubtraction(), 5, 10, 20));
// Array
// (
// [left identity] =>
// [right identity] => 1
// [associativity] =>
// )
As expected, the associativity laws fail. We also have an issue with the left identity because of 0 - $a == -$a. So let's not forget to test our monoids regarding the laws to ensure that they are correct.
Two interesting monoids can be created regarding the Boolean type:
<?php
class Any extends Monoid
{
public static function id() { return false; }
public static function op($a, $b) { return $a || $b; }
}
class All extends Monoid
{
public static function id() { return true; }
public static function op($a, $b) { return $a && $b; }
}
print_r(check_monoid_laws(new Any(), true, false, true));
// Array
// (
// [left identity] => 1
// [right identity] => 1
// [associativity] => 1
// )
print_r(check_monoid_laws(new All(), true, false, true));
// Array
// (
// [left identity] => 1
// [right identity] => 1
// [associativity] => 1
// )
These two monoids allow us to verify whether at least one or all conditions are met. These are the monoidic versions of the every and some functions in the functional-php library. These two monoids serve the same purpose as the sum and product ones since PHP does not allow us to use Boolean operators as functions:
<?php
echo Any::concat([true, false, true, false]) ? 'true' : 'false';
// true
echo All::concat([true, false, true, false]) ? 'true' : 'false';
// false
They can prove useful when you need to create a series of conditions programmatically. Instead of iterating over all of them to generate results, just feed them to the Monoid. You can also write a none monoid as an exercise to see if you understood the concept well.
Using monoids
One of the most obvious ways to use our new monoids is to fold a collection of values:
<?php
$numbers = [1, 23, 45, 187, 12];
echo IntSum::concat($numbers);
// 268
$words = ['Hello ', ', ', 'my ', 'name is John.'];
echo StringConcat::concat($words);
// Hello , my name is John.
$arrays = [[1, 2, 3], ['one', 'two', 'three'], [true, false]];
print_r(ArrayMerge::concat($arrays));
// [1, 2, 3, 'one', 'two', 'three', true, false]
This property is so interesting that most functional programming languages implement the idea of a Foldable type. Such a type needs to have an associated monoid. With the help of the property we have just seen, the type can then be easily folded. However, the idea is difficult to port to PHP as we will miss the syntactic sugar needed to improve over using the concat method like we just did.
You can also use them as the callable type and pass them to higher order functions:
<?php
use function Functional\compose;
$add = new IntSum();
$times = new IntProduct();
$composed = compose($add(5), $times(2));
echo $composed(2);
// 14
Obviously, this is not limited to the compose function. You could rewrite all of the previous examples from this book that used an add function and use our new Monoid instead.
As we progress in this book, we will see more ways to use monoids associated with functional techniques that we have yet to discover.
Monads
We started learning about functors, which are a collection of values that can be mapped over. We then introduced the idea of applicative functors, which allow us to put those values in a certain context and apply functions to them while preserving the context. We also made a quick detour to talk about monoids and their properties.
With all this prior knowledge, we are finally ready to start with the idea of monads. As James Iry humorously noted in A Brief, Incomplete, and Mostly Wrong History of Programming Languages:
A monad is a monoid in the category of endofunctors, what's the problem?
This fictional quote, attributed to Philip Wadler, one of the original people involved in the Haskell specification and a proponent of the use of monads, can be found in context at http://james-iry.blogspot.com/2009/05/brief-incomplete-and-mostly-wrong.html.
Without some knowledge of category theory, it would be hard to clearly explain what the quote is all about, especially since it is fictional and voluntarily vague enough to be funny. Suffice to say that monads are akin to monoids as they share roughly the same set of laws. Also, they are directly linked to the concept of functors and applicative.
A monad, like a functor, acts as some kind of container for a value. Also, like for applicative, you can apply functions to the encapsulated values. All three patterns are a way to put some data inside a context. However, there are a few differences between the two:
· The applicative encapsulates a function. The monad, and the functor, encapsulate a value.
· The applicative uses functions that return non-lifted values. The monad uses functions that return a monad of the same type.
As functions are also valid values, this doesn't mean both are incompatible, it only means we will need to define a new API for our monad type. However, we can freely extend Applicative as it contains totally valid methods in a monadic context:
<?php
abstract class Monad extends Applicative
{
public static function return($value): Monad
{
return static::pure($value);
}
public abstract function bind(callable $f): Monad;
}
Our implementation is pretty simple. We alias pure with return as Haskell uses this term in monads so that people don't get lost. Be aware that it has nothing to do with the return keyword you are accustomed to; it's really just to put the value inside the context of the monad. We also define a new bind function that takes a callable type as parameter.
As we don't know how the internal value will be stored and because of the limitations of the PHP type system, we cannot implement neither the apply nor the bind function although they should be pretty similar:
· The apply method takes a value wrapped in the Applicative class and applies the stored function to it
· The bind method takes a function and applies it to the stored value
The difference between the two is that the bind method needs to return the value directly, whereas the apply method first wraps the value again using the pure or return functions.
As you may have come to understand, people using different languages tend to name things a bit differently. This is why you will sometimes see the bind method called chain or flatMap, depending on the implementation that you are looking at.
Monad laws
You know the drill by now; there are also some laws a monad must respect to be called a monad. The laws are the same as for a monoid-identity and associativity. So all the same useful properties of a monoid are also true for a monad.
However, as you will see, the laws we will describe seem to have nothing in common with the identity and associativity laws we've seen for monoids. This is linked to the way we defined the bind and returnfunctions. Using something called the Kleisli composition operator we can transform the laws so that they read a bit like the ones we saw before. However, this is a bit complicated and not at all useful for our purpose. If you want to read more about it, I can direct you to https://wiki.haskell.org/Monad_laws.
Left identity
return(x)->bind(f) == f(x)
The law states that, if you take a value, wrap it in the context of the monad, and bind it to f, the result has to be the same as if you call the function directly on the value. It ensures that the bind method has no side effects on the function and the value besides applying it.
This can only be true because, contrary to the apply method, the bind method does not wrap the return value of the function inside the monad again. This is the work of the function.
Right identity
m->bind(return) == m
This law states that, if you bind the returned value to a monad, you will get your monad back. It ensures that return has no effect than putting the value inside the context of the monad.
Associativity
m->bind(f)->bind(g) == m->bind((function($x) { f($x)->bind(g); })
This laws states that you can either bind the value inside the monad first to f then to g or you can bind it to the composition of the first function with the second. We need an intermediary function to simulate this like we needed one in the interchange law for applicatives.
This law allows us the same benefits as previous associative and composition laws. The form is a bit strange because the monad holds the value and not the function or operator.
Validating our monads
Let's write a function to check a monad validity:
<?php
function check_monad_laws($x, Monad $m, callable $f, callable $g)
{
return [
'left identity' => $m->return($x)->bind($f) == $f($x),
'right identity' => $m->bind([$m, 'return']) == $m,
'associativity' =>
$m->bind($f)->bind($g) == $m->bind(function($x) use($f, $g) { return $f($x)->bind($g); }),
];
}
We also need an identity monad:
class IdentityMonad extends Monad
{
private $value;
private function __construct($value)
{
$this->value = $value;
}
public static function pure($value): Applicative
{
return new static($value);
}
public function get()
{
return $this->value;
}
public function bind(callable $f): Monad
{
return $f($this->get());
}
public function apply(Applicative $a): Applicative
{
return static::pure($this->get()($a->get()));
}
}
And we can finally verify that everything holds:
<?php
print_r(check_monad_laws(
10,
IdentityMonad::return(20),
function(int $a) { return IdentityMonad::return($a + 10); },
function(int $a) { return IdentityMonad::return($a * 2); }
));
// Array
// (
// [left identity] => 1
// [right identity] => 1
// [associativity] => 1
// )
Why monads?
The first reason is a practical one. When you apply a function using an applicative, the result is automatically put inside the context of the applicative. This means that, if you have a function returning an applicative and you apply it, the result will be an applicative inside an applicative. Anyone who has seen the film Inception knows it is not always a great idea to put something, inside something, inside something.
Monads are a way to avoid this unnecessary nesting. The bind function delegates the task of encapsulating the return value to the function, meaning you will only have one level of depth.
Monads are also a way to perform flow control. As we've seen, functional programmers tend to avoid using loops or any other kind of control flow, such as the if conditions that make your code harder to reason upon. Monads are a powerful way to sequence transformation in a really expressive way while keeping your code clean.
Languages such as Haskell also have specific syntactic sugar to work with monads, such as the do notation, which makes your code even easier to read. Some people have tried implementing such a thing in PHP without much success in my opinion.
However, to truly understand the power of the monad abstraction you have to look at some specific implementations, as we will do in the next chapter. They will allow us to perform IO operation in a purely functional way, pass log messages from one function to another, and even compute random numbers with a pure function.
Another take on monads
We decided to implement our Monad class leaving both the apply and bind methods abstract. We had no other choice as the way the value is stored inside the Monad class will only be decided in the child class.
However, as we already said, The bind method is sometimes called flatMap in Scala, for example. As the name implies, this is nothing but the combination of a map and a function called flatten.
Do you get where I am going with this? Remember the issue with nested applicatives? We could add a flatten function, or join as Haskell calls it, method to our Monad class, and instead of having bind as an abstract method, we could implement it using map and our new method.
We will still have two methods to implement, but instead of both doing roughly the same job, calling a function with a value, one will continue to do that and the other one will be in charge of un-nesting the Monadinstances.
As such a function has only limited use for the outside world, I decided to go with the presented implementation. Doing it with the flatten function instead is a nice exercise that you can try to solve to get a better understanding of how monad works.
A quick monad example
Imagine that we need to read the content of a file using the read_file function and then send it to a webservice using the post function. We will create two versions, as follows, of the upload function to do just that:
· The first version will use traditional functions, returning a Boolean false in case of an error.
· The functional version will assume curryied functions returning an instance of the Either monad. We will describe this monad further in the next chapter; let's just assume it works like the Either type we already saw earlier.
In the case of success, the given callback must be called with the status code returned by the post method:
<?php
function upload(string $path, callable $f) {
$content = read_file(filename);
if($content === false) {
return false;
}
$status = post('/uploads', $content);
if($status === false) {
return $false;
}
return $f($status);
}
And now the functional version, as follows:
<?php
function upload_fp(string $path, callable $f) {
return Either::pure($path)
->bind('read_file')
->bind(post('/uploads'))
->bind($f);
}
I don't know which one you prefer, but my choice is clear. The choice of using Either instead of Maybe is also not innocent. It means the functional version can also return a detailed error message instead of just false in case of error.
Further reading
If after completing this chapter you still find yourself a bit lost, as this is such an important topic, don't hesitate to read one of the following articles or some others you found yourself:
· A small introduction to monads in PHP also with a related library at http://blog.ircmaxell.com/2013/07/taking-monads-to-oop-php.html.
· A good introduction to Scala, which anyone who has written some Java should understand, at https://medium.com/@sinisalouc/demystifying-the-monad-in-scala-cc716bb6f534.
· A video with a more mathematical approach at https://channel9.msdn.com/Shows/Going+Deep/Brian-Beckman-Dont-fear-the-Monads.
· A humorous JavaScript tutorial on monads. You either love or hate the style. If you are fluent with JavaScript, I can only recommend you read the whole book: https://drboolean.gitbooks.io/mostly-adequate-guide/content/ch9.html.
· A really complete, if somewhat difficult, introduction to monads. Some basic Haskell knowledge is needed to understand the explanations at https://wiki.haskell.org/All_About_Monads.
Summary
This chapter was certainly a mouthful, but fear not, it was the last of its kind. From now on, we will tackle more practical topics with real-life applications. Chapter 6, Real life monads will present some useful uses of the abstractions we just learned about.
Abstractions, such as functors, applicative, and monads, are the design patterns of the functional world. They are high-level abstractions that can be found in a lot of different places and you will need some time to be able to discern them. However, once you will get the feel for them, you will probably realize that they are everywhere and it will greatly help you to think in terms of manipulating data.
The laws that preside over our abstractions are really prevalent. You probably assume them already when writing code without noticing it. Being able to recognize the patterns we've learned about will bring you more confidence when doing refactoring or writing algorithms because what your instinct always suspected will be backed up by facts.
If you want to play around with this chapter's concepts, I can only recommend you start playing with the functional-php library we presented in Chapter 3, Functional basis in PHP. It contains a lot of interfaces defining various algebraic structures, the fancy name given by mathematicians to functors, monads, and such. Some of the method names will not be exactly the ones we used, but you should be well equipped to understand the idea behind them. As the library name makes it a bit hard to find, here is the link once more, https://github.com/widmogrod/php-functional.