A key feature of programming languages is their capability for designing abstractions. Most imperative languages support functions, and you may be familiar with a few that support more advanced abstractions, such as macros in Lisp or classes in most popular modern languages.

Though languages will have some abstractions as language features, abstractions are occasionally encoded as social constructs, often called "design patterns". Although they aren’t a fundamental part of programming language, things such as factories (common in Java), visitor patterns, thread pools, and client-server request-response communication protocols are all design patterns just as much as functions or classes.

In mathematics, abstraction takes on a slightly different meaning. Abstract mathematics relies on defining simple objects and a few axioms that relate them, and seeing what sort of results these axioms yield. (An axiom is simply a fact taken for granted, something that is assumed to be true without proof.) For instance, an important mathematical abstraction is the group:

Mathematical abstractions have a tendency to be very general, and can be hard to apply to real-world scenarios and data. With the example above, how could we use a group structure in our software? Without a more concrete application, that abstraction is hard to utilize. On the other hand, traditional abstractions in software are straight-forward to apply, but can be hard to analyze rigorously. We get very few theoretical guarantees simply by knowing that some class implements the visitor pattern.

While the standard style of abstractions can be used in Haskell (and often are), we often prefer to use more rigorously defined mathematical abstractions. We represent these abstracts through a typeclass along with a set of laws that well-behaved instances must obey. (The language does not and cannot verify that the laws are followed, so whenever you write an instance of a typeclass with a set of associated laws, it is up to you to verify that the laws hold. The community tends to quickly point out invalid instances if they are in published libraries.)

The group abstraction above might be defined as the following typeclass:

Whenever we wrote an instance for this class, we would want to verify that the following laws hold:

The laws above are not valid Haskell, but are just a way to express the laws that relate to our Group typeclass.

The abstraction of a group turns out not to be very useful in Haskell, so we won’t spend any more time on it; it’s served us well as an example, and is no longer useful to us. Note that although that particular abstraction isn’t useful, the style in which we defined it (as a typeclass with some laws) is common throughout the Haskell ecosystem. With that in mind, let’s spend the rest of this guide looking at some useful abstractions that Haskell programmers use every day.

The first abstraction we’d look to look at is fairly similar to the Group example, but somewhat more restricted. Like before, we’d like to generalize a notion of combining different elements using some sort of addition. For instance, we can combine numbers using + and we can combine lists and String s using ++. However, while numbers have inverses (so we could make them a Group), there’s certainly no notion of an inverse for strings or lists. To simplify our life, we can get rid of the requirement for an inverse.

The resulting algebraic structure is called a monoid:

This definition is similar to the definition of a group; all we’ve done is removed one requirement! The typeclass looks pretty familiar, too:

As usual, this abstraction comes with a set of laws, corresponding to the items in the mathematical definition above. We use the operator <>, which is just an infix alias for mappend.

The value of the monoid abstraction comes from its wide applicability, so let’s take a look at some examples. The most obvious instance would be one for numbers:

This instance, while tempting, has a number of problems (no pun intended). The main semantic one is that that’s not the only way to define a monoid over numbers! For example, we could also try to define something like this:

The other slightly more technical issue with both of the instances above is that they create an opportunity to seriously confuse the Haskell type system. If you try to define these instances, you’ll get an error message complaining about UndecidableInstances.

In order to solve both of these issues, we can wrap the number in a semantically-meaningful newtype. We’ll create two new types – one called Sum for the monoid under addition, and another called Product for the monoid under multiplication.

With instances like these, we can write a general "sum" function to combine a list of monoids.

We can use this as a sum or a product by wrapping our values in the Sum or Product constructor:

The pattern of using newtype s to distinguish between monoids is fairly common, because for many data types there are multiple ways to interpret them as a monoid. For instance, for the Bool type we can interpret the binary operation <> as either an "and" or an "or", which yield the All and Any monoids, respectively:

The all and any functions can then be implemented very similarly to the sum and product functions above.

Yet another instance of this pattern (once more, no pun intended) is the First and Last monoids. These extract values from a list of Maybe values; as their names may suggest, they extract the first Just values and the last Just values encountered.

The instance implementation is left as an exercise to the reader. In both cases, the identity should be Nothing. In the First case, mappend should keep the left-most Just result it sees, whereas in the Last case, it should keep the right-most Just result.

Not all monoids fit this newtype ing pattern. For example, an incredible useful monoid instance is the one for the Ordering data type, implemented as follows:

This monoid allows us to easily write comparator functions. For instance, suppose we had a type representing someone’s name:

If we wanted to implement an ordering on names that sorted first on last names, then first names, then middle names, we could easily implement such an ordering:

Recall that the function compare :: a -> a -> Ordering is necessary for implementing the Ord typeclass, and that we already have an Ord implementation (and thus a compare function) for String s. Using the String compare and the Monoid instance for Ordering, we can easily write the lexicographic ordering for our Name data type.

The last monoid we’ll look at is the [a] monoid. This instance can be constructed almost trivially using the empty list and ++. however, this monoid has an interesting property. Although it has a somewhat special syntax, [] is actually a type constructor (similar to Maybe). [] takes any type a and spits out a valid Monoid. For this reason, the list type [a] is referred to as the free monoid – we get it for free for any type a, without any extra effort on our part. Although this is fairly uninteresting for monoids, we’ll see later that other algebraic structures also admit free variants which are somewhat harder to derive but can be used with great effect.

In the previous section, we started off our study of abstraction in Haskell with the concept of a monoid, which was, roughly speaking, a type of thing that you can combine together. In this section, we’ll get some more practice with Haskell-style abstract thinking by discussing yet another abstraction used by Haskell programmers on a daily basis.

Recall the map function, which applies a function to every element of a list:

What makes lists special, though? Suppose we had a simple binary tree data structure:

We can define a function very similar to map for our Tree data structure. Let’s call it treeMap:

Indeed, we’re beginning to see a pattern! We often have a container (such as [a] or Tree a), and we’d like to apply some function of type a -> b to every element in the container.

What we’re looking at turns out to be a bit more abstract than just containers. In Haskell, this abstraction is known as the functor (a name which, like many things in Haskell, comes from category theory). The associated type class looks like this:

We’ve already seen two types that fit this pattern, namely lists and trees. We can provide an instance of each:

Note that we’re implementing a typeclass for Tree, not Tree a. Although Tree by itself is not a type (just something we can use to create a type, often called a type constructor), we can use it in typeclasses. In fact, if we look at the signature of fmap we see that it contains the types f a and f b, which means that whatever f is, it has to be a type constructor that takes exactly one argument.

So far, we’ve seen that we can create typeclasses that abstract over types (things like Maybe a and Int) as well as typeclasses that abstract over type constructors (like Maybe or Tree). Not only are these completely different things, but it would make no sense to mix them! Suppose we tried to implement a functor instance for Int:

In this case, fmap would have type fmap :: (a -> b) -> Int a -> Int b, which makes no sense (what is an Int a?).

In order to make sure that instances and types makes sense, Haskell has a kind system, which is effectively a type system on top of types (instead of on top of values). The kind system is a bit simpler, though, having only the following two rules:

While the first rule is fairly simple, the second can be a bit more difficult to parse. Kinds with -> act similarly to types with ->. A type with kind * -> is something that takes a concrete value type (such as Int) and yields another concrete value type. A good example of this would be Maybe – Maybe takes a type, such as Int, and yields a new value type, Maybe Int. Thus, Maybe on its own must have kind -> . By the same rules, we can determine that Either must have kind -> * -> *.

In the case of the Functor instance, we can tell by the signature fmap :: (a -> b) -> f a -> f b that the type f must have kind * -> , because the type f a appears as a real value (an argument to fmap) and must thus be of kind .

Before moving on, let’s look at a few more examples of functors to solidify our understanding. In order to write a Functor instance, we need a type of kind * -> * (a type constructor that takes on argument). One type constructor we’ve worked with a lot is Maybe, and indeed, this is one of the most common functor uses in Haskell. A Maybe value represents a value or computation that might have failed (and yielded Nothing). Coming from an imperative language, a Maybe a may be similar to a nullable a. In order to work with these failed or nullable values, we can use the following functor instance:

It turns out that this instance is incredibly useful for chaining together computations that work on something that might’ve failed. For instance, suppose we want to use the following lookup function:

Given a list like [(1, "Hello"), (2, "Bye")] we can use lookup to extract the first b associated with a given a:

Suppose we’d like to do a lookup, and then perform some other computations if it succeeds (for example, reverse the string and remove duplicate characters). One way to achieve this is through a case statement, using nub from the Data.List module:

Alternative, using our Functor instance for Maybe, we can write this very cleanly and succinctly with fmap:

We create a new function by composing nub and reverse, and then apply it inside the Maybe. Just like the case, this yields Nothing if the lookup fails, or a Just value if it succeeds.

Just like we have an instance for Maybe, we can create one for Either. Recall that the Either type is declared as follows:

Since it takes two type parameters, it must be of kind *+ -> +*+ -> +*. A Functor instance declaration for Either wouldn’t make sense, since Functor requires something of kind *+ -> +*. However, by supplying Either with one variable in the declaration, we can make it’s kind into *+ -> +*: just like you can curry Haskell functions, you can curry Haskell types. Thus, we can write the following instance

Note that by declaring the instance for Either a, we satisfy the requirement that the functor be something of kind * -> *. What this means is that the a is fixed throughout the fmap, so using fmap on something of type Either a b cannot change the a (but it can change the b). In this instance, the type of fmap is specialized to

Note that we have to change the name of the first type variable in Either a to Either c, in order to avoid conflicts with the a and b in a -> b.

Since many Haskell data structures have more than one the parameter, the trick of currying one type parameter and using the curried type to declare a functor is fairly common. For instance, we can do the same thing with the tuple type (a, b): we fix the a and declare a Functor instance with the b as the functor contents:

Note that due to a strange quick of Haskell syntax, we write (,) a in order to declare a tuple type constructor of kind * -> * which has the first element as a and the second element as an argument to the constructor.

Note that a similar syntactic quirk applies to function types. Namely, in order to use the type (c ->) of kind *+ -> +*, you must write (->) c. Thus, the type (->) c b is completely equivalent to c -> b. The observation that (->) c has kind *+ -> +* might lead us to an intriguing question…​ can we write a functor instance for it?

Suppose we want to write a Functor instance for (->) c. We’d start with our general instance scaffold:

However, what would we do with fmap? What does that even mean?

In this case, it’s often helpful to think about the types involved, and let the types guide your coding. We know that for a functor f, the definition tells us that fmap has type fmap :: (a -> b) -> f a -> f b. Since we are specializing f to (->) c, fmap must have type (a -> b) -> (->) c a -> (->) c b. If we undo the syntactic quirkiness, we find that fmap has type (a -> b) -> (c -> a) -> (c -> b). Since we’re letting the types guide our intuition and coding, can you think of something that has that type? The key observation is that both of the two arguments are one-argument functions, and the output of one is the input to the other. It turns out that the type of this fmap is the same as the type of (.), the composition operator! Alternatively, we can write function composition ourselves, and write the following instance:

The following instance is identical in semantics:

And that’s it – it turns out that (->) c can indeed be made into a functor, and pretty easily, too!

This raises two questions:

The first question can be answered by doing what we usually do with Haskell abstractions – coming up with a set of laws that instances of the abstraction must follow, and verifying that the particular instance we’re interested in follows those laws.

In the case of functors, we’d like to enforce a few of our basic intuitions. Our intuitions for functors should tell us that fmap ing a function over a functor is equivalent to applying the function inside the functor. Due to this intuition, we may think that if we apply a function that does nothing, that should have no effect and do nothing to the larger data structure. We can codify this in the following law:

Note that we are writing in point-free style, where we avoid mentioning the actual object that these functions are applying to. What we really mean is that for any functor f and any type f, if any x has type f a, fmap id x must be equal to x.

The other law is motivated in the same way. Since fmap ing a function is like applying a function inside the container, fmap ing the composition of two functions (where one function is directly applied to the output of another) should be the same as fmap ing the first function and then fmap ing the second function. In other words,

These two laws are known together as the functor laws, and codify the behaviours that a "proper" Functor instance must follow. These are quite useful in guiding us in instance implementation. For example, suppose we tried to implement the following Functor instance for lists:

We can verify that the type of fmap is correct. However, the behaviour is a little bit strange – we only keep the first element of the list! Indeed, this strange functor instance would be eliminated by checking the first functor law:

Now that we have some functor laws to guide us, we can answer our first question and verify that our instance for (->) c is a valid functor. Since fmap is just (.), we can check the first law by verifying that

However, we know that id does nothing when composed (on the right or the left), so the first law holds! The second law can be verified in the same manner – by taking the definitions of fmap, expanding them, and then using what we know about function composition and id to prove what we want.

Finally, we can answer our second question, and try to provide some intuition for this functor. Although we can attempt to provide intuition, it is important to remember that ultimately, a Functor is simply any type along with an implementation of fmap which satisfies the functor laws. Our intuition may be helpful for reasoning about this functor, but the definition is just that – something which satisfies the requirements and laws of a functor. With that said, the intuition that helps with the (->) c functor is that we can view this as a data structure with a hole in it, where the hole needs something of type c to fill it.

For example, suppose we have a data structure

In that case, we can create a type that represents a Thing with a hole.

The data structure with a hole is represented by a function, because once we get something to fill the hole (an Int), we can create a complete data structure (a Thing). Thus, applying fmap to something of type (->) c a is like operating on a data structure of type a with an unfilled hole of type c, just like applying fmap to something of type Maybe a is operating on a data structure of type a that might actually be null (Nothing).

Functors, along with the Functor typeclass and fmap, can be very useful for talking about computations happening inside a container or computational context. For example, we can use the Functor instance for Maybe in order to write code which operates on a failed computation and/or nullable value (see the previous section for some examples). But there are many cases where the Functor abstraction turns out to be insufficient.

Consider the head function that takes the first element of a list:

Instead of crashing with an error on empty lists, we may instead want to signal failure by returning a Maybe value, allowing us to write safer, typechecked code. We could rewrite head and call it headMay, with the -May suffix indicating that it returns a Maybe value:

Now, suppose we’re storing a 3D array as a list. (Due to the runtime characteristics of linked lists, this is a terrible idea in practice!) For some reason, we need to access the top left corner of this 3D array. In other words, we have a triply nested list (type []) and we’d like to access the first a in it by repeatedly taking the head of these lists. If we’re using plain old head, this is very easy:

We can test that it works by plugging in firstElement [[[1]]]; indeed, we get 1, as expected. However, if we plug in [[]] or [[[]]], we get the standard head exception, since the element we want to access doesn’t exist.

Naturally, as Haskell programmers, we’d like to rewrite this to be safe, just like we changed head into headMay. A first attempt might look something like this:

However, if you try putting this into GHC, you’ll see that these types don’t match! By returning a Maybe, we’ve broken our ability to compose functions! We might be tempted to turn to our trusty Functor instance, since we’ve seen that that using fmap will help us with error handling. If we try that, we might get something like this:

Indeed, that definition typechecks (better than nothing!), but instead of just giving us a Maybe a we get a much uglier beast of the form Maybe (Maybe (Maybe a)). Clearly, this is not what we wanted, because pattern matching on that thing will be a huge pain!

The underlying reason for the difficulty here is that the Functor instance is good for modeling a single missing value, but it isn’t food for modeling a process in which any individual step might fail. In words, one might describe what we’re doing as a process: Take the head three times, and if any of those fail, return Nothing, otherwise, return Just the result. Indeed, we can implement this with pattern matching:

Eek, that’s ugly! In order to clean this up, we’re going to follow our intuition of describing this as a process that might fail at any step. Let’s implement this as the following function:

We’ve named this function very deliberately: if we use it in infix form (using backticks to turn the function into an infix operator), we get something that is very element and reads almost like English:

Note that in the definition above, we have the first headMay as a special case. We start off our processing chain with its result, headMay xs. In order to write the entire process as one pipeline without the first one being a special case, we’ll define a strangely named return function which just starts us off inside the Maybe:

Now we can write this pipeline in a uniform manner. We use return to put something inside the pipeline, and then use processWith to define what needs to happen:

The name return may seem a little strange at first, but stick with it for now – it will make sense eventually! (Note that return is just a name. Don’t make the mistake of thinking it’s something syntactically special, just because other languages tend to have return as a keyword!)

Using return and processWith, we can define very clean and elegant processing pipelines. It turns out this pattern is very common in Haskell, and in programming in general. Before formalizing this abstraction, let’s look at another example.

The key to this abstraction is that, roughly speaking, we’re generalizing over types of computation. In the case of processWith and Maybe, we are creating a pipeline of processes that might fail and modeling a computation that has the ability to fail at any step. At any step, our potentially failing computation can produce either one value or zero values (failure). We can generalize this behaviour by talking about a computation that can produce any number of values at each step.

In order to represent the state of a computation that can produce multiple values, we’ll just use a plain old list. At each step of the computation, we’ll take all the current values, process them with the next step of the computation, and collect all the results. Note that the step gives us a list of results, as well. The result looks like this:

(Note that this is showing another application of this pipelining abstraction; we can’t actually write two functions named processWith with different type signatures. That’s what typeclasses are for.)

Let’s try this with a simple example. We’ll start with the list [1, 2, 3] and then we’ll filter it by using a function that gets rid of odd numbers, \x -> if odd x then [] else [x]. Combining these with processWith, we get

As expected, this gives us the result [2]. (While you may note that using filter would be much simpler in this case, this simple case does show off how our pipeline works in general.)

Let’s try this on another example. Suppose you want to write a function which takes the Cartesian product of two lists. Namely, given lists of x s and lists of y s, it produces all the pairs (x, y). For the lists xs = [1, 2] and ys = ["Hi", "Bye"], this would produce the output list [(1, "Hi"), (1, "Bye"), (2, "Hi"), (2, "Bye")]. We could write this using pattern matching, though it takes a bit of thinking to figure out how to do it right:

Alternatively, we could model this as a process which outputs multiple values. At the first step, the process outputs the xs; at the second step, it outputs all the ys; then, it combines them with tuples. This might seem a bit convoluted, but produces straight-forward (if syntactically ugly) code:

At this point, we can complete our pattern by implementing a return function:

Now we see why it’s called return: it has a tendency to be used when we need to output a final value from our computation pipeline! Rewriting our Cartesian product with return is a very minor modification:

Although this end result is arguably simpler than our original pattern matching example, this style of programming can be very natural. For instance, we wanted to extend this to three lists, the changes would be very small:

On the other hand, modifying the original pattern matching crossProduct may be a bit tedious and somewhat more error-prone.

As I alluded to earlier when we redefined the meaning of processWith, this abstraction is codified in a Haskell typeclass, as usual. Although one might want to call this typeclass something like Pipeline or Process or Sequenceable, in Haskell this typeclass is called Monad. The typeclass renamed processWith to an infix operator written >>= (pronounced "bind"):

Note how the type signature of >>= looks exactly like processWith, if you replaced m with Maybe or [] (the list type constructor).

We can implement Monad instances for Maybe and [] using the processWith and return definitions we saw previously:

With these instances, our previous functions become

If you’ve heard a lot about monads in Haskell, this is all they are – they are a pattern for describing these sorts of pipelines. That’s it!

Of course, like many abstractions, there are many applications of this abstraction where the word "pipeline" or "computation" won’t seem to be quite right, which is why Haskell programmers have a tendency to prefer abstract names (which may seem meaningless to the rest of us). As with the Monoid abstraction and the Functor abstraction, something is a Monad if it implements the methods in the typeclass and follows some set of laws (called, unsurprisingly, the monad laws). It’s important to note that there are no other requirements for being a Monad, which means that sometimes, you’ll find Monad instances for things that do not follow your intuitions of "pipelines" at all.

Like we did with Functor s, we’ll try to motivate the monad laws with intuition about how these pipelines should be have. So far, we’ve defined return as something hat just wraps a value in our Monad. In the case of Maybe, we wrapped values by putting them in a Just, while with lists, we wrapped values by putting them in a one-element list. We’ll enforce the intuition that return doesn’t do anything except wrap values with two laws, the first being as follows:

This says that if you process m using return, you just get m back.

The second law is effectively a reverse of the first laws. Instead of processing a value which is already in a monad with return, we’ll lift a non-monadic value into a monad using return. Then, we’ll process this value with some function, and verify that the result would be the same had we just applied the function to the non-monadic value in the first place.

The last monad law is a little bit more difficult, but effectively states that >>= is an associative operator.

Note that this isn’t quite associativity of >>=, since we can’t write m >>= (n >>= p) on the right hand side (because n is a function, not a value in a monad). Monads that don’t follow this law can be very unintuitive. This law states that the grouping of things in the pipeline doesn’t matter; if our values go through the entire pipeline, it doesn’t matter if we view the first two processes as one group (the left hand side of the equation above) or if we view the second two processes as one group (the right hand side). This may seem like something we can take for granted, but this is worth encoding as a law precisely because it seems like something we’d want to take for granted.

While typeclasses and laws can be pretty powerful on their own, the Monad abstraction is so important in Haskell that it has its own syntax, known as do notation. This syntax allows us to write these monadic "pipelines" very cleanly, without resorting to anonymous functions like we did in the cartesianProduct example. Do notation has three rules, which dictate how do notation is expanded into a standard Haskell expression.

Expansion 1: The block of code

is expanded to

Note that nextStep may use variable, and may consist of multiple statements.

Expansion 2: The block of code

is expanded to

This case is identical to the previous one, but no variable name is bound. The output of m is ignored.

Expansion 3: The block of code

is expanded to

This allows us to easily embed let statements in do blocks. Note that there is no in after the let! \end{enumerate} With this notation, our firstElementMay and cartesianProduct functions become even cleaner:

Although do notation is incredibly convenient, beware of viewing it as simple imperative programming. Although it may look like an escape hatch from the functional paradigm into a more standard imperative language, do notation is just syntactic sugar over return and bind (>>=); forgetting that can lead to confusion and misunderstanding. Also, note that there are times where using return and >>= directly may be simpler than using do notation, so do not be afraid to use them without the syntactic sugar. (For instance, the firstElementMay implementation is arguably cleaner without do notation.)

So far, we’ve seen three abstractions commonly used in Haskell: the monoid, the functor, and the monad. There are a few other abstractions that we will cover at a later point, but these three will get you the majority of the way to Haskell fluency.

Recall that we started by defining a monoid as follows:

Whenever we had a mathematical abstraction that defined some set (such as the monoid $M$), we could describe the set as a type in Haskell, and describe the abstraction on the set as a typeclass. The resulting typeclass is (unsurprisingly) called Monoid in Haskell, and is defined as follows:

Note that mconcat is actually part of the class, although it has a default definition defined in terms of mappend and mempty. As a result, instances of the Monoid class need only to define those two primitives.

The next abstraction we covered in this guide was the Functor. Although we could give a similar mathematical definition and translate it into Haskell, the mathematics is out of the scope of this guide, so we can skip directly to the typeclass:

The Functor class Haskell uses defines an extra operation, <$. This operation simply replaces the contents of the functor with a new value; thus, 3 <$ Just "hi" == Just 3. For historical reasons, the similar operator <$> is exported from Control.Applicative, even though it is quite idiomatic to use it with any Functor.

Once we’d seen a few functors, we looked at the workhorse of abstractions in Haskell – the Monad typeclass. Like Functor and Monoid, the Monad typeclass includes a few bits we haven’t previously discussed:

In order to implement an instance of Monad, we need to define >>= and return. The typeclass also contains >> (which is like >>= but discards any value produced by its input) and fail, which is used on pattern match failures. However, these are given default definitions defined in terms of >>= and error, so they do not need to be implemented to make something into a Monad.