What does a functor actually look like in various programming languages? We already said it’s something you can use to map, so let’s take a look at some language’s mapping functions:

• Clojure has map, mapv and fnil
• Haskell has map and fmap. (It also has <$>, which is the same as fmap)
• C# has Select
• Java’s streams library has map and mapToInt

So, are any of these functor mapping operations? Well, it won’t take a genius to guess that fmap does the right thing. map in Haskell does the same thing, but only works for Lists. The definition of fmap for list is map, so it’s pretty much a wash. (*)

Land of Compromises

The others? Well, kind of, but you tend to need to squint a bit. The problem is that if you map over an identity function, (e.g. x => x in C#) you should get the same type back as you put in. And actually, that’s very rarely true. map in Clojure can be called on a vector and will return a lazy list. mapv can be called on a lazy list and get back a vector. map in Java and Select in C# send an interface type to the same interface type, but rarely return the exact same type as you were expecting.

Moreover, there isn’t a general mapping interface that lots of functor-like things implement and there isn’t any way to make one. This isn’t a problem for list comprehension, but it horribly breaks functors as a general model of computation. (#) You can still use the concepts, but you’ll end up with a lot of code duplication. Indeed, you’ll probably already have this code duplication and be thinking of it as a pattern. As is all to often the case, low level programming patterns reveal deficiencies in your programming language.

There’s good reasons for these mapping functions not behaving exactly like a functor, though: performance. The haskell compiler has everything, not just lists, as lazy and can optimize types away. Clojure, C# and Java can’t and treat them as hard optimization boundaries.

Haskell ain’t perfect either

We already established in the previous article that there are plenty of functors that have nothing to do with types. Haskell’s Functor type class is therefore only a functor on the category of Haskell types (usually referred to as Hask). This seems good enough, but actually it isn’t.

Consider a set of values. You can easily define a mapping function that satisfies the functor rules. Sadly, Set in Haskell isn’t a Haskell Functor. This is because Set imposes a condition on its values that they be sortable. Whilst this isn’t a problem for real Functor’s, it’s a problem for Haskell functors because type classes don’t admit restrictions on their type parameters. To put it another way, Functor in Haskell is a functor over the whole of Hask, never a subcategory. For that matter, you can’t do the (*2) functor that I described last time in any sensible way because you can’t restrict its action to integers.

It turns out this problem is fixable, with Rank-2 typeclasses, but don’t hold your breath for that to land in Prelude any time soon. In the meantime, you can’t use Functor to represent functors with domain type restrictions.

(*) Many smart Haskellers believe (and I agree with them(+)) map should work on all functors and fmap should be retired. There’s a general theme here: the standard libraries are showing their age and need work to simplify them.

(+) If you’ve never seen Alan Rickman play Obadiah Slope, you’re missing out.

(#) If you’re prepared to lose information, all you really need is reduce/Foldable anyway.

Functors : Category Theory Stuff

If you ever want to talk the same language as smart Haskellers, you need to know a bit of category theory. Here’s some notes on how I understand category theory right now.

The first thing to to appreciate is a list isn’t a functor, “list” is a functor. In particular, it’s a mapping from one type to another e.g. int to list of int. Furthermore, it’s a mapping that preserves the structure of int, in that performing “map” works.

Considered this way, there’s no such thing as a “higher order type”, there’s just functions from one type to another. Types with more than one type parameter in Java/C# are just multiple arity functions on types.

Some other things that are worth considering: you can make a list of any type, even a list. Not only that, but if a and b are different types, list of a and list of b are different as well. So, in maths terms, it’s an injection of the type space onto a subsection of the same type space.

What the heck is a category?

Now, let’s go back to the start and talk terminology. A category is a bunch of “objects” and “arrows” between them. They behave basically like values and functions. Indeed, values and functions form a category. The only real requirement is that arrows compose like functions and that there’s an identity map that does nothing.

In the context of type theory, the objects are the types themselves. The arrows are higher order type constructors. Just like normal functions, they’re not reversible. Now let’s make a bit weirder. Just the lists and the functions between lists and other lists form a category too.

The next bit may or may not make sense if you don’t have a maths background. Mathematically, a functor isn’t anything to do with types at all, it’s just a mapping between one category and another that preserves some structure.

Wait what?

Let’s think of a really simple category. Let’s have the objects be integers and the arrows be rotations of integers e.g. add three, subtract two. And “add zero” is an identity map.

Now let’s have another one which is the same, only all of the numbers and rotations are even. Then “times two” maps objects and functions between the two categories. So 3 becomes 6 and “add 3” maps to “add 6”. And finally, “add zero” becomes… “add zero”. So “times two” is a perfectly valid functor that is absolutely nothing to do type theory at all.

Finally, a small note, if you’re just looking at category theory for the purposes of understanding Haskell you’ll come across the phrase “locally small” a lot. Every last category you are ever going to worry about is locally small, so don’t sweat it.

One of the things that people new to Haskell may not appreciate is that academia’s love affair with monads has been waning for some time. In its place is a more nuanced hierarchy of Functor, Applicative, Monad. (*)

So what the heck is a functor? Well, really it’s just something you can map over and it makes sense. “Makes sense” has a specific mathematical meaning, but I’m going to gloss over it and keep going.

Let’s talk about some things you can map over:

• A list, [a]
• A set, Set a
• A nullable value, Maybe a
• A random value, Rand StdGen a
• A function returning a value, (->) a
• A program returning a value, IO a (We’ll ignore this one from now on, I’m just mentioning it because IO is kind of important.)
• A record, where we only map over one of the fields. e.g. imagine a pair (x,y) where x and y are different types

So, if you were mapping “add one” you’d get

• A list where all of the values were one larger e.g. [2,4] becomes [3,5]
• A set where all of the values were one larger e.g. #(2,4) becomes #(3,5).
• A value one larger, or null. So null becomes null, and 3 becomes 4.
• A random integer value between 1 and 6 becomes a random integer value between 2 and 7.
• A function f(x) becomes a function g(x) where g(x) = f(x) + 1
• The pair (x,y) becomes (f(x),y)

I’ve found that while getting your head around the concept, it’s best to just concentrate on nullable values and lists. In particular, if you’re familiar with Clojure or LINQ, it’s about understanding that things like nil-punning and fnil are exactly the same concept as map and behave the same way.

Just to complicate matters, the set example doesn’t actually work in Haskell, but I’ll get to that in a later post.

My Head is Hurting

If you want to learn the stuff I’m saying properly, go do Brent Yorgey’s Introductory Haskell course and do the exercises. It’s a significant time investment, but well worth it.

(*) This is a gross over-simplification, so sue me.