2022-03-30

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.

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 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

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.

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
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