Higher Kinds in C# with language-ext [Part 4 - applicatives]
This is a multi-part series of articles, it's worth going back to the earlier parts if you haven't read them already:
Since the last article I've released an early alpha of language-ext. The alpha contains all of the trait-types in this series – so if you feel like 'skipping ahead' then feel free to have a look. Just remember that it's not ready for production yet!
Anyway, let's now look at the next trait-type: ‘Applicatives’. Or, to give them their full name: Applicative Functors.
Applicative Functors are a 'stepping stone' between functors and monads – they're probably less well-known but have some interesting properties of their own when it comes to lifted expression evaluation. Two of the major uses in language-ext is to enable automatic parallel processing of effectful computations and to automatically collect multiple errors when validating. Those aren't the only usages – all of the higher-kinded-types, including the collection-types, have the applicative traits.
If we take a look back at Functor, it has a single method in its trait: Map
. Map
takes a regular function Func<A, B>
and allows it to run on the bound-values within the functor, effectively making a Func<A, B>
into a Func<F<A>, F<B>>
.
For example, if I have an A
then a Func<A, B>
will get me a B
. This is basic stuff. But, if I have one or more A
values within an F<A>
, I want to be able to apply the Func<A, B>
to the bound values to transform them: that's what Map
does. It means that every function that's ever been written to work with single values of A
can now work with any type that is a 'container' of zero or more values of A
.
So, forList<A>
we get to turn it into aList<B>
by applyingFunc<A, B>
withMap
.
The function passed to map has a single argument - it's a unary operation. So, simple operations like this are easily achievable:
// Simple unary function
static bool Not(bool x) =>
!x;
// Mapping of a list of booleans
var xs = new List<bool>([true, false, true]);
var ys = xs.Map(Not);
// Mapping a boolean Maybe
var mx = new Just<bool>(true);
var my = mx.Map(Not);
What happens if we want to do a binary operation? How would we achieve that?
Let's take a look at a simple mathematical expression:
1 × 2 + 3 × 4
What if the operands weren't just pure values, but were instead lifted up into a Maybe
?
Just(1) * Just(2) + Just(3) * Just(4)
Could we still operate on those values without losing the semantics of the Maybe
structure – namely that the values are optional?
If the values were int?
then we may write some code like this:
int? w = ...;
int? x = ...;
int? y = ...;
int? z = ...;
if(w.HasValue &&
x.HasValue &&
y.HasValue &&
z.HasValue)
{
return w.Value * x.Value + y.Value * z.Value;
}
else
{
return null;
}
Plenty of boilerplate and plenty of opportunities to make a mistake.
WARNING: This next section is becomes a bit of a mindfuck before it gets good. Stick with it!
With Maybe<int>
what could we do? So far, we've only got support for Map
and Fold
behaviours. Map
takes unary function arguments, but we have binary functions (+
and ×
), how can we make them unary? Simply, we can curry them:
// Binary addition function
static int Add(int x, int y) =>
x + y;
// Binary multiplication function
static int Multiply(int x, int y) =>
x * y;
// Curry the functions
var add = curry<int, int, int>(Add); // (int x) => (int y) => x + y
var multiply = curry<int, int, int>(Multiply); // (int x) => (int y) => x * y
Currying creates a series of nested lambdas rather than a single 'tuple' lambda. This allows us to partially apply our arguments to the functions.
var add10 = add(10); // Func<int, int>
var result = add10(20); // 30
Partial application allows us to progressively feed values into the function without the need to collect all of the argument the values upfront.
Let's now create the four terms of our expression:
var mw = new Just<int>(1);
var mx = new Just<int>(2);
var my = new Just<int>(3);
var mz = new Just<int>(4);
And then start multiplying with Map
:
K<Maybe, Func<int, int>> r1 = mw.Map(multiply);
What we end up here is the value inside mw
being partially applied to the multiply
function – it returns a function that gets wrapped back up inside a Maybe<Func<int, int>>
– if we can just supply one more argument then we have the first multiplication expression done:
var r2 = r1.Map(f => mx.Map(f)); // K<Maybe, K<Maybe, int>>
So, we call Map
on r1
(which has a Func<int, int>
inside), we then pass that to mx.Map
– which completes the multiplication operation.
But, we have problem! We want our Map
operation to be int → int
, we were not expecting another Maybe<int>
to be returned. However, because of our nesting of Map
operations we cause the final r2
result to be two nested maybes. This isn't good!
If we take it further and try to do the full expression: 1 x 2 + 3 x 4
then it gets worse!
var lhs = mw.Map(multiply).Map(f => mx.Map(f));
var rhs = my.Map(multiply).Map(f => mz.Map(f));
var res = lhs.Map(l => l.Map(add).Map(f => rhs.Map(r => r.Map(f))));
Would you like to guess what res
is? You got it:
K<Maybe, K<Maybe, K<Maybe, K<Maybe, int>>>> res; // Ouch!
Four nested maybes! So, not only do we not have the result we want, it's truly horrible to write. We need a better solution, we need applicative functors!
public interface Applicative<F> : Functor<F>
where F : Applicative<F>
{
public static abstract K<F, A> Pure<A>(A value);
public static abstract K<F, B> Apply<A, B>(K<F, Func<A, B>> mf, K<F, A> ma);
}
Take a look at the Apply
function signature. Does is remind you of anything? Let's take a look at Functor
again:
public interface Functor<F>
where F : Functor<F>
{
public static abstract K<F, B> Map<A, B>(Func<A, B> f, K<F, A> ma);
}
By the way, I am now using the definition from language-ext, whereK<F, A>
is the last argument in the argument-list forMap
.
Both Map
and Apply
look almost exactly the same. The only difference is that the Func<A, B>
is also lifted in the applicative Apply
function (i.e. it's wrapped up in a K<F, ...>
).
But, if you look at the, earlier, first step of trying to partially-apply the mulitply
function:
K<Maybe, Func<int, int>> r1 = mw.Map(multiply);
Then you'll notice that it too is a Func
that is lifted into the Maybe
structure. Looks like we might be on something here!
Let's implement Applicative
for Maybe
:
public class Maybe :
Foldable<Maybe>,
Applicative<Maybe>
{
public static K<Maybe, A> Pure<A>(A value) =>
new Just<A>(value);
public static K<Maybe, B> Apply<A, B>(K<Maybe, Func<A, B>> mf, K<Maybe, A> ma) =>
mf switch
{
Just<Func<A, B>> (var f) =>
ma switch
{
Just<A>(var a) =>
new Just<B>(f(a)),
Nothing<A> =>
new Nothing<B>()
},
Nothing<Func<A, B>> =>
new Nothing<B>()
};
public static K<Maybe, B> Map<A, B>(Func<A, B> f, K<Maybe, A> ma) =>
ma switch
{
Just<A> (var x) => new Just<B>(f(x)),
Nothing<A> => new Nothing<B>()
};
public static S FoldWhile<A, S>(
Func<A, Func<S, S>> f,
Func<(S State, A Value), bool> predicate,
S state,
K<Maybe, A> ta) =>
ta switch
{
Just<A> (var x) when predicate((state, x)) => f(x)(state),
_ => state
};
public static S FoldBackWhile<A, S>(
Func<S, Func<A, S>> f,
Func<(S State, A Value), bool> predicate,
S state,
K<Maybe, A> ta) =>
Fold(s => a => f(a)(s), state, ta);
}
I have implemented the traits as they exist in language-ext. So, you'll notice the new implementation ofMap
reflects the interface in language-ext, rather than the implementations from the earlier articles. Additionally, you should see thatFold
andFoldBack
are nowFoldWhile
andFoldWhileBack
– these are the actual abstract methods used in the language-ext interface: it allows for more optimal default implementations of the other trait methods, likeExists
,ForAll
,IsEmpty
, etc.
Let's look at the implementation of Apply
:
public static K<Maybe, B> Apply<A, B>(K<Maybe, Func<A, B>> mf, K<Maybe, A> ma) =>
mf switch
{
Just<Func<A, B>> (var f) =>
ma switch
{
Just<A>(var a) =>
new Just<B>(f(a)),
Nothing<A> =>
new Nothing<B>()
},
Nothing<Func<A, B>> =>
new Nothing<B>()
};
It's a simple nested pattern-match that tries to extract the Func<A, B>
from mf
and the A
from ma
. If either of them are in a Nothing
state then we get Nothing
returned. Which makes sense – we can't invoke the function if we don't have the function or if we don't have the argument to pass to the function.
But, if both mf
and ma
are in a Just
state then we can simply invoke the function and then wrap it back up inside a Maybe
by passing the result to the constructor for Just
.
Let's update our extension methods to allow us to use the new applicative Apply
method. We'll also add a new Map
extension with the arguments flipped (I mentioned in an earlier episode that I would demonstrate why the arguments are flipped – you're about to see why it works this way):
// Functor map (notice that `this` is a `Func`)
public static K<F, B> Map<F, A, B>(this Func<A, B> f, K<F, A> ma)
where F : Functor<F> =>
F.Map<A, B>(f, ma);
// Applicative apply
public static K<F, B> Apply<F, A, B>(this K<F, Func<A, B>> mf, K<F, A> ma)
where F : Applicative<F> =>
F.Apply<A, B>(mf, ma);
If you remember our first attempt at multiplying two Maybe<int>
values together looked like this:
var r = mw.Map(multiply).Map(f => mx.Map(f));
And that resulted in a nested Maybe<Maybe<int>>
. Instead, we can now use the Apply
function (along with the flipped-argument Map
) to avoid the nesting:
var r = multiply.Map(mw).Apply(mx) // K<Maybe, int>
And that works! Returning a K<Maybe, int>
rather than the double-nested maybe we saw earlier. The flipped-argument Map
function also allows us to move the function-argument to the left-most position in the expression, it is then followed by n
arguments that are fluently fed into the function. This just reads better.
For those that know Haskell, you'll recognise this technique. In Haskell it would look like this:
let r = multiply <$> mw <*> mx
I would love to be able to use operators to make this a little more elegant in C#, but operators can't be parametrically polymorphic and so the only way is to use this fluent style.
If you have functions with even more arguments then you can simply chain more calls to Apply
and it will just work.
Now lets do the applicative-version of the imperative nullable-expression from earlier:
var lhs = multiply.Map(mw).Apply(mx);
var rhs = multiply.Map(my).Apply(mz);
var res = add.Map(lhs).Apply(rhs);
It is more concise than the imperative version, it's less error prone, and it supports every single applicative type ever written. So, we can run this with Either
, Option
, Seq
, etc.
It's not quite as easy to read which is definitely the downside to using applicatives in C#. Most applicatives are also monads and monads (in C#) are 'LINQ friendly'. Which means we could have just written:
var res = from w in mw
from x in mx
from y in my
from z in mz
select w * x + y * z;
It's probably easier to read and doesn't need any special currying of functions. So, what is it that applicatives have over monads? Namely, monads are about sequential operations – we can only get each operand of the final expression in-sequence, first the w
, then the x
, then the y
, then the z
, then we return the result (if all succeeded). If any fail we return immediately and don't process the rest.
Applicatives however do not have sequential processing semantics. In fact, they're the opposite.
Let's take a look at the earlier mathematical expression in tree form. We can see that there are two main branches that are entirely independent of each other. We could calculate the left-hand-side in-parallel to the processing of the right-hand-side before applying the values to the addition function.
Because applicatives get access to both their function and its argument at the same time, they're able to follow a strategy where the operands are calculated independently.
You can see this in the Apply
implementation for IO effect type:
public static IO<B> Apply<A, B>(this IO<Func<A, B>> ff, IO<A> fa) =>
from tf in ff.Fork()
from ta in fa.Fork()
from f in tf.Await
from a in ta.Await
select f(a);
Notice how it forks both the function IO and the argument IO. That means they can run in parallel whilst further down the expression awaits both IO operations to complete. If you use functions with more arguments (and therefore chain more Apply
calls) then each argument runs in parallel and the final function invocation only occurs when all arguments have been acquired.
And so, applicatives enable automatic parallelisation of effectful computations. No need to manually write code to do threaded coordination.
Here's a simple example. Let's first get three asynchronous IO operations:
var io1 = liftIO(() => File.ReadAllTextAsync(path1));
var io2 = liftIO(() => File.ReadAllTextAsync(path2));
var io3 = liftIO(() => File.ReadAllTextAsync(path3));
And some function that wants to use the result of those operations:
var concat = (string txt1, string txt2, string txt3) =>
txt1 + txt2 + txt3;
Next we map and apply the IO computations. These three IO operations will now all run in parallel and collect their results before invoking the concat
function.
IO<string> res = concat.Map(io1).Apply(io2).Apply(io3);
You might be thinking "but, you didn't curry theconcat
function first!". You're right, because language-ext hasMap
andApply
overrides that will deal with that automatically for multi-argument delegates. The overrides simply curry the function for you before invoking the regularMap
andApply
methods.
Another thing to note with the above expression is that Map
is called on the function – and so it doesn't get forked; only io1
, io2
, and io3
get forked. That means we're not launching pointless parallel processes to acquire the function (which would normally be available already).
Applicatives are a little hard to get your head around at first – but they are incredibly powerful. Even if you don't need the more 'hierarchal' behaviour (as opposed to the sequential behaviour of monads) they can – in the right circumstance – be very concise and elegant. However, in C# it isn't always the case, so it's best to pick your battles and use them when you need their unique capabilities or when the resulting code will be more elegant.
This article is a little long now – I still haven't explained the Pure
method in Applicative
and I wanted to cover how applicatives can be used for validation – but I think I'll dedicate a separate article to that so I can give some more real-world examples.