Functors from first principle - explained with JS

In this post, I will explain what functors are and why they are useful in a different way than I was taught.
When I tried to learn about the functors concept I usually got to one of those explanations:

• It is something you can map over (But what exactly does map means?)
• It's like lists that you can map over (So, is mapping just looping through elements?)

Those weren't very useful for me. And I ended up reading very very long explanations, and reading many lines of real world code to get all the gotchas and the real meaning.
I will try to spare you, by explaining as fast as possible the concepts.

I will start with the general concept and some demos in JavaScript to make is accessible as possible, but I will end up going to Haskell here as there are things only Haskell can do that are important for your understanding.

Lists are functors - as you can map over them

Let's start with an anecdotal example and expand from there.
Lists as you know them from many languages are functors, as you can map over them.

const myList = [1,2,3,4,5]
const addTwo = (num) => num + 2
myList.map(addTwo) // [3,4,5,6,7]

Map is applying a function to a structure

So what we saw above, is basic map function for a list where we apply the addTwo function to every item in the list.
But mapping a bit more generic definitions is:

Applying a function over *or* around some structure while keeping the structure intact.

In lists, the structure is the list itself. We apply a function, addTwo, that has no otherwise knowledge of the existence of lists, over every item in the structure, the list.

Got it. Mapping over structure. What are structures?

It is a bit hard to grasp the concept of structures as first, when you only have the list example.
But this is where the important generic concept of functors come in play.
Think of the "structure" at play as a box, holding some kind of value in it. When mapping, you apply a function to a potential value within that box, while leaving the box intact.

Keeping us in the realms of javascript, a non-perfect, but still good enough example will be promises.
Promises are boxes that hold potential values, which you can apply a function over without changing the promise box.

let promise1 = new Promise(function(resolve, reject) {
  setTimeout(function() {
    resolve('foo');
  }, 300);
});

// `then` is the equivalent of `map` in our example.
promise1.then(console.log);

console.log(promise1); // Will print out [object Promise]

What happened here?
We have a Promise object, which is a box holding in future evaluation of value.
The then method applies a function to the value within that structure of promise, while leaving the promise object itself intact.
The then method is equivalent to map in our world.

Ok. Got it. But that looks pretty thin, what more is it useful for?

I'm with you. You need more examples to explain the value in this abstraction before we move on.
This is where I need to get out of the classic JS realm a bit, but not too far.
Let's introduce the Maybe Monad. Don't worry, the monad part have nothing to do with our explanation. Just the maybe part.

Maybe monads are a method to handle values that may or may not exists in a safe manner. Instead of having null or undefined values, you'll have Maybe handle the Nothing case gracefully, leveraging the functors methodology.

Basically, Maybe is a box for values that are optional. Let's assume we have an implementation, this is how it might look:

let maybeName1 = Maybe("Snir")
let maybeName2 = Maybe(undefined)

console.log(maybeName1)
// [status: "Just", value: "Snir"]

console.log(maybeName2)
// [status: "Nothing"]

Now, this Maybe structure is a box, that implements a map function, to be a functor! Let's look at a potential map implementation:

// (This is not how `this` really works, assume `this` here is the
// currently referred Maybe object itself. Just for ease of read)
Maybe.map = (fun) => {
  if (this.status === "Nothing") {
    return;
  }
  return fun(this.value)
}

Thus, enabling us to code this:

let maybeName1 = Maybe("Snir")
let maybeName2 = Maybe(undefined)
let maybes = [maybeName1, maybeName2]

maybes.map((maybeObj) => {
  maybeObj.map((name) => console.log(`Hi ${name}!`)
}
// Will logs: "Hi Snir!"

As you can see, the Maybe is a box for holding a value safely, while we can apply function using map to these values (and not needing to worry about checking for "null" values, as the Maybe implementation takes care of that).

In functional programming, these boxes are all over the place. And, may I say, in languages like Haskell with evolved type system, they are even more elegant.

There is more! one last weird example - functions.

So we understood that structures are boxes. Lists are a box for many values, Maybes are a box for safe evaluation of optional values.
But functions are boxes too. Boxes for code execution data.
We can map functions over functions too!

This is where it gets a bit weird, but this is the most important example IMO as it expands your view of what "structures" are.

Sadly, this is also where we have to leave the natural realms of JavaScript, as JS does not hold functions as perfect boxes for implementing functors on them.

The important bit here is natural partial application for functions, which exists in Haskell, Scala and many other functional-natural languages.

In Haskell for example, every function get just one argument, always. So how do we pass more than one argument? well, Haskell just automatically apply the function it created from the first argument, to a function with the second argument.

This creates a world where partially applied (or curried in other name) functions are a first class feature of the language.

Take a look at that:

-- This function takes 2 arguments: name, and address
printPerson name address = putStrLn (name ++ address)

-- Let's apply it with 2 arguments to get a print:
printPerson "Snir" " Tel Aviv"
-- This will print "Snir Tel Aviv"

-- We can also just partially apply, and store in another name:
printShani = printPerson "Shani"
-- This will not print anything yet. It just returns a partially applied function

printShani " New York"
-- This will print "Shani New York"

There are javascript libraries to make this "more" natural, like Ramdajs and it's friends.
I will demonstrate from now on with an "Imaginary" JS that naturally supports this, just so you'll have an easier time following the syntax, alongside haskell, for those who feel comfortable with it.

Let's look at some imaginary map implementation for functions in JS:

// NOTE: this is in an imaginary JS where partial application is natural. // This will not work in real life, it just for understanding the concept.
// And as with the example before, this is not really how `this` works.
// Just assume it refers to the context function, for readability.
Function.map = (fun) => {
  this(fun)
}

Which will theoretically enable us to do:

let add10 = (n) => n + 10
let multiply2 = (n) => n * 2
let addThenMultiply = add10.map(multiply2)

addThenMultiply(1) // Will result in 22

And this is a functor too now.
A function is a structure storing computational information, and mapping over it is changing the stored value - aka the computational information, from just "add 10" to "add 10 then multiply by 2" while not changing the structure itself, which is being the concept of function.

If you got that, it's pretty safe to say you get the conceptual generic idea of functors.

For brevity, and correctness (not playing with imaginary JS) here is the same thing in haskell:

-- The (->) is what represents functions in haskell.
-- This is an instance implementation of Functors to (->) - functions.
-- We implement the `fmap` here, which is just the `map` function.
instance Functor ((->) r) where  
  fmap f g = (\x -> f (g x))

-- Intentionally avoid point-free style, for easier read.
add10 n = n+10
multiply2 n = n*2

addThenMultiply = add10 `fmap` multiply2
addThenMultiply 1

Formality! Let's define functors formally.

Few. You got so far.
Let's just wrap it up with the formal definition of Functors.

A functor must implement map function such that it takes a function from type a to type b, and a Functor with value of type a, and returns Functor with type b.

-- Formal haskell type definition
(a -> b) -> f a -> f b

What does it mean? let's start easy.
We have a list [1,2,3] and a function addOne = (n) => n + 1
Then the list is the Functor, which holds values of type Number. Th function, is a function from Number to Number. So we should result again in a functor (list) of the same type (number).
[1,2,3] -> [2,3,4]

Now say we have a function from Number to another type:
strNum => (n) => "num: " + n
Then, going through the rule, it will be a function, from Number to String transforming a Functor (list) of Number to Functor of String.
[1,2,3] -> ["num: 1", "num: 2", "num: 3"].

Rules

For functors to work as expected, in any generic usage of function, we need to keep 2 basic rules:

1. Functors must preserve identity morphisms This basically means, that if I pass a no-op function for map, the functor should remain intact. Basically, map shouldn't change anything by itself, without the function provided.

let noop = (n) => n
[1,2,3].map(noop)
// Must return `[1,2,3]` again.

1. Functors preserve composition of morphisms This means, that mapping with a composed function, should give the same result as mapping with the functions separated.

let addTwo = (n) => n + 2
let MultiplyTwo = (n) => n * 2
let addThenMultiply = (n) => MultiplyTwo(addTwo(n))

[1,2,3].map(addTwo).map(MultiplyTwo) // [6,8,10]

// Must be equivalent to the use of the composition morphism:
[1,2,3].map(addThenMultiply) // [6,8,10]

That's it!

P.S
There are much more to be said about functors, and more variants of functors to cover.
This should give you a good understanding of the concept, and an easy gateway to more advance topics.

Comments

[Craig McIlwrath]

Why did you write your Maybe.map implementation that way? Wouldn't it make more sense to use the function keyword and the Maybe prototype so that you don't have to leave that note about this?

Something like this:

Maybe.prototype.map = function map(fun) {
  if (this.status === 'nothing') {
    return;
  }

  return fun(this.value);
}

And as an additional note, your (and my rewritten) definition of maybe doesn't satisfy the laws of a functor (maybe.map(noop) !== noop(maybe))

[Snir David]

You are absolutely right (:
I tried to focus on explaining the functors concept, rather than implementation in any language.
JS was chosen as it has easy syntax readable by many.
I didn't want to go into things such as prototype etc'.

But your comment is most welcome, in case it will confuse other people, I hope they will be able to get their answer here (:

[ezzabuzaid]

Thank you, very helpful article