λ Tony's Blog λ
Just what the funk is a Functor anyway?Posted on June 28, 2008
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
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:
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
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:
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
Set, but not
Integer as the type parameter value for E, since
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:
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;
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.
Function interface? Here is an implementation:
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
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?