Functor

We’ll begin with an example. This example will be a simplified version of what a real-world Haskell function to do this task might look like, simplified just enough to allow us to focus on the points we care about.

We need a function that can look up a user record and greet the user when they log in. We can make a simplified model of our “user database” with an association list – that is, a list of tuples.

We find that the Prelude has a function available for looking up a value in an association list.

The lookup function is going to take one argument of the same type as our “key”, and so that type needs to be a member of the Eq typeclass because it needs to be able to tell that an a value that we input is equal (or not) to some a value in the association list. Our a values are Integers according to the type we have given our database, and you can check to make sure those have an Eq instance.

The second argument to lookup is a list of tuples – which will, in this case, be our database – and it will return a Maybe b value. That is, if it finds a record with the given key, it will return the String value that is associated with that key, wrapped in a Just. If it doesn’t find a record with that key, it will return Nothing.

Load the file with the database list into your REPL so we can try it out.

λ> lookup 2 database
Just "Chris"

λ> lookup 5 database
Nothing

Using Nothing rather than throwing an exception when there is no value at that location is nice, but it leaves us with the problem of how to apply a function to whatever value we might retrieve. Let’s say, for example, that we want to greet the user whose record is at that location, so we plan to concatenate a greeting with their name. We want something like this:

This won’t compile because the second argument of the ++ function must be a String and we’ve given it a Maybe String. So, we need to invent something that can work around the Maybe constructor somehow.

We can try getting the compiler to tell usWe’ve used underscores previously in this course as “catchalls” for parameters and for cases inside a case statement; in a pattern context, an underscore is a pattern match for anything, so we can use it for any parameter we don’t care to name or a case that will match anything. Whether the compiler interprets an underscores as a typed hole or a catchall parameter or case depends on where the underscore is located. You can read more about it in the article on underscore. what we need to invent by using a typed hole. A typed hole is a hole we leave in the function implementation for the purpose of provoking the compiler into telling us how to fill the hole.

We represent the hole with an underscore:

When we compile this or load it into the REPL, GHC will helpfully infer the type of the underscore at the beginning of line 3.

It will also give a list of suggestions, functions that the compiler knows about that could fill in the blank. We’ll ignore this, however, and write our own. We now know its type.

We may note, as we did with our map function over lists in a previous lesson, that we could add another set of parentheses to this type signature with no change in meaning, like this:

We don’t usually put these parentheses in because we don’t need themHaskell is what is called “curried by default.” In Haskell, there are no multiple-argument functions; all functions in Haskell take one argument and return one result. Currying refers to turning a function that takes multiple arguments into a series of functions that each take one argument, and this is the default for Haskell. Hence, parentheses making that currying explicit are not necessary in Haskell, but sometimes they help the human reader parse or scan type signatures., but sometimes it’s a helpful reminder of what we’re trying to accomplish.

So, what we’re doing is turning a String -> String function into a Maybe String -> Maybe String function. We’ll call it mapToMaybe and try to implement it. Since Maybe has two possible values, we’ll need to consider both possibilities in our implementation. If the Maybe value is Nothing, we do nothing; if the value is a Just <string>, then we apply the String -> String function to that string value.You could also write this with the case syntax we’ve been using throughout the course; there is no special reason we chose this syntax here, except to show you another style.

Notice that to apply the String -> String function to the Just <string> value, we pattern match on the Just which gives us access to that string value, in a similar fashion as when we deconstruct a list parameter into (x:xs) in order to access the list’s contents. Then we apply the function to the string value, and then rewrap it in a Just.

Now we can fill in our typed hole with our brand new function and everything should work.

λ> greetUser 3
Just "Hello, Alonzo"

λ> greetUser 5
Nothing

This works for our current purpose, but it’s very specific: it can only work with String -> String functions, and we can certainly imagine other use cases for a function that can reach inside that Just constructor for us and transform the value. Rewriting it to work for any a -> b function instead of only String -> String functions doesn’t require big changes.

Let’s take a look at what’s going on here.

We have a function that can concatenate two strings, so if our names were bare Strings, then we could use that function. But what we have instead are Strings in some extra context, a context that tells us we might sometimes have failed to retrieve a string. So we need to map, or lift, our String -> String function to a Maybe String -> Maybe String function, which will preserve the pure function application aspects of the original function while also dealing with the possibility that we may, sometimes, have no value to apply a function to.

This is very satisfying; we can reuse this a lot. But what if a later refactor means we stop using Maybe and start using Either or some other type? Can we generalize this beyond Maybe?

This is Haskell, so the answer is usually yes, we can nearly always generalize further. However, there are some catches. Let’s try to imagine that we want to reimplement this function more generally, giving us a type like this, using a polymorphic type variable that we’ll call f to represent “some type like Maybe”:

But, as we saw above, the implementation needs to deal with the different possibilities – if we have a Nothing or a Left value, we should have a different result than if we have a Just or a Right.Either is another sum type with two possible cases: data Either a b = Left a | Right b. How do we give a general implementation for that? And what does it mean for a type to be like Maybe, in a way that is relevant to this function?

We can answer the first question quickly, and tackle the second question in the next section. The question of how we write different implementations of the same very general, very polymorphic function, is the question of how we handle overloading. In Haskell, in general, we handle that with typeclasses and instances. So, what we really need to do is figure out what “types like Maybe” means.

There are different ways that a type could be like Maybe and we need to only figure out the ways that are relevant to this particular function that we’re trying to implement. We can’t tell necessarily if the type must be a sum type like Maybe, whether it must have some “failure” sort of case, or not. The thing that seems most relevant is the fact that it contains one type – not zero, not two or more. The function from a to b only takes a single argument, a, so we can only apply it to one value. That suggests that a “type like Maybe” for our current purpose must be a type constructor with one type parameter.

We call the “types of types” kinds, and we call parameterized type constructors higher kinded, or sometimes HKTs for “higher-kinded types”. You can think of these as type-level functions, and we can see this for ourselves by querying the kind of a type in the REPL, just as we might query the type of a value.

Types, like Char or Bool that don’t have any type parameters, are concrete types, represented in the kind system by a single star:* or Type is not technically the only kind of types in GHC Haskell, but it’s the only one we need to care about here – also the only one you need to care about most of the rest of the time.

λ> :kind Char
Char :: *

λ> :kind Bool
Bool :: *

While we use types for classifying and organizing data, the primary role of kinds is to talk about the arity of a type constructor.Kinds do serve another purpose in talking about types, in that there are different kinds for lifted and unlifted types, for example. Lifted types are those that have the possibility of bottom inherent in them; unlifted types are primitive machine types that have no possibility of being thunked or being bottom. In practice, you do not often deal with kinds other than * or Type, but it’s not impossible, and in that sense kinds do play a similar classification role as types themselves.

Parameterized type constructors are represented as functions from types to types (or, stars to stars). When they have one type parameter, they are a unary function, from star to star.

λ> :kind Maybe
Maybe :: * -> *

λ> :kind []
[] :: * -> *

Notice that as soon as we apply to them to a type argument, even if it is a wildcard (represented by an underscore), they are represented as concrete types; when a lambda has been applied to all the arguments it is binding, it’s not a function anymore.

λ> :kind Maybe String
Maybe String :: *

λ> :kind [] Char
[] Char :: *

λ> :kind Maybe _
Maybe _ :: *

And type constructors that take two parameters are binary functions. We haven’t talked too much about such type constructors in this course yet, but let’s look at a couple of examples.

λ> :kind (,)
(,) :: * -> * -> *

λ> :kind Either
Either :: * -> * -> *

That might at first indicate that types like Either and (,) can’t be “like Maybe” in the relevant sense for us, but one thing we know about functions is that they are curried by default and can be partially applied. This holds true as well for type-level functions. We can turn Either or (,) into a type constructor awaiting a single type argument by partially applying it.

λ> :kind Either String
Either String :: * -> *

λ> :kind (,) _
(,) _ :: * -> *

Any of these can therefore contain a single type for us to apply our a -> b function to. Earlier we wrote a mapToMaybe. Now we’ll write the analogous mapToEither function. The type will have to look something like this.

We wouldn’t actually be able to use the underscores in a type, but it serves as a temporary visual reminder that we’ve applied the Either constructor to something in order to write this, so that we can see that the a that our (a -> b) function will apply to is in the Right constructor, just like it’s in the Just constructor of Maybe.

Let’s remind ourselves what mapToMaybe looked like.

Partially-applied Either has the same number of parameters that we can transform via function application as Maybe does, so our implementation here will look a lot like mapToMaybe. That means the first case of our function that handles Left values will be very similar to the Nothing case for Maybe.

As far as this function is concerned, there is no value to apply a function to, so all we can do is return the Left values. Whatever value it holds is tied up as part of what we’ve been calling the type context.

The case for handling Right valuesIt is ok for your variables to be entire words, even when they are type-level variables, so long as they are not capitalized. Anything capitalized at the type level is the name of a particular type or type constructor, not a variable. will look very similar to the case for handling Just values in mapToMaybe. To make it compile, we have to give a name to the type argument we had been representing with an underscore; it doesn’t matter what, but we like to make it something that reminds us visually still that it’s different from the one we’re applying the function to.

We can write a valid implementation of this function for most sum types then, no matter how many cases or type parameters (as long as there is at least one) that they have. If they have more than one parameter, then the type constructor can be partially applied to make them “like Maybe” in this way, in their kindedness. We’ve been calling them map functions because that’s what they do.

Functions map values from one set to values of another, and this function maps one set of functions – (a -> b) functions – to another set of functions whether they are Maybe a -> Maybe b functions or Either _ a -> Either _ b functions or some other context that we had earlier generalized as f. We may also refer to this mapping as lifting, in the sense that these functions lift an a -> b function into some new type context.

As we suggested, very briefly, with tuples, it’s not only sum types that you can write such a function for, and unfortunately we’re not going to have much time in this course to get into those. For now, let’s work with the assumption that there are a sufficient number of such types that do form a class, a set of types that can all have sensible, law-abidingWe will not get to the laws in this course, but they are covered in some depth in the Functortown course. implementations of this function. We’ll have a typeclass, then, and a set of instances that uniquely pair a type name with the correct implementation. What do we call this class?

A long time ago, the logician Rudolf Carnap coined the term functor to describe function words in languages. Function words have little to no semantic content of their own so they don’t change the meaning of a proposition. Some such function words take a sentence as input and produce another sentence as output, and the output sentence has a somewhat different context. For example, we can take a proposition P and attach to it the functor, not and produce not P. It doesn’t change the meaning or structure of PIt’s true that adding or removing negation and other function words from actual sentences can change their phonetic and syntactic representations, which can be said to change the “structure” but not in the way that Carnap cared about. itself, but it changes the context and affects the truth value. Other linguistic functors indicate various grammatical relations, such as conjunction. P && Q is a different proposition from either P or Q, with a different truth value, but it doesn’t change the meaning of either statement.

It happens that mathematicians then borrowed this word functor from Carnap for describing mappings between two categories. We need not belabor this point, but a category is a structure that has objects linked by “arrows,” also called morphisms. A functor maps one category to another, preserving the relationships between the objects and morphisms. Categories are abstract enough that it can be a little difficult to wrap your head around exactly what this means or why you’d care, but thankfully we can focus on something a little more concrete.

One example of a category is the category of sets; the objects in this category are sets and the arrows linking them are functions. That most closely maps to the “category” we’re concerned with when writing Haskell, the category (often called “Hask”) that contains types and functions between types. In this context, then, a functor is a law-abiding mapping between two types. In particular, it refers to just what we did above, lifting a function entirely into a new context.Since all the types in Haskell are in one category, these are technically endofunctors – that is, functors that map a category to itself – and you may sometimes hear that word. In Haskell, the word “functor” is also used to refer to type constructors for which we can write such a function

And this is how the class that we found ourselves in need of came to be called the Functor class, and its method, the one we wrote above first as mapToMaybe and then mapToEither is called fmap. fmap has little semantic content on its own: all it does is change the context.

The definition of the Functor class looks like this:Note that this class definition, as it is written here, requires the KindSignatures GHC language extension.

Notice the class definition tells us that f must be a unary type constructor.

We could now change our greeting function from the first section to use fmap.

And if we do that, then we won’t have to worry about changing the type to Either somewhere down the road; the compiler will change which implementation of fmap it uses but you can rely on it behaving the way you expect. That’s one of the reasons that we keep saying that typeclass instances are supposed to be law-abiding, to avoid nasty surprises if the types change.

Let’s reload this into our REPL and check that everything is still working.

λ> greetUser 1
Just "Hello, Julie"

We use the word “functor” to refer to type constructors that meet certain criteria. Most often, what we mean is a type constructor that has a sensible instance of the Functor class. But fmap isn’t the only mapping between types that exists. Other functorial typeclasses include Applicative, Monad, Bifunctor, Contravariant, and Profunctor. A type must be a Functor before it can be Applicative or Monad, although that isn’t true of all of these classes.

Why then should the Functor class get to have that name, when there are other functors and not all of them even require the type to be an instance of Functor? As you will see as you work through understanding each typeclass in its turn, the basic idea of fmap in some form or another is the foundation of all the other mappings, so having understood this one in detail provides a key to understanding all the others.

You may remember the list function, map, that we spent some time on earlier in this course.

Let’s compare the types of map and fmap and see if they look similar.

λ> :type map
map :: (a -> b) -> [a] -> [b]

λ> :type fmap
fmap :: Functor f => (a -> b) -> f a -> f b

The list type is a functor, and map is a version of fmap specialized to lists. This map function lifts an a -> b function to being a “list of a to list of b” function.

We note that the list type has only one type parameter, so it meets our criterion for being “like Maybe”.

We saw earlier that it has the correct kindedness. It is recursively defined, so there can be infinitely many values of type a in the list, but what matters for fmap purposes is the number of type arguments, not the number of values at the term-level. List is also an applicative functor and a monad, although the next (and final!) lesson on monads won’t discuss lists as such.