In category theory, a functor is a mapping between categories. Practically speaking, given the following unary function interface:
public interface Fn1<A,B> {
apply(A a);
B }
A function of type Fn1<A,B>
to be lifted to a
function of type Fn1<F<A>,F<B>>
, for some
generic type F
.
In Java, a functor might look like this:
public interface Functor<A,F extends Functor<?,?>> {
<B> F map(Fn1<A,B> f);
}
I like to picture it like this:
.--------------. .-------------------.
| Category * | | Category F<*> |
|--------------| |-------------------|
| A | | F<A> |
| B | | F<B> |
| Fn1<A,B> ~~~~~~~ map ~~~~> Fn1<F<A>,F<B>> |
'--------------' '-------------------'
This can be read as follows:
*
contains objects of type A
and B
, and a morphism from A
to
B
.F<*>
contains objects of type
F<A>
and F<B>
, and a morphism from
F<A>
to F<B>
.F<*>
maps morphisms from
*
, for example converting Fn1<A,B>
into
Fn1<F<A>,F<B>>
.This is useful when you have a value of type F<A>
and you want to apply a function of type Fn1<A,B>
to
it, resulting in a value of type F<B>
.
Though Java doesn't have either an explicit unary function interface
or a Functor
interface, it's easy to write simple data
structures that make use of both. Let's look at some examples.
In other languages, a Maybe
is a box that might contain
a value. It has two implementations: Just
, which contains a
value of a given type, and Nothing
, which does not contain
a value.
If we imagine that Maybe
represents the category of
optional values, we can see that Just
and
Nothing
are functors. Here's how it looks:
.------------------. .--------------------------------------.
| Category * | | Category Maybe<*> |
|------------------| |--------------------------------------|
| Int | | Maybe<Integer> |
| String | | Maybe<String> |
| Fn1<Int,Int> ~~~~ map ~~~~> Fn1<Maybe<Integer>,Maybe<Integer>> |
| Fn1<Int,String> ~~~~ map ~~~~> Fn1<Maybe<Integer>,Maybe<String>> |
'------------------' '--------------------------------------'
In Java, we can implement Maybe
as a single class that
abstracts over Just
and Nothing
:
public class Maybe<A> implements Functor<A,Maybe<?>> {
private final A a;
private Maybe(A _a) {
= _a;
a }
public <B> Maybe<B> map(Fn1<A,B> f) {
if (a == null) return nothing();
else return just(f.apply(a));
}
public String toString() {
if (a == null) return "nothing";
else return "just(" + a.toString() + ")";
}
public static <A> Maybe<A> just(A a) {
return new Maybe<A>(a);
}
public static <A> Maybe<A> nothing() {
return new Maybe<A>(null);
}
}
We can try it out on some simple lambdas:
System.out.println(
.just(1)
Maybe.map((x) -> x + 20)
.map((x) -> x * 2)
); // just(42)
System.out.println(
.<Integer>nothing()
Maybe.map((x) -> x + 20)
.map((x) -> x * 2)
); // nothing
The expression (x) -> x + 20
is syntatic sugar in
Java 8 for a Fn1<Integer,Integer>
instance, since it
is a class with exactly one method:
new Fn1<Integer,Integer>() {
public Integer apply(Integer x) {
return x + 20;
}
}
When using map
on just(1)
, we start with an
instance of type Maybe<Integer>
and apply the
function (x) -> x + 20
of type
Fn1<Int,Int>
, resulting in an instance of type
Maybe<Integer>
whose value a
is
21
.
When we then use map
to apply the function
(x) -> x * 2
, we end up with a
Maybe<Integer>
whose value a
is
42
.
Since Maybe<A>
implements a method
<B> Maybe<B> map(Fn1<A,B> f)
,
Maybe
is a functor.
In other languages, a List
is a box that contains zero
or more values in a particular order. Like Maybe
, it has
two implementations: Cons
, which contains both a value of a
given type and a subsequent List
, and Nil
,
which contains neither a value nor a subsequent List
.
If we imagine that List
represents the category of lists
of values, we can see that it is also a functor. Here's how it
looks:
.------------------. .------------------------------------.
| Category * | | Category List<*> |
|------------------| |------------------------------------|
| Int | | List<Integer> |
| String | | List<String> |
| Fn1<Int,Int> ~~~~ map ~~~~> Fn1<List<Integer>,List<Integer>> |
| Fn1<Int,String> ~~~~ map ~~~~> Fn1<List<Integer>,List<String>> |
'------------------' '------------------------------------'
In Java, we can implement List
as a single class that
abstracts over Cons
and Nil
:
public class List<A> implements Functor<A,List<?>> {
private final A h;
private final List<A> t;
private List(A _h, List<A> _t) {
= _h;
h = _t;
t }
public <B> List<B> map(Fn1<A,B> f) {
if (h == null) return nil();
else if (t == null) return cons(f.apply(h), null);
else return cons(f.apply(h), t.map(f));
}
public String toString() {
if (h == null) return "nil";
else if (t == null) return "cons(" + h.toString() + ", nil)";
else return "cons(" + h.toString() + ", " + t.toString() + ")";
}
public static <A> List<A> cons(A h, List<A> t) {
return new List<A>(h, t);
}
public static <A> List<A> nil() {
return new List<A>(null, null);
}
}
As before, we can try it out on some simple lambdas:
System.out.println(
List.cons(1, List.cons(1, List.cons(2, List.cons(3, List.nil()))))
.map((x) -> x + 20)
.map((x) -> x * 2)
); // cons(42, cons(42, cons(44, cons(46, nil))))
System.out.println(
List.<Integer>nil()
.map((x) -> x + 20)
.map((x) -> x * 2)
); // nil
When using map
on cons(1, ...)
, we start
with an instance of type List<Integer>
, apply the
function (x) -> x + 20
of type
Fn1<Int,Int>
, resulting in an instance of type
List<Integer>
representing
[21, 21, 22, 23]
.
When we then use map
to apply the function
(x) -> x * 2
, we end up with a
List<Integer>
representing
[42, 42, 44, 46]
.
Since List<A>
implements a method
<B> List<B> map(Fn1<A,B> f)
,
List
is a functor.
Though Java's built-in List
interface doesn't extend the
Functor
interface, it's easy to write a simple wrapper that
gets us most of the way there.
public class ListFunctor<A> implements Functor<A,ListFunctor<?>> {
public final java.util.List<A> l;
public ListFunctor(java.util.List<A> _l) {
= _l;
l }
public <B> ListFunctor<B> map(Fn1<A,B> f) {
.util.List<B> bs = new java.util.ArrayList<B>();
javafor (A a : l) {
.add(f.apply(a));
bs}
return new ListFunctor<B>(bs);
}
public String toString() {
return l.toString();
}
}
We can use this in a similar fashion to our List
implementation:
System.out.println(
new ListFunctor<Integer>(java.util.Arrays.asList(1,1,2,3))
.map((x) -> x + 20)
.map((x) -> x * 2)
); // [42, 42, 44, 46]
System.out.println(
new ListFunctor<Integer>(new java.util.LinkedList<Integer>())
.map((x) -> x + 20)
.map((x) -> x * 2)
); // []
Since ListFunctor<A>
implements a method
<B> ListFunctor<B> map(Fn1<A,B> f)
,
ListFunctor
is a functor.