## Tuesday, July 16, 2013

### Functors

Consider the function below.

``````function plus1(value) {
return value + 1
}
``````

It is just a function that takes an integer and adds one to it. Similarly we could could have another function plus2. We will use these functions later.

``````function plus2(value) {
return value + 2
}
``````

And we could write a generalised function to use any of these functions as and when required.

``````function F(value, fn) {
return fn(value)
}

F(1, plus1) ==>> 2
``````

This function will work fine as long as the value passed is an integer. Try an array.

``````F([1, 2, 3], plus1)   ==>> '1,2,31'
``````

Ouch. We took an array of integers, added an integer and got back a string! Not only did it do the wrong thing, we ended up with a string having started with an array. In other words our program also trashed the structure of the input. We want `F` to do the "right thing". The right thing is to "maintain structure" through out the operation.

So what do we mean by "maintain structure"? Our function must "unwrap" the given array and get its elements. Then call the given function with every element. Then wrap the returned values in a new Array and return it. Fortunately JavaScript just has that function. Its called `map`.

``````[1, 2, 3].map(plus1)   ==>> [2, 3, 4]
``````

And `map` is a `functor`!

A `functor` is a function, given a value and a function, does the right thing.

To be more specific.
A `functor` is a function, given a value and a function, unwraps the values to get to its inner value(s), calls the given function with the inner value(s), wraps the returned values in a new structure, and returns the new structure.

Thing to note here is that depending on the "Type" of the value, the unwrapping may lead to a value or a set of values.

Also the returned structure need not be of the same type as the original value. In the case of `map` both the value and the returned value have the same structure (Array). The returned structure can be any type as long as you can get to the individual elements. So if you had a function that takes and `Array` and returns value of type `Object` with all the array indexes as keys, and corresponding values, that will also be a functor.

In the case of JavaScript, `filter` is a `functor` because it returns an `Array`, however `forEach` is not a `functor` because it returns `undefined`. ie. `forEach` does not maintain structure.

Functors come from category theory in mathematics, where functors are defined as "homomorphisms between categories". Let's draw some meaning out of those words.

• homo = same
• morphisms = functions that maintain structure
• category = type

According to the theory, `function F` is a `functor` when for two composable ordinary functions `f` and `g`

``````F(f . g) = F(f) . F(g)
``````

where `.` indicates composition. ie. functors must preserve composition.

So given this equation we can prove wether a given `function` is indeed a `functor` or not.

## Array Functor

We saw that `map` is a functor that acts on type `Array`. Let us prove that the JavaScript `Array.map` function is a `functor`.

``````function compose(f, g) {
return function(x) {return f(g(x))}
}
``````

Composing functions is about calling a set of functions, by calling the next function, with results of the previous function. Note that our `compose` function above works from right to left. `g` is called first then `f`.

``````[1, 2, 3].map(compose(plus1, plus2))   ==>> [ 4, 5, 6 ]

[1, 2, 3].map(plus2).map(plus1)        ==>> [ 4, 5, 6 ]
``````

Yes! `map` is indeed a `functor`.

Lets try some functors. You can write functors for values of any type, as long as you can unwrap the value and return a structure.

## String Functor

So can we write a functor for type string? Can you unwrap a string? Actually you can, if you think of a string as an array of chars. So it is really about how you look at the value. We also know that chars have char codes which are integers. So we run plus1 on every char charcode, wrap them back to a string and return it.

``````function stringFunctor(value, fn) {
var chars = value.split("")
return chars.map(function(char) {
return String.fromCharCode(fn(char.charCodeAt(0)))
}).join("")
}

stringFunctor("ABCD", plus1) ==>> "BCDE"
``````

You can begin to see how awesome `functors` are. You can actually write a parser using the string functor as the basis.

## Function Functor

In JavaScript functions are first class citizens. That means you can treat functions like any other value. So can we write a functor for value of type function? We should be able to! But how do we unwrap a function? You can unwrap a function by calling it and getting its return value. But we straight away run into a problem. To call the function we need its arguments. Remember that the functor only has the function that came in as the value. We can solve this by having the functor return a new function. This function is called with the arguments, and we will in turn call the value function with the argument, and call the original functors function with the value returned!

``````function functionFunctor(value, fn) {
return function(initial) {
return function() {
return fn(value(initial))
}
}
}

var init = functionFunctor(function(x) {return x * x}, plus1)
var final = init(2)
final() ==> 5
``````

Our function functor really does nothing much, to say the least. But there a couple things of note here. Nothing happens until you call final. Every thing is in a state of suspended animation until you call final. The function functor forms the basis for more awesome functional stuff like maintaining state, continuation calling and even promises. You can write your own function functors to do these things!

## MayBe Functor

``````function mayBe(value, fn) {
return value === null || value === undefined ? value : fn(value)
}
``````

Yes, this is a valid `functor`.

``````mayBe(undefined, compose(plus1, plus2))     ==>> undefined
mayBe(mayBe(undefined, plus2), plus1)       ==>> undefined
mayBe(1, compose(plus1, plus2))             ==>> 4
mayBe(mayBe(1, plus2), plus1)               ==>> 4
``````

So mayBe passes our `functor` test. There is no need for unrapping or wrapping here. It just returns `nothing` for `nothing`. Maybe is useful as a short circuiting function, which you can use as a substitute for code like

``````if (result === null) {
return null
} else {
doSomething(result)
}
``````

## Identity Function

``````function id(x) {
return x
}
``````

The function above is known as the `identity function`. It is just a function that returns the value passed to it. It is called so, because it is the `identity` in composition of functions in mathematics.

We learned earlier that functors must preserve composition. However something I did not mention then, is that functors must also preserve identity. ie.

``````F(value, id) = value
``````

Lets try this for `map`.

``````[1, 2, 3].map(id)    ==>>  [ 1, 2, 3 ]
``````

## Type Signature

The type signature of a function is the type of its argument and return value. So the type signature of our `plus1` function is

``````f: int -> int
``````

The type signature of the functor `map` depends on the type signature of the function argument. So if `map` is called with `plus1` then its type signature is

``````map: [int] -> [int]
``````

However the type signature of the given function need not be the same as above. We could have a function like

``````f: int -> string
``````

in which the type signature of `map` would be

``````map: [int] -> [string]
``````

The only restriction being that the type change does not affect the composability of the functor. So in general a functor's type signature can

``````F: A -> B
``````

In other words `map` can take an array of integers and return an array of strings and would still be a functor.

Monads are a special case of Functors whos type signature is

``````M: A -> A
``````

More about monads in the next chapter.

#### 3 comments:

1. It's a pleasure to read your blog posts! They include the right references and exclude the complications, and explain these concept finally in a simple way. Thanks, sincerely!

2. String is not exactly a functor since it's not parametric - if the "container" type doesn't allow for it's value to be polymorphic, then it can't satisfy the laws. In String's case, it's just Char instead of "a".

You can, however, make a Profunctor instance for Function. With that you can transform a String into a list of chars during a computation, then transform it back:

Function.prototype.dimap = function(g, h){ return compose(h, this, g); }

var stringToChars = dimap(split(""), join(""))

then e.g. stringToChars(reverse)("mystring")

But anyways, i thought that was neat and figured I'd share.

Really digging the FPJS articles!

1. I did suspect strings may not be functors. But I thought it would make a good example. Thanks for clarifying the whole thing.