So far, the typeclasses we’ve seen have obvious analogues in nonfunctional languages too. This section will look at a few of the typeclasses that are particularly important to functional programming design.
Functorlink
The Functor
typeclass is for data types that can be treated like containers whose elements can be “mapped over.” Specifically:
typeclass Functor f
map : (a > b) > f a > f b
You might also think about a functor as a way to apply a function through a data structure. Lists are a common example; indeed, many objectoriented languages give a map
method to their array or list class.
instance Functor []
= []
map _ [] ::xs) = f x :: map f xs
map f (x
 this evaluates to [10, 4]
= map stringLength ["functional", "peep"] someInts
Optional
is also a useful Functor
:
instance Functor Optional
Nothing = Nothing
map _ Just x) = Just (f x) map f (
Foldablelink
Foldable
is the typeclass of data structures that can be “folded”, accumulating some result at each point:
typeclass Foldable t
foldl : (b > a > b) > b > t a > b
The l
at the end of foldl
indicates that this is a left fold ^{1}. The words “left” and “right” refer to the head and tail of a list, respectively; in general, left folds start at the “front” of a data structure (they are breadthfirst), and right folds start at the “back” (depthfirst). What this means is best illustrated by an example. Consider this definition of the sum
function, which sums a list of integers:
instance Foldable []
= acc
foldl _ acc [] :: xs) = foldl f (f acc x) xs
foldl f acc (x
sum : [Int] > Int
= foldl (+) 0 sum
Now let’s consider what happens when this function is evaluated. This next bit isn’t code; each line represents a step of “unwrapping” the fold until we get to the point where we only have math left to do:
sum [1, 2, 4, 8]
foldl (+) 0 [1, 2, 4, 8]
foldl (+) (0 + 1) [2, 4, 8]
foldl (+) ((0 + 1) + 2) [4, 8]
foldl (+) (((0 + 1) + 2) + 4) [8]
foldl (+) ((((0 + 1) + 2) + 4) + 8) []
((((0 + 1) + 2) + 4) + 8)
As you can see, the first thing to be evaluated is \(0 + 1\), and we proceed down the list, evaluating the “leftmost” operations first. This implies the existence of a right fold ^{2}:
foldrList : (a > b > b) > b > [a] > b
= b
foldrList _ b [] :: xs) = f x (foldr f b xs)
foldrList f b (x
sumr : [Int] > Int
= foldr (+) sumr
When this is evaluated, we get
sumr [1, 2, 4, 8]
foldr (+) 0 [1, 2, 4, 8]
(1 + (foldr (+) 0 [2, 4, 8]))
(1 + (2 + (foldr (+) 0 [4, 8])))
(1 + (2 + (4 + (foldr (+) 0 [8]))))
(1 + (2 + (4 + (8 + (foldr (+) 0 [])))))
(1 + (2 + (4 + (8 + 0))))
Unsurprisingly, now we’re starting on the right! This ends up evaluating to the same result, but that is only the case for associative operations. You may recall from math class that this has to do with how we group a series of operations; if we just write \(0 + 1 + 2 + 4 + 8\) there are five different \(+\)s that we could choose to evaluate first. Of course, with addition, it doesn’t matter; any way we group the operations comes out to the same result. We call functions with this property associative. On the other hand, subtraction is definitely not associative:
((((0  1)  2)  4)  8) = 15
(1  (2  (4  (8  0)))) = 5
In this case, foldl
and foldr
give different results! This isn’t actually that big of a deal though—if you know which side you’re starting from, you can always define your folding function appropriately (and perhaps reverse your list) in order to get the result you want. It turns out, though, that sometimes it does matter which fold you choose!
The examples above with (+)
are reductions: they collapse the list as they traverse it. Both reductions happen in linear time (since they traverse the input list exactly once), but foldl
happens in constant space, while foldr
uses linear space! For very long lists, this can easily overflow the stack. The reason is that when folding from the left, we’re keeping a “running total” of the folded value; each rescursive call need not generate its own stack frame, so the fold only needs as much memory as is required to store the result value. On the other hand, folding from the right means that we must traverse the entire list before we can start evaluating stuff, and each time we recurse further into the list, we have to hold on to the current value while we wait for the evaluation to work its way back up the stack!
However, not all folds are reductions, and interestingly, the situation is reversed for nonreductive folds. Consider the two functions below, which implement map
over a list, one with a left fold and the other with a right fold. You should be able to convince yourself that they both produce the same result as we saw for the Functor
instance above:
mapl : (a > b) > [a] > [b]
= foldl mapAndAppend [] where
mapl f = ys ++ [f x]
mapAndAppend ys x
mapr : (a > b) > [a] > [b]
= foldr mapAndPrepend [] where
mapr f = f x :: ys mapAndPrepend x ys
Note that when we’re folding from the left, we put each successive result at the end of the new list. Likewise, when we’re folding from the right, we start at the end of the list, so we append each result to the head of the new list. Evaluating these as we did before, we get
"Mrs", "Birdy", "says", "peep"]
mapl stringLength [ (((([] ++ [3]) ++ [5]) ++ [4]) ++ [4])
"Mrs", "Birdy", "says", "peep"]
mapr stringLength [ (3 :: (5 :: (4 :: (4 :: []))))
The problem here is that concatenation using ++
runs in time proportional to the length of the lefthand list, and each time we do a concatenation, the lefthand list gets bigger; suddenly our left fold is in quadratic time! We would therefore rather choose a right fold for this job, because it allows us to use the constanttime list constructor ::
rather than lineartime concatenation.
Now, depending on your language’s evaluation rules, how it implements lists, and particuarly how smart its optimizer is, your mileage may vary. The moral of this story is that you should choose your fold so that reductions are strict and tailrecursive, and nonreductive folds build the output structure efficiently, using only constanttime operations (if possible).
Monoidlink
First, a warning: monoids are to monads as Java is to JavaScript, so apologies in advance for the similar words. Blame mathematicians again.
Here’s the definition of Monoid
:
typeclass Monoid a
empty : a
(<>) : a > a > a
This can be read a couple of different ways. Usually the one folks see first treats <>
as an operator for glomming two instances of the monoid together, with empty
as the “neutral” element; for example, with integers:
instance Monoid Int as Sum
= 0
empty <>) = (+)
(
sum : [Int] > Int
= foldl (<> using Sum) sum xs
Notice that I have named the instance; this can sometimes be useful, because there may be multiple ways for a given data type to implement a typeclass. Such as:
instance Monoid Int as Product
= 1
empty <>) = (*) (
Each of these specifies a particular way that integers can be stuck together. With these examples handy, we can write down the monoid laws:
 Associativity

(x <> y) <> z == x <> (y <> z)
 Identity

x <> empty == empty <> x == x
The requirement that <>
be associative means that there aren’t monoid instances for division or subtraction. (By the way, division has another problem too; <>
should always be defined for all values, but division by zero isn’t defined!)
The other way to interpret a monoid is as a way to choose between two values with <>
, with empty
providing a default choice.
instance Monoid (Maybe a) as First
= Nothing
empty
Just x <> _ = Just x
Nothing <> Just x = Just x
Nothing <> Nothing = Nothing
instance Monoid (Maybe a) as Last
= Nothing
empty
<> Just y = Just y
_ Just x <> Nothing = Just x
Nothing <> Nothing = Just x
Here, the First
instance always chooses the first nonNothing
value it was given; likewise, Last
always chooses the last.
As a final example, Bool
also admits two possible monoids:
instance Monoid Bool as All
= True
empty <>) = (&&)
(
instance Monoid (Maybe a) as Any
= False
empty <>) = () (
Applicativelink
The extravagantlynamed applicative functor is, of course, simply a functor that is applicative!
That sounds offensively unhelpful, but interestingly it’s one of the more meaningful names for important concepts (looking at you, ‘Monad’). To illustrate what it means, let’s consider a puzzle. A program has asked the user for two integers, x
and y
, but since getting these integers involves communing with the outside world of side effects, they are both of type IO Int
. Your goal is to add them together. How can we do this?
Unlike most data types, IO
values cannot be “unwrapped”, because that would defeat the purpose of keeping side effects contained. IO
is a functor, so we can do things like
x : IO Int
= askUserForInt
x
y : IO Int
= askUserForInt
y
z : IO Int
= map (*2) x  double it! z
but before you ask, x + y
doesn’t work because IO Int
is not a number! It’s more like a promise of a number, and in fact thinking about IO
like an ES Promise
or a Java CompletableFuture
is not a terrible approximation.
Okay fine, it’s a trick question, and presumably you have already figured out that the answer has to do with whatever an applicative is. Plain functors simply don’t provide enough power to support this sort of operation. Happily, IO
is an Applicative
, which gives us access to this gadget:
liftA2 : (Applicative f) => (a > b > c) > (f a > f b > f c)
 definition will come in a moment!
addTwoIOs : IO Int > IO Int > IO Int
= liftA2 (+)
addTwoIOs
= addTwoIOs x y  ta da! addXAndY
The function liftA2
takes a pure function of two arguments, and turns it into a function over two Applicative arguments. The term lift is one that will occur a lot; it’s usually given to a function that takes a “plain” function and transforms it into a “special” one—e.g. lifting the humble (+)
into the exciting world of IO
. “liftA
” denotes a lift into Applicatives, and “liftA2
” indicates that it operates on functions of two arguments; once you get over that hurdle, it’s easy enough to construct liftA
\(n\) but usually that’s excessive. In fact, you’ve already seen liftA1
: it’s just functor map
!
liftA1 : (Applicative f) => (a > b) > (f a > f b)
 where have I seen this type signature before?
Hopefully that is enough to start shedding light on the name applicative functor. Let’s look at how it’s actually defined.
typeclass (Functor f) => Applicative f
pure : a > f a
(<*>) : f (a > b) > f a > f b
The pure
function lifts a plain value into an applicative. The name is intended to suggest that we’re getting “just” that value: no spooky side effects, no accidental emails to scandalize grandma, it’s a pure value. For instance, if we didn’t want to bother asking the user for numbers (they would probably screw it up anyway), we could just say
myX : IO Int
= pure 2
myX
myY : IO Int
= pure 3 myY
The other thing, (<*>)
, is pronounced “apply”, and it takes a lifted singleargument function and applies it to a lifted value. These two things together allow us to define liftA2
:
liftA2 : (Applicative f) => (a > b > c) > (f a > f b > f c)
= pure f <*> x <*> y liftA2 f x y
Which is to say, we lift f
up into the applicative, (partially!) apply it to x
, and then finally apply that to y
. In fact, we could have started with liftA2
instead:
(<*>) : (Applicative f) > f (a > b) > f a > f b
<*> x = liftA2 id f x f
Monadlink
The Monad
class contains one function, (>>=)
(pronounced “bind”), on top of what is already present in an Applicative
(such as (<*>)
and pure
).
typeclass (Applicative m) => Monad m where
(>>=) : m a > (a > m b) > m b
This may not seem like a huge innovation at a glance, but in fact monad bind is the main thing that allows us to do useful work in functional languages, which is why we refer primarily to the IO
monad rather than the IO
functor or applicative. To see why, consider an example:
askForName : IO String
=  ask the user for their name somehow
askForName
printGreeting : String > IO ()
= println ("Hello, " ++ name ++ "!") printGreeting name
Try as we might, there is no way, using only Functor
or Applicative
operations, to ask the user for their name and then chain that result into printGreeting
. You may have already deduced how to do this in the IO
monad:
:: IO ()
askForNameAndGreet = askForName >>= printGreeting askForNameAndGreet
This is why monads are so exceptionally important for making nontrivial functional programs: they let us pipe the results of sideeffectful operations into each other. This is basically what an interactive program is all about! Of course, the type of side effects IO a
is not the only monad, and for other types, the semantics of “what it means for this thing to be a monad” vary. We will be going over many of these in Monads: A Field Guide.
Traversablelink
Traversable
is used for data structures that can contain multiple actions, which can be performed in a specific order. For instance, given a list of IO
actions which ask the user to type a word on the console:
askForWordsThreeTimes : [IO String]
= [askForWord, askForWord, askForWord]
askForWordsThreeTimes
askForWord : IO String
 something
The type of askForWordsThreeTimes
is somewhat inconvenient, though. We really just want one action, which contains the results. For this type of situation, we use traverse
:
typeclass (Functor t, Foldable t) => Traversable t where
traverse : (Applicative f) => (a > f b) > t a > f (t b)
In the type signature for traverse
, think of a
as an “input type” and b
as an “output type”. t a
is a collection of inputs in some structure t
, and the result is one big action that contains the results in the same structure: f (t b)
.
There is a helper function sequence
that can be used if your structure already has a bunch of actions, and you just need to collect them instead of mapping:
sequence : (Traversable t, Applicative f) : t (f a) > f (t a)
Using this, we can get
askForThreeWords : IO [String]
= sequence askForWordsThreeTimes askForThreeWords
Note that we’re not combining the results in any way; we’re just turning, for instance, a list of actions into one action with a list of results. The order in which those actions is performed is always the same for any given structure, which is defined by the traverse
implementation for that structure. For instance, lists are always evaluated from left to right:
 this was mostly borrowed from Haskell's implementation
instance Traversable []
= foldr cons_f (pure []) where
traverse f = liftA2 (::) (f x) ys cons_f x ys
sequence
can also be used for some funny edge cases, like if you accidentally end up with a Maybe (IO a)
when you really want an IO (Maybe a)
.