0. Overview

1. Functors, Applicatives, Monads

For myself, this is probably the most confusing part of the course… So I’ve written up some notes to aid my understanding for this specific chapter.

1.1 Functors

Functors are essentially just boxes, you could put values into these boxes and perform operations on them, and a thing to notice is that, the operations does not change the shape of the ‘data structure’

For instance, a [] is a box, you could have a list of anything in it such as Integers, [1, 2, 3]

is a valid box with elements inside. You might have come across the function map before, and map takes a function and a list of elements, apply the function to every element of the list, then returning it.

So for instance map double [1, 2] will give you [2, 4] and it looks pretty reasonable, and this is where we’re gonna get our intuition from, for our next function, fmap .

fmap is a generic function and it works very differently for each Functor . In Haskell, there is another Functor that we need to be aware of and that is Maybe . In Short, Maybe encapsulates the information inside a container that tells you whether this value exists or not.

data Maybe a = Just a | Nothing

Just a means there is a exact instance of a living in Just , whereas Nothing just means you’ve got Nothing, well at least nothing meaningful, it could occur for instance, when an error arises.

So, fmap basically means it can apply the function to a compact object, by penetrating through the structure and applying the function upon every element inside it. We will illustrate this by an example.

Let’s say we have a function called double where it takes an Integer and returns the doubled Integer.

double :: Int -> Int
double = (*2)

so naturally, you would think by fmapping the two types of objects will output these


fmap double [1, 2] -> [2, 4]

fmap double (Just 5) -> Just 10

and this would be correct, intuitively this is pretty simple but we do have to manually tell Haskell what to do with the data structures when dealing with fmap.

For []:
fmap xs = map xs

For Maybe a:
fmap f (Just x) -> f x
fmap f Nothing -> Nothing

Well of course, these are just pseudocode notation to aid better understanding, the correct syntax should really be this.

instance Functor [] where
	fmap :: (a -> b) -> [a] -> [b]
	fmap = map

instance Functor Maybe where
	fmap :: (a -> b) -> Maybe a -> Maybe b
	fmap f Nothing = Nothing
	fmap f (Just x) = Just (f x)

1.1.1 `<$>`

Well, in Haskell there are always ways to make your code more elegant, for Functors we don’t necessarily have to use the keyword fmap, instead there is an operator <$> which acts as an alias for fmap

(<$>) :: Functor f => (a -> b) -> f a -> f b
f <$> x = fmap f x

I mean, it just looks cooler doesn’t it.

double <$> [1,2,3] = [2,4,6]
double <$> Just 5 = Just 10

Challenge: Double Nested Functors

OK let’s say if you’re a real trouble maker and you present us with these sort of data:

Just (Just 5)
[Just 1, Just 2, Just 3]
[[1,2],[3,4]]

Where we have two functors essentially nested within each other, now what do you do? A trick is to try to think of <$> as a ‘penetrating’ function that gets inside the Functor So it helps you unwrap the boxed value. Take [Just 1, Just 2, Just 3] as an example, this is good because it nests two different Functor types, which would hopefully be less confusing when wrapping the values.

So, as before, we wanna target the pure values, aka 1 2 3, and transform them into 2 4 6, but we need to start from the outside, where we see a list. When applying functions to a list we automatically think of map but in this case, use <$> since we need to stick to the syntax.

let xs = [Just 1, Just 2, Just 3]
f <$> xs -> [f Just 1, f Just 2, f Just 3]

This is pretty easy to illustrate as we have distributed f to every single element in the list, we just have to figure out what f is, notice that in previous exercises we have successfully performed the following transformation. double <$> (Just 5) -> Just 10 . So we do in fact know how to apply a function to a single Functor

Therefore, the function f we desire is simply the eta-reduced version of the <$> from before, by eliminate x from both sides of the function argument. Giving us double <$>

Finally, we substitute f back in our equation and we should get:

 (double <$>) <$> xs -> [Just 2, Just 4, Just 6]

Other double nested Functors should also follow this logic, such as Maybe .

1.2 Levelling up… Now Applicatives

Before we get into any actual discussion, we need to be aware the fact that there exists a certain hierarchy within Functors, Applicatives and Monads, that is, they are supersets of each other, meaning Functors is the biggest collection encapsulating Applicatives, which in turn encapsulates all of Monads.

Therefore, as shown in the class definition, we have the Functor f => constraint.

class Functor f => Applicative f where
	blah blah blah...

There are two very important functions added in the Applicative class, which is pure and <*>.

Pure simply wraps a given value inside the applicative, in its simplest form? So what does that even mean, say you have a value 2 and you wanna wrap it into a list, the most intuitive thing to output is [2]. It is the simplest data structure that contains our value and nothing else, therefore it is pure by our definition.

pure :: a -> f a

for []:
pure a -> [a]

for Maybe:
pure a -> Just a

<*> On the other hand, is quite different, but first we’ll just layout the type signature and examine for the two classes.

class Functor f => Applicative f where
    pure :: a -> f a
    (<*>) :: f (a -> b) -> f a -> f b

We have noticed that this time round, our function has also been labelled with the f . But why would you do something like this? For [], you might have a list of functions to process onto a set of data, which we will explore now.

Let’s say you have a list of functions and a list of data.

let functions = [(*2), (+3)]
let xs = [1, 2]

Naturally you wanna take all the combinations of the functions and data and combine them together, then lay it all out. Which is equivalent of taking the Cartesian product between two sets.

$$ [f_1, f_2] <*> [x_1, x_2] = [f_1 x_1, f_1 x_2, f_2 x_1, f_2 x_2] $$

Something like this, therefore for the [] instance, you would have:

instance Functor [] => Applicative [] where
	pure :: a -> [a]
	pure x = [x]
	
	(<*>) :: [a -> b] -> [a] -> [b]
	fs <*> xs = [f x | f <- fs, x <- xs]

Or if you wanna be creative, you could do this, it requires a bit more imagination but is more fun.

fs <*> xs = concat ((<$> xs) <$> fs)

You’re dealing with a bunch of fs, and their task, or it’s function (on the LHS of the outer <$>) is to do <$> xs for each of the f, so there is indeed f <$> xs under the hood, therefore creating a sublist for every transformed element, lastly concat everything to flatten down them into a single list.

A notable thing is that we have the following identity:

pure f <*> xs == f <$> xs

But it’s not that useful on its own, a good use case will be partially applied functions, but before that, let’s define the Applicative rules for Maybe

instance Applicative Maybe where
	pure x = Just x
	Nothing <*> _ = Nothing
	(Just f) <*> x = f <$> x

Notice that now we have a label on the left side of the <*> indicating if we have a valid function that we can apply stuff to, this is good.

Just (+3) <*> Just 5 -> Just 8
Nothing <*> Just 5 -> Nothing
Just (*2) <*> Nothing
= (*2) <$> Nothing 
= Nothing (by def of <$>)

1.2.1 Chaining of multiple `<*>` and using `<$>`

If we take a closer look at the type signature of <*>, we would notice that the following is possible.

Just (+) <*> Just 1 <*> Just 2
>> (+) <$> Just 1 <*> Just 2
>> Just (1+) <*> Just 2
>> (1+) <$> Just 2
>> Just 3

This is effectively the chaining of multiple applicatives, and this allows infinite operations with <*> because the LHS partially applied functions would always have a Applicative f wrapped around it, so the type signature is satisfied.

So this seemingly confusing mixed use of <$> and <*> can be justified.

But a lot of the times when we are working with Maybe values, it’s the values that are uncertain, rather than the functions, naturally, you might wanna do something like this, where the function is a “normal” binary function.

(+) Just 5 Just 6 -> Just 11 --desired Output

For simplicity’s sake we will just stick to the Maybe types.

magic = someMagicFunction that does that

-- by inspection, magic should have the following types

magic :: (a -> b -> c) -> Maybe a -> Maybe b -> Maybe c
magic f x y = f <$> x <*> y

Congrats, you’ve just invented liftA2.

The following is liftA2 with generic Applicative f types.

liftA2 ::  Applicative f => (a -> b -> c) -> f a -> f b -> f c
liftA2 f x y = f <$> x <*> y

1.2.2 LiftA2

As we have just seen, our magic function took a binary function and two wrapped arguments and performed operation to the values within and returned a wrapped result, this is great news.

If we revisit the code, we can see the leftmost f <$> acts like an activator which enables the right chain of actions to start, then recursion takes over and the underlying <$>s take arguments one at a time to complete the computation.

But notice that it doesn’t really have to be a binary operator, it could be a function with any number of arguments, what if we have a function called sum3?

sum3 :: 3Ints - > Int
sum3 x y z = x + y + z

Well as we have seen earlier, the chaining of <*> is recursive in itself, so we can easily add the third argument to the end.

1.2.3 LiftA3 and Generalization

liftA3 :: (a -> b -> c -> d) -> f a -> f b -> f c -> f d
liftA3 f x y z = f <$> x <*> y <*> z
-- or using previous defintions
liftA3 f x y z = liftA2 f x y <*> z

well if you really wanted to, you could design a function liftA69 that uses previously defined functions, which can be written like this. (My favourite number btw.)

liftA3 blah blah
--def for liftA4
--def for liftA5
...
-- def for liftA68
liftA69 :: (x1 -> x2 ... -> x69 -> z) -> f x1 -> f x2 -> .. f z
liftA69 ... x69 = liftA68 ... <*> x69

Ok let’s not be so naughty lol.

1.2.4 sequence

A use case of the liftA2 function is sequence, generally, it takes a Foldable t and a Applicative f and unwraps the Applicative f inside the Foldable and take it outside. For instance, let’s say if you have [Maybe Int] and you wanna flatten it down to a single Maybe [Int] where if there is any instance of Nothing in the original list, it would give us Nothing, else it wraps the Int list in a Just. To illustrate better let’s look at an example.

[Just 1, Just 2, Just 3] -> Just [1, 2, 3]
[Just 1, Nothing, Just 3] -> Nothing

So to do this, we think of recursion, we need to add the elements one by one, firstly to a single empty list, which is Just [] , and what happens when you have another value, say Just 3? and you wanna add it with the list? Since both of them live in the Applicative world, we use liftA2 (:) to combine them together.

liftA2 (:) (Just 3) (Just []) -> Just [3]
liftA2 (:) (Nothing) _ -> Nothing
similarly for the other orientation.

Obviously, we don’t like writing recursions ourselves, so the foldr function comes in very handy.

sequence' :: [Maybe Int] -> Maybe [Int]
sequence' = foldr (liftA2(:)) (Just [])

1.3 holy shit it’s monad!!! ⚠️😱😱

So you’ve come this far… Now you deserve this red flower → 🌺

Monad is here to complete the last piece of the puzzle, on top of Applicatives, it adds the following two function.

class Applicative m => Monad m where
	return :: a -> m a
	(>>=) :: m a -> (a -> m b) -> m b

return functions exactly like pure, it wraps a raw value in the minimal Monadic context, this will give us a hint for later chaining of operations and the do-syntax later on.

>>= on the other hand, if we take a look at the type signature carefully, we find that we start with a m a, then a function that takes a normal a and returns a m b, finally returning that m b.

How could that ever be useful you might ask?

Let’s just take a look at the Maybe Monad class and investigate more.

instance Monad Maybe where
	return = pure
	Nothing >>= _ = Nothing
	(Just x) >>= f = f x

Notice we have the following identify:

>> (Just y) >>= return
>> Just y

This trivial example is displayed to investigate the syntax of the (>>=) , where you have a wrapped value on the left, and a function on the right, notice that it’s different than what you would have for <*> and <$> , where the function is on the left, then argument is on the left. This will come obvious later when we do the chaining of the operations.

1.3.1 `<- Binding` and `do` notation

We have noticed that, from the type signature of (>>=), in this operator, we notice that our input m a, gets exposed at some point in the operation. So let’s say if you have two monad objects, ma and mb.

let ma = Just 1
let mb = Just 3

How would you add them together to get Just 4? Using >>= ?

-- Hint: Use this structure
-- m >>= \x -> return x = m

so 
op :: Maybe Int -> Maybe Int -> Maybe Int
op ma mb = ma >>= \a -> mb >>= \b -> return (a + b)

>> op (Just 1) (Just 4)
>> Just 5

Very good, it works now but we can all agree that the syntax looks a little ugly doesn’t it, it’s not very elegant and that is exactly why we have the do block (which is syntax sugar for those mess). I don’t want those lambdas and chained >>= all over the place.

It works something like this, notice that in the lambdas we have essentially exposed the contained value and directed where they should go? the <- operator does exactly that, it extracts the value and assign it to a temporary “variable”, essentially.

op ma mb = do
	a <- ma
	b <- mb

So in this case, we have a = 1, b = 3, well at least conceptually.

Lastly, we need to perform the operation 1 + 3 = 4, but 4 is a Int rather than a Maybe Int, so we wrap it inside a return, and return (aha!) it to the user. Do you see why are we calling the Monad version of pure as return? This really completes the last bit of syntax sugar that hints that we are returning to the user.

op ma mb = do
	a <- ma
	b <- mb
	return (a + b)

So much better.

Complete Haskell Notes