A functor has three things:
1. A type constructor
2. A "map" function
3. A "flatten" function
So basically it is just a parametric type such as List<T> which has a type constructor so you can get a concrete type (eg List<String>), a map function which takes a function f: A => B and and turns it into a function List<A> => List<B>, and a "flatten" function with will turn a List<List<A>> into a List<A>.
The last part is what allows "flatMap" which takes a function f: A => List<B> and turns it into a function List<A> => List<B> and is really just a shorthand for doing map and then flatten.
A functor is a type constructor with a map operation (that obeys composition and identity), similar to how a group is a set with an operation. (And similarly, we casually talk about the type as though it were the functor, just as we talk about the set as though it were the group; if someone says "the Option functor" that's a slight abuse of notation in the same way as "the group of integers").
In particular, a functor is a type constructor F together with a higher-order function deriving transformations `F T -> F S` given a transformation `T -> S`, subject to some semantic requirements. This is the `map` or `fmap` people refer to as defining the functor.
Unfortunately, due to abuse of notation, the type constructor isn't given much focus. But it's true that "type constructor" is the first conceptual hurdle.
You asked. I'm happy to dissect it to your level, but I don't know what you may be familiar with, and if you're not comfortable with type functions, I'm going to have a hard time motivating the extra bits a functor has.
The List functor is a combination of the type function sending `T` to `List<T>` and the ... what do you want me to call it, a function function? implemented in Java as:
static <T, S> Function<List<T>, List<S>> map(Function<T, S> f) {
return (ts) -> {
var ss = new ArrayList<S>();
for (final var t : ts) ss.add(f.apply(t));
return ss;
};
}
We call it as map(f).apply(ts). If we want to pass them both at once, we can rewrite the function so that it's not static, but it doesn't much change that it's a mapping operation.
But it's not the `map` method that's the important part, so much as the idea that we can (or want to; can't in Java) pass `List` to any function that needs a Functor, which can then use whatever `map` implementation that functor has, without knowing what actual type function it was given.
Really, I suspect it's neither the type constructor nor the map function that's the conceptual hurdle. It's abstracting over the type constructor; taking a type constructor as a parameter. You may have never used a language that supports that, or seen a need for it, and this may all seem like needless sophistry until you do.
I might get flack from the FP purist crowd, but I like to think of functors as containers + context.
- 5 is a value. Its type is int
- int is a type
- T is a type parameter. Like the x in "f(x)", we have to pass one in to evaluate it
- List<T> is a type constructor. It takes a type, T, and spits out a new, "compound" type. It will "contain" T's.
- [3,5,7] is a list. Its type is List<int>. We fed the type "int" to List<T> to construct a new type
- List<T> is a functor because it "contains" T's. List<int> "contains" ints.
- F<T> -> () (a function which takes a T and returns nothing) is a type constructor. It's not really a functor. There's ways in which it technically can be (e.g. decorators in python) but for the sake of pedagogy and giving a counterexample, I'm going to say it's not, because you usually aren't going to map over something like that.
- because functors "contain" other values, you can apply a function to the contents, without changing the container context. This is called map. It may change types, eg mapping sqrt over a list of ints could give floats. But it always gives the same "container type"
The tricky bits:
- To be a true blue functor, there has to exist an identity function that is a no-op and gives you the same types and values back. You needn't define it, it just has to be possible to define.
- functors need not actually "contain" anything, nor the contained value be primitive data. But they always have this wrapper-like feel to them, with an outer type, an inner type, some context/data/value/computation, and the ability to map over that inner value. E.g. Optional<T> could contain nothing, but you can still map over it.
- it's not necessary to be able to dereference or "dispense" the contained value. Sometimes, like the IO monad pattern, the inner value gets "stuck". it never leaves the IO, it's only ever (flat)mapped over.
- the inner value can be: nothing, a single datum, a collection of data, a function, a computation, another functor, another type constructor...almost anything you could assign to a variable.
- well-known functors include: List<T>, Dict<K,V>, Optional<T>, Result<T,E>, Future<T>, Generator<T>, IO<T>, Tree<T>. T* (pointer to a T). Virtually all container types.
I like your approach. However, I don't think that this:
- List<T> is a functor because it "contains" T's. List<int> "contains" ints.
Is really correct. I believe a `Container<T>` becomes a functor only if it also 'has' (can have?) a function that can take a function and apply it to all values in the 'container'. So, a 'map' of some sort.
I mean, I see your explanation of 'map' later on. It's also probably true that in real world software engineering contexts any 'container type' of that kind would also be one that either has or can naturally have a `map'. It's just that if someone willing to understand this read your comment and went: "Aha! Some container thing is a functor because it contains things!" I think they'd gain incorrect understanding.
I have pretty much the same intuition, except I think of functors not just as containers, but as sources of T. If you have a source of Ts, you can adapt it with a function from T to S to get a source of Ss. If you want to apply a pipeline of type-changing operations to some source of initially Ts, a functor is the right metaphor. (And if you have a sink instead of a source, that's a contrafunctor.)
If you have two sources and you want to combine them into a single source, you need an Applicative Functor, also known as a monoidal functor.
If you have a source that itself produces sources, and you want to flatten the nesting and treat it as a single-level source, you need a Monad.
> F<T> -> () (a function which takes a T and returns nothing) is a type constructor. It's not really a functor.
I'm having a little trouble matching the prose against the type signature. A function which takes a T and returns nothing would have type `T -> ()`; no F in sight. I'm guessing you meant that F<T> is defined to give `T -> ()`, in which case F is indeed not a functor; it's a contrafunctor, a place to which Ts can be sent (not retrieved).
So why can't we just call the damn things 'Type constructors'?