What the Functor?

My last post aimed to make functional programming as straightforward as possible. An explicit goal of that article was to avoid unnecessary jargon like monads and functors and stick to concepts that will make our code better.

This time around let's dive into all the scary terms and make them not so scary. While knowing these terms might not make your code better, they're fun to know.

The one thing we skip in this article is lambda calculus, check out Mary Had a Little Lambda for more on that. I also have an article called Map, Filter, Reduce that is more practical.

As a warning, we're gonna be diving into some abstract mathematics. This XKCD is now more relevant than ever.

Functional programming combines the flexibility and power of abstract mathematics with the intuitive clarity of abstract mathematics.[11]

A monad is just a monoid in the category of endofunctors, what's the problem? [7] [8]. Hopefully, you'll understand this when we're done.

One final disclaimer, I didn't know any of this when I set out to write this article. I've heavily annotated this post with resources I used to learn this stuff as I was going. If you're already knowledgeable on category theory, please be gentle when correcting me on twitter @MatthewGerstman.


Functors

What fun would it be if we didn't start with the titular term, functor.

A functor is anything that can be mapped over. This is most commonly a list, but really it's any object that can be mapped over.

For example, we can make a Wizard that can be mapped over.

Note: in most practical situations, a functor would be parametric (containing a type parameter like String in Array<String>), but Wizard does fulfill the basic definition of a functor.

Now the map function also needs to meet the following criteria.

Identity Law  [1]

If map is given an identity function it must return the exact same object. Like so:

functor.map(x => x) === functor

This one is hopefully straightforward.

Composition Law  [1]

functor.map(x => f(g(x))) === functor.map(g).map(f)

Woah that's a intimidating. What does this actually mean? Let's look at an example.

We have joinGryffindor and learnExpelliarmous. If we call

wizard.map(joinGryffindor).map(learnExpelliarmous) it needs to be equivalent to  wizard.map(w => learnExpelliarmous(joinGryffindor(w))).

Now it's worth calling out, it needs to be functionally equivalent. In abstract mathematics we're not worried about pointers and references so we can consider this good enough. This is also known as "Fast and Loose Reasoning is morally correct." [13]


Category

The next term we need to dive into is a category. A category is an algebraic structure that models objects and their relationships with each other.

Below we can see a category of int, string, and float.

Taken from article by Nikolay Grozev [5].

The category is the entire chart. It's how we convert from int to string, float to string, or int to float, or float to int.

Now while in practice, a functor is just a thing we can map over, it has a more advanced explanation. In category theory, a functor is a transformation between two categories [5]. This is a transformation of the entire category.

For example, we can transform the entire category above with a List functor. The relationships between all of the types goes from a function like toString to map(func) or  map(toString). This also applies to toFloat, round, and any other functions in our category.

Taken from article by Nikolay Grozev [5].

Endofunctor

Now that we have functors and categories, let's discuss endofunctors. An endofunctor is a functor that transforms a category into itself.

I spent several hours trying to grok this, and more importantly, understand how it's relevant in software. After reading many articles I stumbled on this talk [6] by @DanielaSfregola and it clicked.

For all intents and purposes, all functors in programming are endofunctors. A functor is really just metadata around a value that allows us to map over it.

The objects in our category are our types, and the arrows are the relationships between those types. These relationships are fundamental to the language so we can't just create a wrapper (functor) that changes how these types are interrelated.

We can't change how types are related unless we change the definition of the type altogether. Even in JavaScript, which has gnarly behaviors around NaN, undefined, and other types, the relationship between them is still defined in the spec and can't be changed with a simple functor.

Practically speaking, all functors in programming are endofunctors. There are all sorts of nuanced exceptions to this rule but those are out of scope here. Think of it like physics 101 when we pretended friction wasn't a thing.

Seriously though, watch that talk, I closed so many tabs after watching that talk.


Monoid

Cool cool, cool cool cool. We've defined some of the scariest terms in functional programming, let's move on to monoids.

A monoid is a category with one object. A monoid has three important rules: identity, composition, and associativity. In programming, it's a wrapper around an object that enforces these rules.

  • Identity: This states that there must be a way to use the monoid such that it returns itself.
  • Composition: This states that we must be able to combine values using the monoid.
  • Associative: This states that the order of operations remains constant so (a +b) + c === a + (b + c).

If these seem vague and generalized, well thats how abstract math works. Let's look at a practical example, a string monoid. [9]

Above, we can see our StringMonoid with an identity value and a compose function.

We can use the compose function to produce a new string.

If we compose with the identity value we get the same value.

Finally, if we call compose on the same arguments it doesn't matter which pair we do first.

Here are some other examples of monoids in JavaScript:

  • Adding and multiplying numbers (with 0 and 1 as the identity value respectively).
  • Joining multiple arrays.
  • Composing multiple functions together.

Monads

We did it! We made it to Monads.

Before we dive in let's take a step back. Functors and monoids were both wrappers around a value that allow us to execute operations on them. In the case of functors it was map in the case of monoids it was compose, where compose is a single operation.

Now monads. Monad's are both a functor and a monoid. That doesn't make this any simpler though. Let's define this in simpler terms.

A monad is a wrapper around some value that makes it easier to compose functions around it. This is often used to abstract away things like API calls or IO. In fact a Promise is a monad.

If we look at these  types above, we have a Wizard and a function that returns a Promise<Wizard>. This promise allows us to compose functions on top of it without worrying about the underlying IO needed to go fetch a Wizard from the server.

Lets break down further.

A monad is based on a simple symmetry — A way to wrap a value into a context, and a way to unwrap the value from the context [10].

Lift

A monad allows us to lift a type into the monad context. In this case we're going from Wizard to Promise<Wizard>. The process of wrapping the Wizard in a Promise is called lifting.

Map

A monad also allows us to map from one wrapped type to another. So we can call wizardPromise.then(joinGryffindor).then(learnExpelliarmous) to update the underlying wizard in the promise.

I should mention that the monad map is the same map we get with a functor. This is because monads are a type of functor.

Now it's worth noting that Promises don't explicitly provide a map function, but then gets us close enough.

FlatMap

Finally, monads give us a way of going from Promise<Promise<Wizard>> to Promise<Wizard>. We should be able to have an arbitrarily nested monad and get to the original underlying value. We should also be able to do a flatMap on it. This is commonly done with a chain function.

Back to Monads

Now it's worth noting that Promises don't perfectly map to monads, but they're close enough to understand the data type.

This also seems like a good time to reiterate, monads are an advanced abstract mathematical type. We're bringing these into our understanding of programming. They don't always line up perfectly with every construct in JavaScript. That's okay!

The point here isn't to make our code perfectly mathematical, we're just trying to understand some of the advanced math that powers our languages.


Wrapping Up

I'm going to admit. This article was challenging to write. I learned a lot in the process. I'd like to reiterate, none of this is important to your day to day code. But if you were curious what all those scary FP terms mean hopefully this satisfied that curiosity.

If you'd like something that will make your code better, check out Functional Programming Fundamentals. You can also check out Map, Filter, Reduce. If you want to learn about lambda calculus check out Mary Had a Little Lambda.

Special thank you to @glittershark1 and @jetpacmonkey for reviewing this.

Thank you to @drboolean for correcting my functor example on Twitter.

Also if you feel the need to buy me a drink you can do so here or follow me on twitter @MatthewGerstman.


Ads

These ads help me pay to keep this site up. Feel free to buy, watch, listen or ignore these like any other ad.


References

Note: I didn't end up quoting all of these directly, but I consulted all of them while writing this article.

  1. https://medium.com/@dtinth/what-is-a-functor-dcf510b098b6
  2. https://medium.com/javascript-scene/functors-categories-61e031bac53f
  3. https://medium.com/@l.mugnaini/functors-applicatives-and-monads-in-pictures-784c2b5786f7
  4. https://medium.com/@lettier/your-easy-guide-to-monads-applicatives-functors-862048d61610
  5. https://nikgrozev.com/2016/03/14/functional-programming-and-category-theory-part-1-categories-and-functors/
  6. https://www.youtube.com/watch?v=8XGFFMPHG0o
  7. http://james-iry.blogspot.com/2009/05/brief-incomplete-and-mostly-wrong.html
  8. https://stackoverflow.com/questions/3870088/a-monad-is-just-a-monoid-in-the-category-of-endofunctors-whats-the-problem/
  9. http://s3.amazonaws.com/erlang-conferences-production/media/files/000/000/760/original/Daniela_Sfregola_-_A_Pragmatic_Introduction_to_Category_Theory.pdf?1510238446
  10. https://medium.com/javascript-scene/javascript-monads-made-simple-7856be57bfe8
  11. https://xkcd.com/1270/
  12. https://gist.github.com/ericelliott/ea925c58410f0ae74aef
  13. http://www.cse.chalmers.se/~nad/publications/danielsson-et-al-popl2006.html
Show Comments

Get the latest posts delivered right to your inbox.