- 14 minutes

Now that we have talked about various ways to fold lists – `foldl`

and `foldr`

– we are going to focus our attention on one particularly nice and convenient function that has earn the name of, simply, `fold`

.

## A tale of two parameters

Recall that a typeclass is something that multiple types have in common. Any time we see a pattern, something that seems to be recurring in code, there’s a good chance we’re going to be able to find a typeclass. We’ll find some things that types have in common with each other.

In this course already we’ve seen all six of these concepts:

1^{st} parameter | 2^{nd} parameter | Result | |||||
---|---|---|---|---|---|---|---|

Addition | `(+)` | :: | number | → | number | → | number |

Multiplication | `(*)` | :: | number | → | number | → | number |

Concatenation | `(++)` | :: | list | → | list | → | list |

And | `(&&)` | :: | `Bool` | → | `Bool` | → | `Bool` |

Or | `(||)` | :: | `Bool` | → | `Bool` | → | `Bool` |

Function composition | `(.)` | :: | `(a → a)` | → | `(a → a)` | → | `(a → a)` |

Hopefully when we look at this list, the pattern we’re talking about ought to jump right out. Not only do all of these functions have two arguments – additionally, the two arguments have the same type, which is also the same as the return type. When we add or multiply two numbers, we get another number. When we concatenate two lists, we get another list. When we compose two `a -> a`

functions, we get another `a -> a`

function.

One way this pattern emerges in our code is that when we use functions of this particular sort, we often end up chaining them together.

Expression | Result | |
---|---|---|

Addition | `1 + 2 + 3 + 4 + 5` | `15` |

Multiplication | `1 * 2 * 3 * 4 * 5` | `120` |

Concatenation | `"One" ++ "Two" ++ "Three"` | `"OneTwoThree"` |

And | `True && False && True && False` | `False` |

Or | `True || False || True || False` | `True` |

Function composition | `removeSpaces . removePunctuation` `. toLowerCase` | `normalize` |

We’ll narrow the set of examples from six to three for brevity’s sake: addition, multiplication, concatenation.

## The diamond operator

What if we told you that when you write expressions like these, you don’t have to specify what operation you’re using, but rather it could be inferred from the types of the parameters?

Expression | Result | |
---|---|---|

Addition | `Sum 1 <> Sum 2 <> Sum 3 <> Sum 4 + Sum 5` | `Sum 15` |

Multiplication | `Product 1 <> Product 2 <> Product 3 <>` `Product 4 <> Product 5` | `Product 120` |

Concatenation | `"One" <> "Two" <> "Three"` | `"OneTwoThree"` |

Wherever `+`

, `*`

, or `++`

appeared in the previous example, they now have all been replaced by this blank-looking `<>`

operator, which some describe as having a sort of diamond shape.

What we’re talking about here is the `Semigroup`

class. The three types that belong to this class we’re demonstrating here are sums, products, and lists. This class has exactly one operation, `<>`

, often referred to as “the semigroup operator”, or sometimes “mappend” (the “m” standing for another concept that we’ll get to shortly).

Type definition | Semigroup |
---|---|

`newtype Sum a = Sum a` | `<>` is addition. |

`newtype Product a = Product a` | `<>` is multiplication. |

`data [] a = [] | a : [a]` | `<>` is concatenation. |

List, of course, is the type we’ve seen before, and its semigroup operation is concatenation. `Sum`

and `Product`

are new to us, and this `newtype`

keyword is new here as well. The `Sum`

and `Product`

types exist to get around a peculiar little problem with our desire to replace all of the operators with this mysterious semigroup operator. Say we have two integers, 3 and 4. What do we get when we semigroupally combine them?

`3 <> 4 = ?`

Do we add them to get 7, or do we multiply them to get 12? Both seem like perfectly sensible answers. And so in circumstances where we want to use the semigroup operator, we need to use not `Integer`

directly, but types like `Sum Integer`

and `Product Integer`

. Sums of integers semigroupally combine with addition, and Products of integers semigroupally combine with multiplication.

`Sum 3 <> Sum 4 = Sum 7`

`Product 3 <> Product 4 = Product 12`

We don’t need to go into a discussion of the subtle distinction between `data`

and `newtype`

here. If you read `newtype`

as `data`

, you’ll get the gist. The `Sum`

type has a single constructor, called `Sum`

, and all it really does is wrap up that `a`

value, whatever type `a`

may be, in the `Sum`

type – for example, `Integer`

becomes `Sum Integer`

. It doesn’t add any structure or change what the data *is* at all, but what it does is exactly what it says: it creates *a new type*. And once we have a new type, we can define the new type’s membership in the `Semigroup`

class differently – one for addition, and one for multiplication.

## Identity

We still haven’t done anything interesting yet; all we’ve done is change our `+`

and `*`

symbols to `<>`

, which is not really a useful accomplishment. But here’s something we might want to do with types that follow this semigroup pattern. Suppose we wanted to write a polymorphic function that behaved like this:

Input | Result |
---|---|

`[ Sum 1, Sum 2, Sum 3, Sum 4, Sum 5 ]` | `Sum 15` |

`[ Product 1, Product 2, Product 3,` `Product 4, Product 5 ]` | `Product 120` |

`[ "One", "Two", "Three" ]` | `"OneTwoThree"` |

This function will take a list of things of some semigroup-having type, and smash all the things in the things in the list together. If it is a list of sums, we will add all the numbers together. If it is a list of strings, we will concatenate them all into one long string.

This seems like something we could do with one of the folding functions we talked about in the previous lesson. There’s one little catch, though, and we always have to thing about all the little catches if we want to write total functions: what would such a function do when the input list is empty?

Input | Result |
---|---|

`[ ]` | `Sum ?` |

`[ ]` | `Product ?` |

`[ ]` | `"?"` |

If the way we combined a list of `Sum`

s was to add all of the numbers together, how can we do that if there are no numbers to add?

Recall that we have the concept of an *identity* value: a value which, if it appears in the list, doesn’t change the result. For example, 0 is the identity for addition, because inserting or removing zeroes doesn’t change the result.

```
sum [ 1, 2, 3, 4, 5] = 15
sum [0, 1, 0, 0, 2, 3, 0, 4, 5] = 15
```

Since removing zeroes from the list shouldn’t change the sum, then the sum of `[0]`

should be the same as the sum of `[]`

– it should be zero. In other words, when we “combine all the items in an empty list”, what we get should be the identity value.

Input | Result |
---|---|

`[ ]` | `Sum 0` |

`[ ]` | `Product 1` |

`[ ]` | `""` |

When we fold an empty list of products, we get a product of 1 – because multiplying a number by 1 has no effect. When we concatenate a list of strings together, but there are no strings in the list, we get the empty string.

In answering this question, we have come across another typeclass – another important thing that many types have in common. Sums, products, and lists, all have an identity value. There’s a class for that.

## Monoid

When a type has a semigroup operator and *also* a corresponding identity value, we call that type a *monoid*. The `Sum`

, `Product`

, and `[]`

types all belong to the `Monoid`

class. A monoid must have two things: the `(<>)`

function, and an identity value, which we call `mempty`

.

`(<>) :: a -> a -> a`

`mempty :: a`

So when we think about what it means to take a list of things and smash them all together, we should think of it like this:

Input | Result |
---|---|

`[ ]` | `mempty` |

`[ a ]` | `mempty <> a` |

`[ a, b ]` | `mempty <> a <> b` |

`[ a, b, c ]` | `mempty <> a <> b <> c` |

For the empty list, what we get is the `mempty`

value. If we have a single element, then in addition to the `mempty`

starting value, we append that element, in whatever way that type enjoys being appended – addition, multiplication, concatenation, etc. The more items we have in the list, the more we can just keep chaining that `<>`

operator over and over.

What we have been discussing is the function known as `fold`

.

`fold :: Monoid a => [a] -> a`

It converts a list of `a`

into a single `a`

, with the constraint that `a`

must belong to the `Monoid`

class.

When you want to collapse a list into a single value, it is not *always* the case that you will want to combine using the element type’s monoid. But when you do, the `fold`

function is nicely concise and convenient.

## Foldable

The type of `fold`

is slightly different than the simplified version we gave above.API documentation for `Data.Foldable`

If you query the type in GHCi, this is what you will see:

```
λ> import Data.Foldable
λ> :type fold fold :: (Foldable t, Monoid m) => t m -> m
```

The actual type of `fold`

does not have *list* as its parameter; rather, it has a generic `t`

as its parameter type, with a `Foldable`

constraint on the `t`

. That `t`

can be `[]`

, but it can also be other types of things, not only lists.

We will give a short demonstration to begin exploring the expanded possibilities that this `Foldable`

polymorphism offers.

We have defined two values of type `Maybe String`

. The first is nothing, and the second is just Alonzo.

What we are to demonstrate here is that, in the sense of being `Foldable`

, `Nothing`

behaves like the empty list, and `Just`

something behaves like a list with one element in it. In fact, we can see that very plainly because there is also a function called `toList`

that converts a value of some `Foldable`

type to its list equivalent.

```
λ> toList example1
[]
λ> toList example2 ["Alonzo"]
```

So if we `fold`

example 1, then what we get is the same as if we were to fold an empty list of strings.

```
λ> fold example1 ""
```

And if we fold example 2, then we get the same result as if we folded a list containing only Alonzo.

```
λ> fold example2 "Alonzo"
```

The type of `fold`

is interesting because it is the pinnacle of polymorphism – there is not a single specific in this type signature. Haskell, and in particular the `base`

library, is full of functions like these. When you run across one for the first time, it can often seem impossibly abstract and meaningless.

The key to understanding a type signature like this is to understand its constraints. We need to have a sense of what it means for something to be foldable, and what it means for something to be a monoid.

One really good way to go about that is to keep these examples in mind. Think of things like `[]`

and `Maybe`

as your paradigmatic `Foldable`

s, and things like `Sum`

, `Product`

, and `[]`

as your prototypical `Monoid`

s. Think of folding as taking a list of numbers and adding or multiplying them together, or taking a list of strings as concatenating them all together into a single string.

And as you go through your life in Haskell and encounter new types of `Foldable`

and new types of `Monoid`

, they can always be likened back to those first examples. A class is something that different types share. Always have at hand several examples of types that belong to each class, and be contemplating what it is that the members of a class have in common.