- 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.
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
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
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
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
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.
• 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
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
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
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
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
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
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.
Bool that don’t have any type parameters, are concrete types, represented in the kind system by a single star:
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
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
(,) 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
(,) 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.
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
Let’s remind ourselves what
mapToMaybe looked like.
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
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
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
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 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
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
Profunctor. A type must be a
Functor before it can be
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
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
We note that the list type has only one type parameter, so it meets our criterion for being “like
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.