To Functor, or not to Functor?

“Pluralitas non est ponenda sine neccesitate”
(“Never increase, beyond what is necessary, the number of entities required to explain anything”)
Occam’s Razor, William of Ockham (1285–1349)

On Functors, Monads, Nomads and Gonads

It is remarkable how some (highly) abstract mathematics is making its way into “more real” worlds like Functional Programming. The wonderfully entertaining A Brief, Incomplete, and Mostly Wrong History of Programming Languages describes how the famous argument that

Monad is just a Monoid in the category of Endofunctors, what’s the problem?

apparently did not impress the audience. Neither did the

“Curse of Monads: When you finally understand it, you’ll lose the ability to explain it to others,”

attributed to Douglas Crockford. Monads become marvellously mysterious, function composition on steroids, receive “maybe gentle intros” and enjoy “tutorial fallacy” as excellently unpuzzled in that article. Most notably how a “Joe Haskeller” confuses understanding for metaphor and “goes writing tutorials hiding the scary stuff” which actually “makes harder for people to learn”. But does it have to be that way?

If you have tried to understand Monads, Functors or other beasts (or friends?) but feel confused, most likely it is not your fault!

Perhaps a confusing explanation by a “Joe Haskeller”? Approach from a too abstract angle before going through simple useful examples? These concepts are not intrinsically hard. But they can easily be made confusing, unfortunately.

How to recognise a Quality Explanation?

Here are some red flags to look for in any explanation or tutorial:

  • Lack of examples.
  • Lack of simple examples like ones without details not relevant to the point. Ideally every single detail must be relevant or left out, see the Occam’s Razor quote above.
  • Lack of interesting examples related to the real world use.
  • Lack to link examples with abstractions. No, it is not enough to simply end with yet more examples and leave it at that. A good explanation must show how all the examples given fit in the abstract concepts.

And the final red flag is very important but so often neglected:

Lack of non-examples. Yes, not everything is nail when you hold a hammer! Show the limitations of the abstractions. Give the simplest yet relevant and useful examples that do not fit into the abstraction, that I call the “non-examples”.

Speaking of which, the subject of this post is:

What is not a Functor aka Functor non-examples

UPDATE. This was aimed for readers who had already read about Functors elsewhere. To cover this gap and make it more accessible to others, here is a quick introduction to Functors and their use in programming.

A Functor is NOT an object implementing a “map” method

The array [1,2] implements map. Does it make it a functor? You can compose functors but how are you going to compose [1,2]? With what?

How about [0]? It also has map. Is this another functor? Or the same?

So no, a specific array like [1,2] is not a functor. At least not in any useful way that you expect. It is an element of the set [number] consisting of all arrays of numbers. And that set [number] itself is what the Array Functor F returns when applied to the set number of numbers:

F(set of numbers) = set of arrays of numbers
F(set of characters) = set of arrays of characters
F(set of anything) = set of arrays of that anything
F: a -> [a], where a is any set of values (aka type)

And now you can define the map method transforming (aka “lifting”) a function between sets of things to another function between the arrays by applying it to each thing:

map(f) is new function sending [1,2,3] into [f(1),f(2),f(3)]

A common confusion — what is f?

It is sadly common to use the same letter f for both functions and Functors next to each other, e.g. in Haskell you see

class Functor f where
fmap :: (a -> b) -> f a -> f b
fmap (f . g)  ==  fmap f . fmap g

But there are two different f here! Can you see them?

The f a in the first line is the new type F(a) (as we write here), whereas the f in the second line is any function a -> b.

It goes without saying that a text is always more clear to your readers, when different things are called differently.


The boring definition interlude

So a Functor F (from the category of sets into that same category of sets) consists of two things:

  • A rule to assign new set F(a) to every set a .
  • A rule (often called map in programming) to assign to any function f between any two sets a and b a new function map(f) between the two sets F(a) and F(b) returned by the Functor.
  • Two laws must be satisfied: The “lifting” map should lift the identity to identity, and the composition of two functions f and g, that can be composed, to the composition of the two separate lifts map(f) and map(g). Here two functions can be composed means the target set of the interior function must match the source of the exterior.

Ok, that was “only” a Functor from the set category to itself. But it is worth to understand that case first. Then the pass to the more abstract Functor between two general categories isn’t that far.

At least, this is what Functor means in maths, where it comes from. You might like to stretch the language and call other things (like Burrito) a functor, but be aware you are doing that. And let your reader be aware of it too. Even better, explain the difference. That will raise the quality bar of your blog and help the reader, who is less familiar, avoid unnecessary confusion and appreciate your article even more.


Back to business…

Functor non-examples with arrays

  • How about trying to apply a function f only to the last array entry:
[1, 2, 3].map(f) = [1, 2, f(3)]

On the surface, both Functor laws apply! The identity f is lifted to the identity map(f) and composition to composition. Yet it is not a functor.

The problem arises when f changes the type. Like isEven(x) that returns boolean. We would get

[1, 2, 3].map(isEven) = [1, 2, false]

that is no more array of booleans. That is, we won’t get

map(isEven): [integer] -> [boolean] 

as would be required from a Functor.

  • How about applying map(f) only to the first array entry and forgetting the rest:
[1, 2, 3].map(f) = [f(1)]

Now with f = isEven, our map(isEven) will send array of integers into array of booleans as desired. And it will even lift compositions to compositions as in the second law.

But we run into problem with the first law saying that the identity should be lifted to the identity:

[1, 2, 3].map(id) = [1] 
vs [1, 2, 3] that we need to be returned by the identity

So again, not a functor.

A Functor is NOT “simply a container”

A container needs to hold something. One thing or several? If the array [1,2,3] were “simply a container” holding 1,2,3, why is it different from the array [3,2,1] holding exactly the same things?

So no, it is more than that. Some additional structure is needed. Like assigning places to each elements. Or a graph or tree would need to specify all the edges between the elements, in additional to “simply holding” them.

Having said that, simply wrapping anything into container is an important and useful example of a functor. Which can well provide some intuition. But it an example! And examples are useful but can also deceive into wrong intuition. Like something only specific to an example that can be confused for a general feature. For instance, that mentioned example is known as the so-called Identity Functor. Which is a boring thing in maths but more useful in programming. In JavaScript, the wrapper map

Identity = x => ({
map: f => Identity(f(x))
})

is actually NOT the Identity Functor. It is actually a thing in addition to the Functor, making the Identity the so-called Pointed Functor. Which is very useful, as it lets us write

Identity(x).map(f).map(g).map(h)

instead of

h(g(f(x)))

And does provide some intuition. But it is still an example.

The functor “map” does NOT “simply run the function over all values (or elements)”

Sometimes, it is only some of the values. The classic example is the Pair Functor:

To every type (set of values) a , it associates the set of Pairs (x, y) where y is of type a, and x is anything. (Note here how don’t associate anything to the individual values, only to their sets.)

Now define the lift map(f) by only applying f to the second entry:

(x, y).map(f) = (x, f(y))

Yes — the function f only applies to the second argument, this is not a typo! So no, the functor map does not always run over all values inside the container.

That looks weird first, but becomes less “unnatural” when comparing to the JavaScript comma operator that always picks the second entry:

const result = (x = 2, x * x) //=> 4

And we get map(f) going from F(a) to F(b) whenever f: a -> b , as required from a Functor. Because this time, the type of the first entry does not matter!

Both laws apply too and we get a Functor. Note how it is similar to the above Array non-example, where the map looks exactly the same. The main difference here is in F(a), the associated set of values provided by the Functor. In the array case, we consider arrays with all entries of typea , in the case of pairs only the second entry is of type a. Thus, in the array case, the same map does not return a correct type.

Some further reading on Pairs for JavaScript lovers: http://www.tomharding.me/2017/04/27/pairs-as-functors/

Many ways to skin a cat, sorry, a Functor

As we have just seen with arrays, there may be several legal ways to define the map. If you were not impressed by that example, think of some fancy graphs or trees, where there different rules how to apply you function to different values.

Conclusion

I hope this tiny non-exhaustive excursion into the Functor non-examples helped to dispel some myths aka confusions about Functors. And if not, don’t give up. Find the best explanation for your taste. The one that with similar goals. A mathematically rigorous introduction may not be the same as the one explaining how the things are “useful”. With the latter being subjective.

And finally, dear author, please don’t hide the “scary details” from your readers. Not everyone needs everything completely, strictly and mathematically defined. What your reader will appreciate, however, is to be told where is a metaphor, where is an example, where is a simplification, and where is the real thing.

PS. Critics, corrections, objections, improvements and even disprovements are welcome :)