Futures & Monoids

In the post From Callback to Future -> Functor -> Monad we clearly saw how Futures/Promises map to some well known constructs from FP and category theory.

First we saw that Futures are Functors, because they are able to take a function and apply it to their eventual outcome. Next we saw that they are also Monads because they are able to describe a computation as a sequence of steps through mapping a Monadic function (i.e. a function that returns itself a Monad (=Future)) then flattening the result to get the final result.

In this post w’ll meet another less famous construct from category theory. We will see what it represents and how it can be useful.

Another view of Parallelism

Remember the following use case from the first Post ?

suppose we are trying to fetch some content from some web URL that can be sometimes unavailable, upon a failure of our request, we’ll try an alternative URL, we can use ‘flatMapError’ to catch the first failure and return the alternative request

resultF = requestF('/url1').flatMapError( err => requestF('/url2') )

First we request the ‘main’ server and, upon failure, we request the alternative one. The example above can be rewritten with Promises

resultP = requestP(‘/url1’).catch( err => requestP(‘/url2’) )

Both examples illustrate well the sequential nature of Monads. Things has to be done one after one. But you may notice that there is a better way to solve the above use case. We don’t have to wait for the first request to fail in order to try the alternative url, we can send the 2 requests in parallel and just pick the first incoming response, the faster wins.

But how do we express this parallelism in Futures? we already saw that lifted functions which take multiple arguments can be used to describe parallel operations. But clearly this is not the kind of parallelism we want, so what’s the other kind ?

Lifting revisited

let’s quickly review the concept of lifting. We saw that the ‘lift’ function

1. takes a function that operates on non future values and
2. returns another function that applies the same transformation to future values.

// String -> Number (non lifted version)
function length(str) { 
  return str.length;
}
//Future String -> Future Number (lifted version)
lengthF = lift(length)

We also saw that a lifted function that takes multiple Futures has to wait for all of them to complete before applying the underlying function.

Suppose now we want to lift the following function

// [a] -> [a]
function multi_id(...args) {
  return args;
}

the function acts like an identity function but with multiple arguments, the return value is as an array of the passed inputs. Lifted to Futures, it’ll return a Future holding a list of all completion values from the input Futures.

[Future a] -> Future [a]
multi_idF = lift(multi_id)

For promises, the lifted multi-id function is called ‘Promise.all(iterable)’ which “returns a promise that resolves when all of the promises in the passed in ‘iterable’ argument have resolved”. As you can see, ‘Promise.all’ is just the special case of lifting the multi-Identity function.

Now, let’s imagine the above function in terms of the logical ‘and’ (‘&&’) operator, in a sens that the ‘completed’ property of the output future is a logical and (‘&&’) applied to the ‘completed’ property of all given futures

all(fut0, fut1, ..., futN) = fut0 && fut1 && ... && futN

Viewed from this perspective, what’s the meaning of the logical ‘or’ (‘||’) operation applied on futures?

In an ‘and’ operation, we examine all the terms of the expression so the evaluation wont stop until the last term. Similarly in futures, the evaluation wait for the last completed future and returns all the futures.

Let’s transpose the same reasoning to ‘or’. In an ‘or’ operation, we stop the evaluation when we encounter the first ‘true’ term. So similarly for futures, an ‘or’ operation stops on the first completed future.

Below how we may implement this operation for 2 futures

Future.prototype.or = function(fut2) { 
  const resultF = new Future();
  this.ready(tryComplete); 
  fut2.ready(tryComplete);
  return resultF;
  function tryComplete(fut) {
    if(!resultF.completed) 
      resultF.complete(val);
  }
}

As we are only interested in the winner future, we only complete the future if it has not been already completed.

Back to our previous example, we can now express our parallelism

resultF = requestF(‘/url1’).or( _ => requestF(‘/url2’) )

We can easily extend the ‘or’ function to multiples arguments using the ‘forEach’ method. In this case, w’ll be defining (something similar) another operation that also exists in promises, ‘Promise.race(iterable)’ which “returns a promise that resolves or rejects as soon as one of the promises in the iterable resolves or rejects”.

Actually this a not quite the same, Promise.race will return as soon as a promise in the iterable rejects while in our example we have to wait for the **latest promise that resolves successfully**.

Category Theory, again

I’ll now introduce our 3rd guest from the Category theory land. Besides been a Functor and a Monad, a Future is also a Monoid.

The most intuitive (although restrictive) way of thinking of Monoids is that they are additives. Take the analogy with the ‘or’ operation, you can start with an expression ‘a or b’, the terms of expressions are booleans, and so the result. Add another term to the expression ‘a or b or c’, the result is still a boolean. Repeat the process above with numbers and you’ll get the same result. Monoids are just simple as that (yet a very useful abstraction).

The fact that the ‘or’ operation on booleans returns always a boolean (just as the ‘+’ operation on numbers always returns a number) leads us to refine the definition : Monoids needs an *additive* operation that doesn’t fall outside; take for example the ‘+’ operator applied only to the range [1..12]. The range [1..12] along with the ‘+’ operation is not a Monoid because ‘11+10’ is not contained within the range. But the same range with the operation ‘(x+y) modulo 12’ (more accurately 13) forms a Monoid because whenever we jump by the given operation we don’t fall outside the range. This property is called closure. Of course Futures under the ‘race’/’or’ operation verify this as the result is always a Future.

A Monoid need also something else, called the identity element. Which is a value that is always neutral with respect to the additive operation. For the example of numbers under the ‘+’ operation, the identity element is zero ‘0’. With respect to the multiplication ‘x’ it is ‘1’. In the case of booleans under the ‘or’ operation it is the ‘false’ constant because ‘false or x’ will always yield ‘x’.

So what’s the identity element for Futures? The element has to be neutral with respect to the ‘or’/’race’ operation, i.e.

future.or(identF) == identF.or(future) == future

We need a future with the latest time of completion we can imagine, i.e. where ‘completion time == Infinity’. In other words, the identity element for Futures is the never ending future.

Future.never = new Future();

Additive yes, but in what order?

In fact, we have to add another requirement, the additive operation has to be associative. Meaning “the order in which the operations are performed does not matter as long as the sequence of the operands is not changed”(1). I m pretty sure you’ve already encountred associativity in your Math School,

a + (b + c) = (a + b) + c

For Futures it means

fut1 or (fut2 or fut3) = (fut1 or fut2) or fut3

It’s not difficult to verify that the above property holds for futures. If you want to go for a formal proof, you can use a pair ‘(value, time)’ to denote the meaning of futures; and define the ‘or’ operation as

(v1, t1) or (v2, t2) = (vk, tk) such as tk = min(t1, t2)

I will not list the detailed proof here (I’m not that strong on Math :) ). Just note that the associativity of futures under ‘or’ results from the associativity of numbers under the ‘min’ operation

min(t1, min(t2, t3)) == min(min(t1, t2), t3)

In terms of promises, it means the 3 expressions below are equivalent

Promise.race([p1, p2, p3])
Promise.race([p1, Promise.race([p2, p3]))
Promise.race([Promise.race([p1, p2]), p3]))

So to resume, a Monoid can be described with a pair (M, op) with the following properties.

• x ‘op’ y = z with the requirement that x, y, z are members of M (op is known as ‘append’ or ‘mappend’)
• Existence of an identity element ‘id’ such as ‘x op id = id op x = x’ for all x in M (sometimes called also ‘empty’ or ‘mempty’)
• Associativity. (x op y) op z = x op (y op z) for all x, y, z in M

Monoidal reduction

You should be already familiar with the ‘Array.reduce’ operation. The function reduces (or folds) an array into a single value, by successively applying a binary operation to all the elements of the array. Here is the well known example of summing numbers in an array using ‘0’ as a seed.

function sum(array) { 
  return array.reduce( (acc, n) => acc + n, 0)
}

we know that numbers form a Monoid under the ‘+’ operation. Doesn’t this give you some ideas?

If we abstract away the specific ‘number’ and ‘+’ and replace them with the more generic ‘Monoid’ and ‘append’ (additive operation) then we can normalize the ‘reduce’ operation to be working with any Monoid instance.

function sumM(array) {
  return array.reduce( (acc, m) => acc.append(m), identity)
}

Since Futures are Monoids themselves we can write the multi-argument Promise.race in terms of monoidal reduction

Future.or = function(…args) {
  return args.reduce( (acc, fut) => acc.or(fut), Future.never )
}

The ‘array.reduce’ method expects only a binary operation and optionally a seed value. But with Monoids we have additional information, we know that the binary operation is associative and that the identity element is neutral in respect to that operation.

The advantage of using Monoids is a more generic and predictable code. Using an explicit interface along with well defined properties conveys better meaning to the code, make the code more flexible and maintenable.

Uses of Monoids

Example: the Writer Monad

A typical example of Monoids is often illustrated with the Writer Monad. As for other Monads, it’s best understood through a use case : Suppose we have defined a pipeline of transformations by sequencing a set of functions, for example

function increment(num) { return num + 1;   }
function square   (num) { return num * num; }
function modulo10 (num) { return num % 10;  }
result = modulo10( square( increment(...) ) )

Now in order to see what’s going on inside this pipeline, we can run the example through a debugger, but sometimes this is not possible. In this case the usual solution is to log messages into the console or any other output.

The Writer Monad solves the problem by embedding the log messages directly into the intermediate and the final results. In the above example the type of the of the manipulated value is a Number. the Writer Monad will wrap the number value, say, into a pair (String, Number) where String is the type of the log messages and Number is the domain type manipulated by the functions.

function WriterStr(log, val) {
  this.log = log;
  this.val = val;
}
WriterStr.prototype.bind = function (fn) {
  var w = fn(this.val);
  return new WriterStr(this.log + ‘\n’ + w.log, w.val);
}
WriterStr.unit(val) {
  return new WriterStr(“”, val);
}

WriterStr requires the 2 operations requierd in Monads

• ‘unit’: simply wraps the value by adding an empty log message
• ‘bind’ : chains the successive computations by accumulating the log messages from each step into the running log.

In order to integrate our previous pipeline we have to change the normal functions into monadic ones. i.e. make them returning WriterStr instances instead of plain numbers

function increment(num) { 
 return new WriterStr(“adding 1 to “ + num, num + 1); 
}
function square(num) { 
 return new WriterStr(“squaring “ + num, num * num); 
}
function modulo10(num) {
 return new WriterStr(“applying modulo 10 to “ + num, num % 10); 
}
var result = increment(5).bind( val => 
               square(val).bind( val => 
                 modulo10(val)))
//result: 
{
  "log":"adding 1 to 5\nsquaring 6\napplying modulo 10 to 36",
  "val":6
}

The final result is a pair (log, val) where val is the final result of the computation while log, its side effect, is a description of all steps involved in the computation.

Now note how the Writer ‘unit’ lifts a normal value by joining an empty string to it, and how ‘bind’ applies the string concatenation on each step. As you may have already noted, String with the concatenation operation is a Monoid where the identity element is the empty string.

String.prototype.append = String.prototype.concat
String.identity = ""

So the Writer Monad can in fact work with any Monoid not just strings

function Writer(append, identity) {
  function W(log, val) {
    this.log = log;
    this.val = val;
  }
 
  W.unit = function(val) {
    return new W(identity, val);
  }
 
  W.prototype.bind = function(fn) {
    var w = fn(this.val);
    return new W(append.call(this.log, w.log), w.val);
  }
 
  return W;
}
var WriterList = Writer(Array.prototype.concat, []);

and now the monadic functions has to return log messages as arrays to match the expected type for WriterList

function increment(num) { 
  return new WriterList([“adding 1 to “+num], num + 1); 
}
...

Other examples

This link gives an interesting use of Monoids: exploit the generality of the Monoid interface and 2–3 finger trees to define a general purpose tree structure. The tree can then be reused to implement multiples data structures (lists, priority queues) by just modifying the underlying Monoid interface.

Conclusion

Monoids are simple structures that can be found easily everywhere : numbers, strings, lists and futures/promises are just some examples.

Their main advantage is to provide a more abstract way to factor operations that follow a pattern of appending starting from an ‘empty’ element. If you search through your source code there is a great chance you’ll find this pattern.

Below some links if you’re willing to learn more about Monoids (if you don’t mind reading Haskell code)

• Monoid chapter from Haskell wikibook
• Monoids and Finger Trees (example cited above)
• sigfpe article with many examples of Monoid uses
• Monoids definition in fantasy-land (a specification of common Alegbraic Structures in JavaScript)
• Brian Beckman: Don’t fear the Monad, talk about Monads that explains Monoids with an accessible language