- 32 minutes

Welcome back! This lesson is going to combine some of the stuff we’ve worked on in the last couple of lessons, leading to the next and final lesson where we bring a lot of this stuff together into one exciting thing at the end.

Applying functions to values to produce new values is the most fundamental act of programming there is, and it’s what a lambda calculus like Haskell is centered around. However, in any nontrivial Haskell program, you find yourself dealing with values that are embedded or contained in some other type. You still need a way to apply functions to those values, despite the fact that they are hidden within some other type structure. In this lesson, we’ll look at an example, write a function that solves that problem for us, and then begin discussing how to generalize it.

## Maybe a

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.

`lookup :: Eq a => a -> [(a, b)] -> Maybe b`

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 `Integer`

s 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.

## Maybe map

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.

```
• Found hole:
_ :: ([Char] -> [Char]) -> Maybe [Char] -> Maybe [Char]
• In the expression: _
In the expression: _ ("Hello, " ++) (lookup record database)
In an equation for ‘greetUser’: greetUser record = _ ("Hello, " ++) (lookup record database)
```

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.

`_ :: (String -> String) -> Maybe String -> Maybe String`

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:

`_ :: (String -> String) -> (Maybe String -> Maybe String)`

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 `String`

s, then we could use that function. But what we have instead are `String`

s 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`

”:

`generalMap :: (a -> b) -> (f a -> f b)`

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.

## Higher kindedness

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 (,) _
(,) _ :: * -> *
```

## Either map

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.

`mapToEither :: (a -> b) -> Either _ a -> Either _ b`

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?

## Naming the 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 `P`

It’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"
```

## Other functors

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.

## List map

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`

”.

`data [] a = [] | a : [a]`

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.