If you have used the Java Stream Api, the Browser’s Fetch Api or modified a list in Javascript, you’ve come across a Functor. It’s a beautiful, intensively analyzed concept from Category Theory and Functional Programming that you’ll begin to see everywhere.
You probably know the the Java Stream Api as a convenient interface to perform a series of data transformations:
List<String> lengths = Stream.of("a", "b")
.map(String::length)
...
.collect(Collectors.toList());
The same can be achieved with regular lists in Javascript:
const lengths = ["a", "b"].map(item => item.length);
But would you have guessed that Promises (called “Future” in Java) like
const lengthProm = fetch('http://getString.com')
.then(response => response.json())
.then(item => item.length);
have a similar underlying structure to be used under the same interface? And Sets, Trees, Optionals, and even functions themselves? The underlying structure in common is called a “Functor”.
More: Short tutorial on Java Streams
More: Documentation of Promises
More: Fetch Api Doc
Origin
Functor is a concept for containers from Category Theory, the branch of Math that investigates patterns of composition with functions. These patterns turn out to be tremendously useful in programming, because programming is all about decomposing large problems into smaller ones and composing small solutions back into larger ones. As you may know, mathematicians have a tendency to generalize a concept as far as humanly possible while keeping and proving useful laws about it. This is why programming languages, frameworks and apis come and go but concepts like Functor stay: You will begin to see it everywhere.
More: An enjoyable philosophical introduction into Category Theory
In the following sections you will see a lot of code examples to show how widespread this concept already is in mainstream programming languages. The examples will vary between Java and Javascript/Typescript code, depending on how well the language can show the concept without too much syntax.
Functor
A Functor is the most common Category Theory concept you will find in mainstream languages, sometimes under disguise. A Functor is a container type that provides a map
function to modify its items, the payload type, with a pure function. In Java and Typescript this type has the shape Container<Payload>
and includes lists, optionals, trees, sets etc.
To get a feeling on how widespread Functors are, we will see some interesting examples in detail.
List Functor
The most widespread Functor you will see is a list:
"a","bb"].map(item => item.length) // result is [1, 2] [
This Javascript list ["a", "bb"]
is a Functor, because it has type List<String>
as the container type (in the Java/Typescript notation) and String
as the payload type, and it provides a map
function to modify its items. This map
function takes a pure function of type String -> Integer
and transforms the value of type List<String>
into a value of type List<Integer>
. Do you see how the payload type is simply replaced according to the pure function. This becomes more evident when we look at the types of the same example written as follows:
const strings = ["a","bb"]; // type: List<String>
const modify = item => item.length; // type: String -> Integer
const lengths = strings.map(modify);// type: List<Integer>
// lengths is [1, 2]
What we see with types, we can also see with the values: the map
function only modifies the payload items and not the container structure? The resulting list contains the same number of items in the corresponding same order. This is the main guarantee you get with a Functor.
The essence of a container as a Functor is the map
function that takes a pure function of type A -> B
(replace type variables A
and B
with any types you want) and transforms a Container<A>
into a Container<B>
by only modifying all the payload items A
but not the state/structure (often called “context”) of the container.
Unfortunately Java lists were not retrofitted to have a map
function for performance concerns. Instead you have to take a slight detour over Streams:
List<String> lengths = List.of("a", "bb").stream()
.map(item -> item.length()) // or just String::length
.collect(Collectors.toList());
Streams are “lazy” and permit certain optimization, lists are not. But the same Functor concept applies, because Brian Goetz, one of the Java Language Archtitects who decide what features make into the Java language, is privately a Haskell programmer and well aware of Functors.
More: How lazy Java Streams allow optimizations
Functor as a for-loop
A map
function is better to program with than a for-loop:
// classical style
const strings = ["a", "bb"];
const lengths = [];
for (i = 0, ; i < strings.length; i++) {
.push(strings[i].length)
lengths
}
// better but still improvable
const lengths = [];
for (const item of ["a", "bb"]) {
.push(item.length);
lengths
}
// best
"a","bb"].map(item => item.length); [
Not only is it shorter, but it’s also conceptually easier the mind to understand: It minimizes the “moving parts”, that is, things you can manipulate and get wrong. It’s pure (=side-effect-free) and all involved variables (["a", "bb"]
and item => item.length
) can be immutable (see why you should favor immutability). But most importantly, it forms an expression and makes that piece of code declarative. There are no statements involved anymore.
As a rule of thumb: An expression is a piece of code that represents (= evaluates to) a value and that you can assign to a variable like:
const strings = ["a","bb"]
// |-expresssion-| -> represents value ["a","bb"]
const lengths = ["a","bb"].map(item => item.length)
// |------------expression-----------| -> represents value [1,2]
In contrast, statements are commands for the computer to perform without representing a value:
const a = for (i = 0; ...) { ... }; // ⚡ doesn't work
// |---- statement -------|
const a = for (item of ...) { ... }; // ⚡ doesn't work
// |------ statement ------|
const a = while (i < 10) { ... }; // ⚡ doesn't work
// |---- statement -----|
const a = if (i < 10) { ... } else { .. }; // ⚡ doesn't work
// |--------- statement ---------|
With an expression you can think less about what that code procedurally does and more about what it declaratively is (=what value it represents):
Optional Functor
The next most widespread Functor you will see (at least in the Java world) is Optional:
.of("a").map(item -> item.length()) // result is 'of(1)' Optional
Again, the of("a")
is a Functor, because it’s a container—with container type Optional<String>
—that provides a map
function to modify its payload item—having payload type String
.
In this previous example, the map
function takes in a pure function of type String -> Integer
to transform Optional<String>
into Optional<Integer
. Again, do you see how the payload type is just replaced according to the pure function? This becomes more evident when we take a closer look at the types:
// example 1
= Optional.of("a"); // type: Optional<String>
var stringOpt <String,Integer> modify = item -> item.length; // String -> Integer
Function= stringOpt.map(modify); // type: Optional<Integer>
var lengthOpt // lengthOpt is 'of(1)'
// example 2
= Optional.empty(); // type: Optional<String>
var stringOpt <String,Integer> modify = item -> item.length; // String -> Integer
Function= stringOpt.map(modify); // type: Optional<Integer>
var lengthOpt // lengthOpt is 'empty()'
Notice again how the map
function only modifies the payload item and not the container structure? The internal state (called “context”) of the Optional, “with item” or “empty”, isn’t changed: If the Optional contains an item, the result contains one; if the Optional is empty, the result is empty. This makes Optional the better alternative to represent “no value” than null
: When using map
you cannot forget the null-check ever again.
More: “Context” of other Functors
More: Tony Hoare’s “Billion Dollar Mistake”: Null
Promise Functor
Another the widespread functor is the Promise type (sometimes called “Future”):
const stringProm = Promise.resolve("a"); //type: Promise<String>
const modify = item => item.length; //type: String -> Integer
const intPromise = stringProm.map(modify);//type: Promise<Integer>
With a Promise you wrap and represent a value that will be available later (like after downloading with fetch
), but you program as if it’s already here.
Notice again how the map
function in the previous example only modifies the payload item and not the container? The internal state (called “context”) of the Promise, “pending”, “fulfilled” or “rejected” isn’t changed, at least not by the map
function (only later on the next event loop).
More: Documentation of Promises
More: The Browser’s fetch
Api Doc
More: Nice talk explaining the JS Event Loop
Actually, in Javscript the map
function is called then
. However, this then
function is overloaded. It’s only equivalent to the Functor map
function when you pass in a pure function that does not return itself a Promise. If that function returns itself a Promise, you implicitly use the flatMap
of the Promise as a Monad.
Function Functor
One suprising Functor is a function. It can be viewed as a container and has a map
function. If we squint our eyes a little, we can view a function of type Boolean -> String
as a container of strings with booleans as the index: We can rewrite the function type as a container typeBoolFunction<String>
with String
being the payload type. This is just to emphasize the similarity to lists List<String>
. Instead of integers for the index (like in list.get(0)
we then use booleans (like f.apply(true)
or just f(true)
). So, in this example the function “container” holds two string values, one for each boolean.
As with any other Functor, the map
function for the function “container” accepts a(nother) pure function to modify its payload items:
= bool -> bool ? "a" : "bb";// BoolFunction<String>
var stringFunction = item -> item.length; // String -> Integer
var modify = stringFunction.map(modify);// BoolFunction<Integer>
var intFunction // intFunction is 'bool -> bool ? 1 : 2'
// of type 'Boolean -> Integer
The result is another function “container” of integers that also holds two items, one for each boolean. So again, the map
function hasn’t changed the shape/context of the “container”.
In Java this BoolFunction
interface doesn’t exists as such but is actually called Function<Boolean,String>
with two type slots/arguments. We say that “it’s a Functor only in the second type slot”, where you define the payload item type; the first slot just exists to configure the container index type and thereby controlling the function “container’s” size. The map
function is actually called andThen
and so only works on the second type slot. So, in real Java code the previous example is written as follows:
<Boolean,String> stringFunction = bool -> bool ? "a" : "bb";// Function<Boolean,String>
Function<String,Integer> modify = item -> item.length; // String -> Integer
Function<Boolean,Integer> intFunction = stringFunction.andThen(modify);//Function<Boolean,Integer>
Function// intFunction is 'bool -> bool ? 1 : 2'
// of type 'Boolean -> Integer'