dimitris papadimitriou
dimitris papadimitriou More than 12 years’ experience as full stack developer and Software Architect . Functional javascript with categories.

Introduction to Functors (Video)

Introduction to Functors (Video)

The Idea: In JavaScript the most famous functional programming idea is to use array.map to replace iterations instead of for loops in order to transform the values of the array. That is because an array is a Functor, which is a more abstract idea that we will explore in this section. Functors can be considered the core concept of category theory. Functors is all about providing a map method that makes some valid transformation to encapsulated data.

In mathematics, a functor is a map between categories. A category is just a collection of objects and arrows between objects like below. Category c has the objects x,y and an arrow f from x to y. That’s all there is to it basically. kind of.


In Programming one major category is this of Types int,bool…. The arrows between the types are the functions/methods f:ab. But because the concept is so broad, categories arise in all kind of areas inside programming. For example If we get the category where objects are programs then the arrows between them could be Compilers, that get an input program and give a different program Comp: Program1→AssemblyProgram. A parenthesis here. My absolute favorite book in this topic is Computability and Complexity: From a Programming Perspective also Neil has a free pdf here.

The Simplest Functor - Identity Functor

Let me tell you what functor is right now for Object oriented programming paradigm: It’s a *container*. together with a mapping function. We will start by looking at the minimum structure that qualifies as a functor in javascript:

1
2
3
4
const Functor = (v) => ({
  value: v,
  map: (f) => Functor(f(v))
});

Run This: Js Fiddle

This is the minimum construction that we could call a functor because it has exactly two things

  1. ​ A “constructor” that maps a value v to an object literal

    1
    
     Id = (v) => {value: v}
    
  2. and it has a mapping method

    1
    
    map:(f) => {_} 
    

    that lifts functions f

Because it’s the minimal functor structure it goes by the name Identity functor. Let us see a simple example where we have two integers 2 and 4 (here we take for simplicity the category of integers as our initial category C) also in this category there is the function square = x=>x*x that maps 2 to 4.

If we apply the Id(_) constructor we can map each integers to the Id[int] category. For example 2 will be mapped to Id(2) and 4 maps to Id(4), the only part missing is the correct lifting of the function f Id[f] to this new category. It’s easy to see that the correct mapping is:

1
this.map = (f) => Id(f(value));

Because:

1
2
var square = x=>x*x;    
Id(2).map(square) = Id(square(2))

The type of the functor map method is

1
map: (a  b)  f(a)  f(b)

this means that if you give me a function from a to b (a → b) and I have an f(a), I can get an f(b)

Mapping objects with. of(_)
In order to cover the first requirement that a functor should map each object x in C with an object F(x) in D we have used a “constructor” that maps a value v to an object literal Id = (v) => { }. In many functional libraries online you may find the explicit definition of an .of() that does the same thing

        Id.of =v=>({ v: v, map: f => Id.of(f(v))  })
        
Run This: Js Fiddle

The Basic Functor Mechanics

The following picture represents the whole idea behind how we construct the map of a functor. If we accept the Functor as a container metaphor ( in our case this is the object literal seen as a container {value: v}), which is an acceptable way to visualize functors especially in an Object-oriented programming setting.

The mapping function that lifts the function f: int →int It follows the steps:

  1. Open the container F(a) and access the value a
  2. Applying the function f on the value a and get a new value b
  3. wraps the resulting value again into a new container F(b) and return this F(b)

in the simplest form of the Identity functor the map follows those steps

Commutative Diagrams

There is one important thing about the mapping function, though. The mapping should get the same result for [4] if we take any of the two possible routes to get there. This means map (aka lifting of a function from C to D) should preserve the structure of C.

  1. We could first get the Functor and then map it. This is the red path on the diagram.

    1
    
     functor(y) = functor(x).map(f); 
    
  2. Or first lift 2 with f and then get the Functor.

    1
    
     functor(y) = functor(f(x)); 
    

Two objects that were connected with an arrow in category C, should also be connected with an arrow in category D. And reversely, if there was no connection in C there should be no connection in D. When the red and blue paths give the same result, then we say that the diagram commutes

Moreover, that means that the lifting of morphisms (aka arrows, aka functions in programming) preserves the structure of the objects in C.

In practical day to day programming, commutating diagrams means that we can exchange the order of operations and still get the same result. It is not something that happens automatically and is something very helpful to have when coding

Commuting Diagrams in Category Theory
in Category theory the concept of commuting diagrams is equivalent to the concept of equality. Is a visual diagrammatic notion of Equality.

Excerpt from the Book Functional Programming in Javascript in LeanPub https://leanpub.com/functional-programming-in-js-with-categories

comments powered by Disqus