Monads, Categories, and
the Structure of Programming

endofunctor $\longleftrightarrow$ type constructor

In Java, examples of type constructors include:

• List (which produces types List<T>)
• Map (which produces types Map<K, V>)
• Set (which produces types Set<T>)

In C++, examples of type constructors include:

• std::vector (which produces types std::vector<T>)
• std::map (which produces types std::map<K, V>)
• std::set (which produces types std::set<T>)

monad $\longleftrightarrow$ type constructor with flattening

Canonical example: lists

          [[1, 2, 3], 
           [4, 5, 6], 
           [7, 8, 9]]
        

$\downarrow$

          [1, 2, 3, 4, 5, 6, 7, 8, 9]
        

monoid $\longleftrightarrow$ type with concatenation

• Lists

  
                [1, 2, 3] ++ [4, 5, 6] == [1, 2, 3, 4, 5, 6]
              

• Strings

  
                "hello" ++ "world" == "helloworld"
              

• Natural numbers (concatenation in unary)

  
                3 ++ 5 == 8
              

Concatenation of type constructors

Concatenation of lists has type signature: $$\pplus : \texttt{List<T>} \times \texttt{List<T>} \to \texttt{List<T>}$$

Concatenation of the type constructor List has type signature: $$\pplus : \texttt{List<List<T>>}\to \texttt{List<T>} $$

This is flattening!

Outline

Up next: What are monads and why are they useful?

Later: More about categories and monoids

Pure functions

A pure function is deterministic and has no side effects.

Side effects change the state of the system outside the function.

• Input and output
• File system access
• Throwing exceptions
• Global variables
• Mutable function parameters

Functional programming

Functional programming is a style that focuses on:

• Pure functions
• Immutable data
• Declarative, not imperative code

            def odd_squares(arr):
              return (arr.filter(lambda x: x % 2 == 1)
                         .map(lambda x: x ** 2))
          

Functional programming should feel like mathematics.

Functional programming

People like functional programming.

Some languages are designed for it: Excel, Mathematica, Haskell

How do these languages handle side effects?

• Excel/Mathematica: Give up on being functional languages
• Haskell: Use monads!

Introduction to Haskell

Haskell uses mathematical notation for function definitions.

Function application does not require parentheses.

          f :: Int -> Int
          f x = x + 1
        

Introduction to Haskell

Just like in math, Haskell makes it easy to compose functions.

          f :: Int -> Int
          f x = x + 1

          g :: Int -> Int
          g x = x * 2

          h :: Int -> Int
          h = f . g
        

Introduction to Haskell

There is a built-in identity function.

It works with all types.

In Haskell, we usually write a, b, etc. for generic types.

          id :: a -> a
          id x = x
        

Introduction to Haskell

Haskell supports pattern matching in function definitions.

          fib :: Int -> Int
          fib 0 = 0
          fib 1 = 1
          fib n = fib (n - 1) + fib (n - 2)
        

(This code is not perfectly safe, it enters an infinite loop for negative values of n.)

Introduction to Haskell

You can also define functions on multiple variables.

The type Int -> Int -> Int means Int -> (Int -> Int).

          gcd :: Int -> Int -> Int
          gcd n 0 = n
          gcd n m = gcd m (n `mod` m)
        

In other words, after this definition, Haskell considers gcd n to be a perfectly good function with type Int -> Int.

Introduction to Haskell

Pattern matching is especially powerful for algebraic data types.

          data Shape = Circle Float | Rectangle Float Float

          area :: Shape -> Float
          area (Circle r) = pi * r * r
          area (Rectangle l w) = l * w
        

In math, this is the type $\mathbb{R} + (\mathbb{R} \times \mathbb{R})$.

Introduction to Haskell

A List is a recursive algebraic data type constructor.

          data List a = Empty | Nonempty a (List a)

          len :: List a -> Int
          len Empty = 0
          len (Nonempty x l) = 1 + len l
        

In math, we write $L(a) = 1 + (a \times L(a))$.

The Maybe type constructor

(Also called Optional in other languages.)

          data Maybe a = Nothing | Just a

          peek :: List a -> Maybe a
          peek Empty = Nothing
          peek (Nonempty x l) = Just x
        

In other languages, we would likely have peek :: List a -> a and it would either throw an exception or return a sentinel value.

The Writer type constructor

Writer allows you to collect text to print to the console.

          data Writer a = Writer a String

          addone :: Int -> Writer Int
          addone x = Writer (x + 1) "User added one. "
        

Although it seems trivial right now (just a fancy name for a tuple), it will become important later.

The IO type constructor

This built-in type constructor is used whenever the console is used to get input or display output.

IO a means an I/O operation that returns a value of type a.

          putStrLn :: String -> IO ()
          getLine :: IO String
        

Note that getLine is not a function!

Where we are

We learned about the type constructors:

• List
• Maybe
• Writer
• IO

Secretly, these are all monads! That means we need to show how they implement flattening.

Next up: Different types that implement the same functions.

Type classes

Type classes outline functionality that many types should share.

Eventually, we'll define the Monad type class.

          class Show a where
            show :: a -> String
          
          print :: Show a => a -> IO ()
          print x = putStrLn (show x)
        

Type classes

We can implement the functions in a type class for various types.

          instance Show a => Show (List a) where
            show Empty = ""
            show (Nonempty x Empty) = show x
            show (Nonempty x l) = show x ++ ", " ++ show l
          
          main :: IO ()
          main = print (Nonempty 3 (Nonempty 8 Empty))
        

Functors

We defined earlier that endofunctors are just type constructors.

Formally, an (endo)functor must also be an instance of the Functor type class.

          class Functor F where
            fmap :: (a -> b) -> F a -> F b
        

The meaning of fmap f is that it applies f to each element inside the container.

Functors

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

Functors

          instance Functor Writer where
            fmap f (Writer x s) = Writer (f x) s
        

          instance Functor List where
            fmap f Empty = Empty
            fmap f (Nonempty x l) = Nonempty (f x) (fmap f l)
        

When fmap is not enough

Imagine that f wants to change x into y and put it in a box, but x is already in 2 boxes. One option is:

But the next time, f will have to get help from fmap 3 times!

Monads

A monad is a functor that also supports flattening. Formally,

          class Functor m => Monad m where
            join :: m (m a) -> m a
            return :: a -> m a
        

Haskell prefers the word join over flatten, but the meaning is the same.

The function return is less important, it just puts a value into the container.

The Maybe monad

          instance Monad Maybe where
            join (Just (Just x)) = Just x
            -- Nothing cases omitted
            return x = Just x
        

In code, we can now do fmap f . join.

The Writer monad

          instance Monad Writer where
            join (Writer (Writer x s1) s2) = Writer x (s1 ++ s2)
            return x = Writer x ""
        

The Writer monad

          f :: Int -> Writer Int
          f x = Writer (x + 1) "Applied f. "

          g :: Int -> Writer Int
          g x = Writer (x * 2) "Applied g. "

          h :: Int -> Writer Int
          h x = Writer (x - 1) "Applied h. "
        

We want the "composition" f . g . h, but that is not possible.

The Writer monad

Instead, we can use fmap and join!

          composed :: Int -> Writer Int
          composed = join . fmap f . join . fmap g . h
        

Haskell provides a reverse fish operator to make this more concise:

          (<=<) :: Monad m => (b -> m c) -> (a -> m b) -> a -> m c
          f <=< g = join . fmap f . g 
          composed = f <=< g <=< h
        

The Writer monad

Reverse fish composition fulfills the same need as standard composition with side effects, but remains pure. Recall that:

          f x = Writer (x + 1) "Applied f. "
          g x = Writer (x * 2) "Applied g. "
          h x = Writer (x - 1) "Applied h. "
        

Then f <=< g <=< h is equivalent to:

          composed x = Writer (((x - 1) * 2) + 1) 
                       "Applied f. Applied g. Applied h. "
        

do notation

Another way to use monads in Haskell is do notation.

          composed :: Int -> Writer Int
          composed x = do
            y1 <- h x 
            y2 <- g y1 
            y3 <- f y2
            return y3 
        

Superficially, it now looks a lot like other languages!

do notation

To explain do notation, you will will first need to understand lambda functions.

A lambda function is just an unnamed function. It has the following syntax:

          squareAll :: List Int -> List Int
          squareAll list = fmap (\x -> x * x) list
        

do notation

Let f :: a -> m a for some Monad m and type a. Then,

          g x = do
            y <- f x
            ...
        

is defined to mean:

          g = ((\y -> ...) <=< f)
        

do notation

          h x = do
            y <- f x
            z <- g y
            return z
        

          h = (\y -> ((\z -> return z) <=< g) y) <=< f
            = (\y -> (return <=< g) y) <=< f
            = return <=< g <=< f
            = g <=< f
        

do notation in I/O

          main = do
            print "Enter name:"
            name <- getLine
            print ("Hello, " ++ name)
        

          main = ((\_ -> (
                    (\name -> 
                      print ("Hello, " ++ name)
                    ) <=< (\_ -> getLine)) ()
                  ) <=< (\_ -> print "Enter name:")) ()
        

Where we are

We learned about functors and monads.

• fmap helps functions jump into containers
• join flattens out nested containers
• Monads capture side effects
• <=< and do make it easy to compose monadic functions

Next up: categories and monoids

Functor laws

Our category is called * (all types). We said that an (endo)functor is a type constructor F :: * -> * that supports fmap.

Formally, fmap must also satisfy the following:

• Identity law:
fmap id == id
• Composition law: If h == f . g, then
fmap h == fmap f . fmap g

Monad laws

Monads are required to satisfy:

• Identity laws (acting on m a):
  • Box from outside: join . return == id
  x 📕
  return 😈 x 📕
  x 📕
  join ✨ x 📕
  x 📕
  • Box from inside: join . fmap return == id

Monad laws

Monads are required to satisfy:

• Identity laws (acting on m a):
  • Box from outside: join . return == id
  • Box from inside: join . fmap return == id
  x 📕
  fmap 🤝 return x 📕
  return 😈 x 📕
  x 📕
  join ✨ x 📕
  x 📕

Monad laws

• Associativity law (acting on m (m (m a))):
join . join == join . fmap join

"Joining outer first is the same as joining inner first."

Monoid laws

The monoid laws are exactly the same as the monad laws, with outside/inside replace with left/right!

          class Monoid m where
            (++) :: m -> m -> m
            empty :: m
        

• Identity laws: empty ++ x == x andx ++ empty == x
• Associativity law: (x ++ y) ++ z == x ++ (y ++ z)

Final takeaways

• Functional programming languages have functions return monadic types instead of producing side effects.
• The structure of a monad lets you easily compose such functions.
• Monoids in the category of endofunctors is a correct but terrible definition.