FUNCTORS, APPLICATIVES AND MONADS IN HASKELL

2022-03-30

Disclaimer

In this article we will learn about the three main abstract structures in Haskell: functors, applicatives and monads. Before getting started I want to make a disclaimer:

this guide is not intended to replace the existing literature about monads in Haskell, this is just the method I have used to understand them. I can't guarantee you that reading this post will give you the right insight to understand these topics, I think it's impossible to understand them on the first try, even beginners tutorials struggle on that. Furthermore, keep in mind that you may have a different skill set from mine; before learning about monads I already had a background in category theory and in functional programming, this guide is based on this assumption.

Before talking about functors, applicative and monads, we need to figure out a couple of things about Haskell's type system.

Data Types

As you might already know, Haskell provides a lot of builtin data types, such as Int, Integer, Char, String, Maybe, etc. In order to implement a new type, we can use either data, newtype or type. Let us break down the differences:

Algebraic Data Type

An algebraic data type is a type formed by combining two or more types. In Haskell, they are defined using the data keyword. An ADT allows us to define a new data type with an arbitrary number of constructors, each constructor can have an arbitrary number of arguments. For example, Haskell defines the Bool type as

                
data Bool = False | True

This is read as “Boolean is either False or True”.

The word “algebraic” refers to the fact that these kind of data types are built using algebraic operators such as and(product) and or(sum). They work in the following way:

sum is equivalent to the logical (exclusive)disjunction(e.g., A | B means either A or B);
product is equivalent to the logical conjunction(e.g., A B means both A and B).

As we said earlier, Haskell allows data types to have an arbitrary number of constructor(zero or more) and an arbitrary number of arguments(zero or more), furthermore data types can be recursive, this approach allows us to easily define a tree-like data structure:

                
data Tree t = Leaf t | Node (Tree t) (Tree t) deriving Show

as you can see, a tree can either be a leaf(i.e. the end node) or a node with two subtrees. The last part(deriving Show) allows us to print out a Tree object in the console:

                
Prelude> t = Node (Leaf 0) (Node (Leaf 1) (Leaf 2))
Prelude> t
Node (Leaf 0) (Node (Leaf 1) (Leaf 2))

Newtype

Another way to declare new data types is by using the newtype keyword. This type declaration can be used whether you want to declare a new type that has exactly one constructor, The advantage of using newtype over data is that the former is optimizer by the compiler, hence it is faster than the latter.

Type

The last way to declare data types in Haskell is by using type keyword. This declaration consists in a type synonymous to another data type. For example, the String type is defined as

                
type String = [Char]

type keyword works like the typedef keyword from C/C++.

Typeclasses

Now that we have a brief understanding of how types works in Haskell, we can introduce another core topic: typeclasses.

A typeclass is a construct that implements ad-hoc polymorphism(i.e., overloading). A typeclass consists in a set of functions that defines a certain behavior; an instance of a typeclass implements that behavior concretely.

Typeclasses are quite similar to interfaces from the object-oriented world: defining a sort of blueprint and then delegating the concrete classes to implement the methods(i.e., the behavior). Be sure, however, to not mix up OOP classes and Haskell classes, because they are not the same thing.

For example, the Eq typeclass is defined as follows:

                
class Eq a where
(==) :: a -> a -> Bool
(/=) :: a -> a -> Bool

which contains all types that allow equality.

Functor

In order to introduce the concept of functors, let first see the definition of the Maybe data type:

                
data Maybe a = Just a | Nothing

Now suppose that we want to apply the function

                
-- Increment by one
inc :: Int -> Int
inc n = n + 1

to the wrapped value Just 2. If we try to do this, we get this error:

                
*Main> inc (Just 2)
<interactive>:2:6: error:
    • Couldn't match expected type 'Int' with actual type 'Maybe a0'
    • In the first argument of 'inc', namely '(Just 2)'
      In the expression: inc (Just 2)
      In an equation for 'it': it = inc (Just 2)

This is where functors come in.

>
A functor is a typeclass defined as follows:
                    
class Functor f where
   fmap :: (a -> b) -> f a -> f b
                    
                
A functor typeclass defines the fmap function, fmap applies a function(a -> b) to a wrapped value (f a) and returns a new wrapped value (f b).

If we try to apply the Inc function to the wrapped value Just 2 using fmap we should get the wrapped value Just 3, let us try:

                
*Main> fmap inc (Just 2)
Just 3
*Main> inc <$> (Just 2) -- Same result, using the infix operator
Just 3

That is what we were expecting. Let us now see the instantiation of the Functor classtype for the Maybe datatype:

                
instance Functor Maybe where
fmap f (Just a) = Just (f a)
fmap f Nothing = Nothing

Let us break this down:

In the first case, we “extract” the value a from the Just, we then apply the f function to a and we finally wrap the result value in a new Just context;
In the second case, we just return a Nothing.

Increment a Tree-like Data Structure

Let us now to solve this simple computer science problem. Given the following tree-like data structure binary tree example

increment each node by 1. The first thing we want to do is to give an internal representation of the binary tree in Haskell using an algebraic data type:

                
data Tree t = Leaf t | Node t (Tree t) (Tree t) deriving Show

In order to work with this Tree type, we can create a new instance of the Functor classtype:

                
instance Functor Tree where
    fmap f (Leaf t) = Leaf (f t)
    fmap f (Node t leftSub rightSub) = Node (f t) (f <$> leftSub) (f <$> rightSub)

Again, this is what happens here:

If the node is a leaf, apply the function f and wrap it in a new Leaf;
If the node is internal, first apply the f function to the node's state, then apply the fmap function to the left and right subtree and finally wrap the result in a new Node.

We can now proceed to represent the binary tree using our new data type:

                
*Main> let t = (Node 0 (Leaf 1) (Node 2 (Leaf 3) (Leaf 4)))
*Main> t
Node 0 (Leaf 1) (Node 2 (Leaf 3) (Leaf 4))

Then we can apply the inc function to the t tree:

                
*Main> fmap inc t
Node 1 (Leaf 2) (Node 3 (Leaf 4) (Leaf 5))

Applicative Functors

Applicatives extend the notion of functors. An applicative allows us to apply a wrapped function to a wrapped value. Here's an example:

Suppose that we want to apply the wrapped function Just (+1) to Just 1, functors are not enough for this kind of operation:

                
Prelude> Just (+1) <$> Just 2

<interactive>:1:1: error:
    • Couldn't match expected type 'a1 -> b'
                  with actual type 'Maybe (a0 -> a0)''
    • Possible cause: 'Just' is applied to too many arguments
      In the first argument of '(<$>)', namely 'Just (+ 1)''
      In the expression: Just (+ 1) <$> Just 2
      In an equation for 'it': it = Just (+ 1) <$> Just 2
    • Relevant bindings include
        it :: Maybe b (bound at <interactive>:1:1)

In order to overcome this error, we can use the applicative operator (<*>):

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

Let us give a proper definition.

>
An applicative is a typeclass defined as follows
                    
class Functor f => Applicative f where
   pure :: a -> f a
   <*> :: f (a -> b) -> f a -> f b
                    
                
An applicative applies a wrapped function(f (a -> b)) to a wrapped value(f a) and returns a new wrapped value(f b).

You now may be wondering: “what is the point of applying a wrapped function? This would have produced the exact same result if we had used a functor.” The answer is, both functors and applicatives are not limited to the Maybe datatype, in fact we can use these abstract structures with any kind of “contexts”. Let us see a more concise example:

Suppose that we want to execute two different functions to the [5, 4, 3, 2, 1] array, in particular these two functions will do the following:

                
-- Decrement by one
dec :: Int -> Int
dec n = n - 1

and

                
-- Multiply by two
mul :: Int -> Int
mul n = n * 2

In order to apply the first “context”(i.e., the two functions) to the other(i.e., the array) we can use an applicative:

                
*Main> let arr = [dec, mul] <*> [5, 4, 3, 2, 1]
*Main> arr
[4,3,2,1,0,10,8,6,4,2]

The resulting array is a vector with twice the size of the original.

Just like for the previous section let us see the instantiation of the Applicative classtype for the Maybe datatype:

                
instance Functor Maybe where
    fmap f (Just a) = Just (f a)
    fmap f Nothing = Nothing

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

Monads

In this last section we will merge everything we have learned so far in this tutorial to understand the concept of monads. A monad extends the notion of applicatives by allowing us to apply a function that returns a wrapped value to a wrapped value. This sounds confusing and intimidating, let us see an example.

Consider the following function:

                
-- Returns n/2 if and only if 'n' is an even integer
half :: Integral a => a -> Maybe a
half n = if even n
            then Just (n `div` 2)
            else Nothing

It takes a number and, if it is even, it returns half of its size in a wrapped value, otherwise it returns Nothing. Since it returns a Maybe, a first approach could be to just use a functor, let us try:

                
*Main> half <$> (Just 2)
Just (Just 1)

We get a wrapped value…wrapped in another wrapper. The problem with this solution is that the functor does not support this kind of functions(i.e., a function that returns a wrapped value), so we need something more advanced, we need a monad:

                
*Main> (Just 2) >>= half
Just 1

The monad operator(»=, pronounced bind), allows us to do that. Here a real definition:

A monad is a typeclass defined as follows:

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

A monad applies a function that returns a wrapped value (a -> m b) to a wrapped value(m a) and then returns a new wrapped value(m b). The Maybe datatype is also a monad:

                    
instance Functor Maybe where
   fmap f (Just a) = Just (f a)
   fmap f Nothing = Nothing

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

instance Monad Maybe where
   Nothing = Nothing
   Just x >>= f = f x

We can also create a stream of monads by chaining the bind operator:

                
*Main> (Just 40) >>= half >>= half >>= half
Just 5

This tells us that Maybe is both a functor, an applicative and a monad.

IO Monad

One of the most useful monads in Haskell is the IO monad. This monad deals with the unpure, input/output world. It defines three functions:

                
getLine :: IO String -- no arguments, read user input
readFile :: FilePath -> IO String -- takes the filepath, returns filepath's content
putStrLn :: String -> IO () -- takes a string and print it

Let us see them in action. In your working directory create a file with some text inside:

                
$> cat foo
1. Hello World
2. This is the second line
3. This is the last line

The following code will ask the user for a file path, then will try to read the file and finally will print out its content:

                
Prelude> putStr "Enter the file path: " >> getLine >>= readFile >>= putStrLn
Enter the file path: foo
1. Hello World
2. This is the second line
3. This is the last line

We can improve this chain of operations by using the DO notation(it is just a syntax sugar for chains of monads):

                
main :: IO ()
main = do
    putStr "Enter the file path: "
    file <- getLine
    buf <- readFile file
    let content = "File content:\n" ++ buf
    putStrLn content

Which produce the same result:

                
*Main> main
Enter the file path: foo
File content:
1. Hello World
2. This is the second line
3. This is the last line