Functor in the 3 different worlds: Linguistics, Mathematics, Programming

While I  was learning about functor I found that it is defined in the category theory. The category theory is a modern mathematic field of the 20 century, which was taught to undergraduates in universities. When I was a student I also took that category theory class but I did not see any interesting. Now I meet it again and this time I could see its interesting application in the functional programming. The furthermore interesting thing is that the name functor was borrowed by mathematicians from the philosopher Rudolf Carnap, who used the term in a linguistic context in which it also has other names as grammatical functor or function word. The English words such as the/that, and/but, in/of, some/both …, are the specific examples of the grammatical functor. They have little or no meaningful content, but they play a role to glue pieces of sentences together into longer syntactic patterns. You can understand the importance of the grammatical functors from the following observation: “Function words account for less than one-tenth of 1 percent of your vocabulary but make up almost 60 percent of the words you use.” (James W. Pennebaker, The Secret Life of Pronouns. Bloomsbury Press, 2011)

We have visited the hometown of the name functor where it was born and used in the linguistic world. Next, we will enter the mathematic world to see how the mathematic functor is defined in the category theory. At last, we will delve into the programming world to check how the programming functor is defined in Functional Programming.

In mathematics a category C consists of the following three mathematical entities:

• A class ob(C), whose elements are called objects
• A class hom(C), whose elements are called morphisms or maps or arrows. Each morphism f has a source object a and target object b. The expression f : a → b, would be verbally stated as “f is a morphism from a to b“. The expression hom(a, b) denotes the hom class of all morphisms from a to b.
• A binary operation ∘, called composition of morphisms, such that for any three objects a, b, and c, we have hom(b, c) × hom(a, b) → hom(a, c). The composition of f : a → b and g : b → c is written as g ∘ f , governed by two axioms: (1) Associativity: If f : a → b, g : b → c and h : c → d then h ∘ (g ∘ f) = (h ∘ g) ∘ f; (2) Identity: For every object x, there exists a morphism Ix : x → x called the identity morphism for x, such that for every morphism f : a → b, we have Ib ∘ f = f = f ∘ Ia

Functors are structure-preserving maps between categories. They can be thought of as morphisms in the category of all (small) categories. A functor F from a category C to a category D, written F : C → D, consists of:

• for each object x in C, an object F(x) in D
• for each morphism f : x → y in C, a morphism F(f) : F(x) → F(y), such that the following two properties hold: (1) For every object x in C, F(Ix) = IF(x); (2) For all morphisms f : x → y and g : y → z, F(g ∘ f) = F(g) ∘ F(f)

Before we begin investigating the programming functor I want to introduce the 2 related concepts.
Hash Category:
Hask is the category of Haskell types and functions. The objects of Hask are Haskell types, and the morphisms from objects A to B are Haskell functions of type A -> B. The identity morphism for object A is id :: A -> A, and the composition of morphisms f and g is f . g = \x -> f (g x). We can generalize that to the types of other languages, like Scala, as well. For every function converting one type to another, in Hask there is an arrow between the two types. Arrow composition is just function composition. The identity arrows correspond to the identity functions. When a functor F transforms a category A into itself, we call it an endofunctor and we write F:A → A. In Functional Programming all the functors are just endofunctors in Hask.
Type Constructor:
Type constructor takes a type as a parameter to construct a concrete type. For example List[T], Option[T] are type constructor. You need to specify the value of the type parameter T in order to produce a Concrete Type. For example, List[String] is a concrete type, while List itself is a Type Constructor. We will write F[ _ ] to denote that F is a type constructor.

Base on the previous mathematical defenition, we can define the functor in Scala as below:

trait Functor[ F[ _ ] ] {
    def map [ A,B ] ( f: A => B ) : ( F[A] => F[B] )
}

The programming functor F above plays a role similarly as a mathematic functor does in the mathematic world. It maps each value of type A in Hash to the value of type F[A] in Hash, and, it maps each function f: A => B in Hash to the function F(f): F[A] => F[B] in Hash too. Note that the return type of map is a function, so we can re-write the above trait to the programmer friendly format as below:

trait Functor[ F[ _ ] ] {
  def map [ A,B ] ( a : F[A] ) ( f: A => B ) : F[B]
} 

Use that trait we can write an instance example for List as:

val listFunctor extends Functor[List] {
  def map [ A,B ] ( a : List[A] ) ( f: A => B ) : List[B] = a map f
} 

Reference sources:
1. MEAP Edition Manning Early Access Program, Functional Programming in Scala, version 10
2. https://en.wikipedia.org/wiki/Functor
3. https://en.wikipedia.org/wiki/Category_theory
4. http://nikgrozev.com/2016/03/14/functional-programming-and-category-theory-part-1-categories-and-functors