DEV Community

loading...
Cover image for Mathematical intuition behind Applicative Functor

Mathematical intuition behind Applicative Functor

ingun37 profile image Ingun 전인건 ・4 min read

This is what I think is the best way of explaining Applicative Functor.

The objective of this post is to give anyone, who is not neccessarily mathematically trained, the mathematical intuition behind Applicative Functor.

It all begins with the simplest possible mathematical structure called Apply.

What is Apply?

You may think that you are not familiar with it but trust me, you already are an expert. apply is a binary function that takes a function f:XY f:X \rightarrow Y and a xX x \in X then apply x x to f f then return it.

apply:YX×XYapply(f,x)=f(x) \begin{aligned} &\text{apply}:Y^X \times X \rightarrow Y \newline \\ &\text{apply}(f,x) = f(x) \end{aligned}

Basically it’s the name for the notation f(x) that you have been using all the time in programming and mathematics. You probably didn’t even bother to learn it’s name because you have been taking it for granted.

Although it looks so trivial, it has rules, namely Applicative rules.

Rule 1 - identity

apply(id,x) \text{apply}(\text{id},x) must always yield x x itself where id is a function that returns the input as it is.

Alt Text

Rule 2 - composition

Follwing must hold

apply(f,apply(g,x))=apply(apply(apply(,f),g),x) \text{apply}(f, \text{apply}(g,x)) = \text{apply}( \text{apply}(\text{apply}( \cdot , f), g),x)

Alt Text

Note that apply(,f)\text{apply}( \cdot , f) results in a curried form of composition f(g)=fg \cdot_f(g) = f \cdot g .

Those seemingly trivial rules keep mathematics and programming making sense.

So what is applicative functor?

Preserving mathematical structure is a fundamental concept of mathematics. You can find it everywhere. For example, matrix preserves linearity, homomorphism preserves algebraic structure, continuous function preserves topological structure, functor preserves Categorical structure etc.

Applicative Functor preserves Applicative rules that we have just mentioned in addition to Categorical structure. In other words, Applicative functor will provide a universal construction (call it η\eta )

η:XAX \eta:X \rightarrow AX

and applyA \text{apply}_A which is the same as apply but for the types that are lifted by A.
applyA:A(X>Y)>AZ \text{apply}_A : A(X -> Y) -> AZ

and any given two composable functions f f and g g and an element x x from the function’s domain will preserve their applicative structure after they are transformed by η \eta .

applyA(Aid,Ax)=Ax \text{apply}_A ( A\text{id}, A x) = A x

Alt Text

applyA(Af,applyA(Ag,Ax))=applyA(applyA(applyA(A,Af),Ag),Ax) \text{apply}_A(Af, \text{apply}_A(Ag,Ax)) = \text{apply}_A( \text{apply}_A(\text{apply}_A( A, Af), Ag),Ax)

Alt Text

It’s all about preserving the structure.

Note that η\eta is widely known as pure or return to programmers, applyA\text{apply}_A as ap.

Applicative Functor as “Functor for binary operators”

I know many people think Applicative Functor as “Functor for binary operators”. It’s because preserving Applicative rules gives rise to preserving binary operators, and it’s very practical and ubiquitous. Let’s see how it works.
In other words, lets see how given a binary operator

+:X×YZ+:X\times Y \rightarrow Z

and an Applicative Functor AA
We can construct following new binary operator
+A:AX×AYAZ +_A:AX \times AY \rightarrow AZ

And it preserves all the original operator’s structure, e.g associativity, identity, commutativity etc.

Thinking of why Functor alone can’t do the job can gives you lots of insight through it. If you try to juggle with Functor alone to achieve the construction, you will soon realise it’s impossible. The reason is that a function as an object pops up and Functor alone is too weak to apply an object to a function as an object. Because Functor can only apply an object to a function as a morphism.

Here’s the construction.

think of + as the curried form.

:X(YZ) : X \rightarrow (Y \rightarrow Z)

then

+=η(+) +’ = \eta(+)

the new object’s type is
A(X(YZ)) A(X \rightarrow (Y \rightarrow Z))

then apply it to the curried form of applyA
+’’=applyA(+) +’’ = \text{apply}_A (+’)

the new object’s type is
AXA(YZ) AX \rightarrow A(Y \rightarrow Z)

You can see it became a function
Since it’s a function now, compose it with applyA\text{apply}_A .
+A=applyA+’’ +_A = \text{apply}_A \cdot +’’

the new function’s type is

+A:AXAYAZ +_A : AX \rightarrow AY \rightarrow AZ

Boom! construction is done.

Conclusion

Applicative functor is nothing but a preservation of one of the easiest mathematical structure apply. There’s nothing to overthink about it.

Discussion

pic
Editor guide