λ Tony's blog λ

The weblog of Tony Morris

Posted on June 28, 2008, in Programming

Runar recently made mention of these so-called Functors and Monads in his excellent post about concurrency/actors in Java. There are all sorts of tutorials out there for understanding what a Monad is, however, I am of the opinion that one must first understand what a Functor is. This is because it is less complex and more general (all monads are functors plus more).

The Java Posse also made a couple of false claims about Runar’s article, but one in particular needs addressing. This is the notion that a functor is applicable to “Functional Programming”. This is false. A functor is applicable to *programming*. You really, really need to understand what a functor is, if you’re ever going to be skilled in *any type of* programming; even if it’s just Java web applications for the rest of your life. This concept does not exist ‘on the other side of the fence’ in the imaginary ‘functional programming world’. These suggestions are understandable of course and I don’t intend to labour the point – only make this point clear, since these apparent divides seem to pop up often. On with the story…

In Java, we have an interface called `[CharSequence](http://java.sun.com/javase/6/docs/api/java/lang/CharSequence.html)`

. A few things can be said about `CharSequence`

. How about:

All implementations guarantee that for some integer

`n`

, then if`n >= 0 && n < length()`

, then`charAt(n)`

will not throw an exception.

We might call this a *law* about `CharSequence`

that all implementations must satisfy. We could even find other laws that must satisfy about implementations of the `CharSequence`

interface.

A Functor is an interface and it has two laws. Sadly though, this interface cannot be expressed using Java’s type system – it is simply not clever enough. We must use a hypothetical Java to express it. First though, we have to make up for Java’s missing first-class functions by using an interface. This is easy:

```
interface Function<A, B> {
B f(A a);
}
```

OK, so this a just an interface like any others. It needn’t satisfy any laws; it just takes an argument (A) and returns (B). We could write bazillions of implementations of this interface in Java. We’re going to need this interface to write the `Functor`

interface.

Now, the missing part of Java is called *higher-kinds* – a term you needn’t concern yourself with too much. I hope this hypothetical syntax is enough to make the point clear:

```
interface Functor<E<_>> {
<A, B> E<b> fmap(Function<A, B> f, E<a> fa);
}
```

So the foreign part here is `E<_>`

. Consider E to stand for ‘Environment’. It is a type parameter that takes yet another type parameter (which is why it is denoted E<_>). This means I could use `List`

or `Set`

, but not `Integer`

as the type parameter value for E, since `List`

and `Set`

take another type parameter while `Integer`

does not. You might think of the `Functor`

interface as ‘applying the given function within the environment’.

We might write an implementation like this:

```
class ListFunctor implements Functor<list> {
public <A, B> List<b> fmap(Function<A, B> f, List<a> list) {
// todo: apply the given function on all elements in 'list' and return the result
}
}
```

In general discussion, we would call this *the list functor*, simply because the value for the environment has been applied. In Runar’s article, he was talking about the `Callable`

functor; yet another environment. There are many possibilities for the environment here; `List`

and `Callable`

are but two.

Let us not forget the laws :) Just like all implementations of `CharSequence`

have laws to obey, so do all functors. They are called *identity* and *composition*.

Remember the `Function`

interface? Here is an implementation:

```
class Identity<a> implements Function<A, A> {
public A f(A a) { return a; }
}
```

If we are given an implementation of `Functor`

– which I will call `f`

– then it must satisfy `f.fmap(new Identity(), x)`

is equivalent to `x`

*(for any value of x)*. So that’s the identity law out of the way. Mapping *the identity function* across a functor yields the same value.

The law of composition is a little less friendly when it comes to expressing it in Java so I will refrain :) While it is an important part of making up the concept of a functor, it may be best to defer this final piece of the puzzle for now.

For completeness, I will state the law using a shorter syntax, but if this is foreign or worrying, then please ignore it: `f.fmap(a compose b, x)`

is equivalent to `f.fmap(a, f.fmap(b, x))`

*(for any value of a, b and x – a and b are Function objects)*.

That’s all there is to a Functor. If you use the `map`

function on lists or perhaps the `map`

method on `scala.Option`

, then you are using one specific instance of a functor, since these functions/methods satisfy the conditions for a functor. Even throwing an exception is using a specific functor! Perhaps that can be explained another time :)

I should also add that when referring to a functor (unqualified), we are referring to a *covariant* functor. Other types of functors include contra-variant and invariant functors. We can talk about those another day :)

Next: Just What the Flip is a Monad?

Questions?