Marty Stumpf

7 Apr 2022

â€¢

4 min read

This is the third of a series of articles that illustrates *functional programming* (FP) concepts. As you go through these articles with code examples in Haskell (a very popular FP language), you gain the grounding for picking up any FP language quickly. Why should you care about FP? See this post.

In the last post, we learned about **higher order functions**, which dramatically increase one's expressive power. In this post, we'll learn more about types and typeclasses, and the **foldable typeclass**, which will help us learn ** folds**, an advanced and important tool.

Typeclasses are categories of types, and so **the instances of a class are types (not values)**! For the types to be in a typeclass, they have to have certain *traits*.

This graph shows the hierarchy of Haskell classes defined in the Prelude and the Prelude types that are instances of these classes:

As shown above, a typeclass typically contains more than one type. This is useful because it allows us to specify categories of types and still write **polymorphic functions** (functions that work on more than one type).

We've already seen the `Ord`

and `Num`

typeclasses in the last couple posts! Let's look at them in detail!

In the first post, we saw the `Ord`

(*ordering*) typeclass. It was a *pre-requisite* for the sorting algorithm to be applicable. If we have a type that is not ordered (e.g, a datatype of colours or shapes) then we cannot sort it. Therefore, when a type is in the `Ord`

typeclass, **it has a defined way of ordering the elements of that type**.

The documentation shows that the `Ord`

typeclass is a subclass of the `Eq`

typeclass (everything in `Ord`

is also in `Eq`

):

```
class Eq a => Ord a where
```

In fact, as shown in the above graph, all except `IO`

and `(->)`

are subclasses of the `Eq`

typeclass! This makes sense, if we don't know how to tell when things are the same, we cannot order them or do much else.

The documentation also specifies the associated **methods** of this typeclass:

```
compare :: a -> a -> Ordering
(<) :: a -> a -> Bool
(<=) :: a -> a -> Bool
(>) :: a -> a -> Bool
(>=) :: a -> a -> Bool
max :: a -> a -> a
min :: a -> a -> a
```

For a type to be in this typeclass, these methods are defined which means we can apply them to the elements of this type. E.g., from the graph above we know that all except a few types are in the `Ord`

typeclass. So we can apply the function `compare`

to instances of the `Bool`

type!

`compare`

takes two inputs, both of a type that is in the `Ord`

typeclass, and returns the `Ordering`

type. The `Ordering`

type has three ** constructors** (possible instances),

`GT`

(greater than), `Eq`

(equal), and `LT`

(less than). It may be unexpected but we can trust the documentation and run `compare`

on `Bool`

. Running compare in GHCi yields:```
Prelude> compare True False
GT
Prelude> compare True True
EQ
Prelude> compare False True
LT
```

Similarly for the other functions:

```
Prelude> max True False
True
Prelude> (<) True False
False
```

In the second post, we saw the `Num`

(*numeric*) typeclass. It was a pre-requisite for our function `g`

along with the `Ord`

typeclass:

```
g :: (Ord a, Num a) => (t -> a) -> t -> Bool
g f y = f y > 100
```

Note that we call the function `>`

in `g`

. So we know that we must apply it to a type that is in the `Ord`

typeclass. (As we see above that `>`

is a method of the `Ord`

typeclass. Because `>`

takes two inputs of the same type and is applied to `100`

, `a`

has to be an instance of the `Num`

typeclass too because `100`

is, as we can see from GHCi:

```
Prelude> :t 100
100 :: Num p => p
```

The `Num`

typeclass includes instances such as `Int`

, `Integer`

, `Float`

and `Double`

. For a full list see the "instances" section in the documentation.

** Recursion schemes** are powerful tool functional programmers should master. One of the most useful recursion schemes is

`Foldable`

typeclass has the methods `foldr`

(the function for folding) and its variants.```
Prelude> :t foldr
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
```

The documentation also shows instances of the typeclass:

```
Foldable []
Foldable Maybe
Foldable (Either a)
Foldable ((,) a)
Foldable (Proxy *)
Foldable (Const m)
```

Note that the foldable typeclass instances are ** type constructors**. They take a type to form a type. E.g.,

`t a`

in the type signature of `foldr`

. This means that `t`

could be a list, or a `Maybe`

, or `(Either a)`

etc. These are the possible `a`

that we can `folds`

in the next post!Understanding types and typeclasses deeply is important for every FPer and you've done it! As we progress we will see more types and typeclasses. Once you get familiar with them you'll have enough grounding to work with any type, and eventually create any type!

It's also very important to understand that `folds`

can be used on many types. In the next post, however, we'll focus on folding a list, a common structure to fold over. I'm sure you'll be impressed by the power of `folds`

, so stay tuned!

Did you like this article?

Marty Stumpf

Software engineer. Loves FP Haskell Coq Agda PLT. Always learning. Prior: Economist. Vegan, WOC in solidarity with POC.

See other articles by Marty

hello@works-hub.com

Ground Floor, Verse Building, 18 Brunswick Place, London, N1 6DZ

108 E 16th Street, New York, NY 10003

Join over 111,000 others and get access to exclusive content, job opportunities and more!