Monads and applicatives

What is a Monad?

A monad is a design pattern from category theory that provides a way to structure programs with effects (like state, I/O, exceptions) in a pure functional way. In category theory, a monad on a category $\mathcal{C}$ consists of:

An endofunctor $M : \mathcal{C} \to \mathcal{C}$
A natural transformation $\eta : \text{Id}_\mathcal{C} \Rightarrow M$ (called unit or return)
A natural transformation $\mu : M \circ M \Rightarrow M$ (called join or multiplication)

These must satisfy associativity and unit laws.

Monads in Programming

In programming, a monad is typically defined as:

class Monad m where
  return :: a -> m a              -- Unit/pure
  (>>=)  :: m a -> (a -> m b) -> m b  -- Bind

Equivalently, using join:

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

-- Bind can be defined in terms of join
(>>=) :: Monad m => m a -> (a -> m b) -> m b
m >>= f = join (fmap f m)

The Monad Laws

Monads must satisfy three laws:

Left Identity:
```
return a >>= f  ==  f a
```
Right Identity:
```
m >>= return  ==  m
```

Associativity:

(m >>= f) >>= g  ==  m >>= (\x -> f x >>= g)

These laws ensure that monadic operations compose predictably and behave like mathematical functions.

Common Monads

1. Maybe Monad

Handles computations that might fail:

data Maybe a = Nothing | Just a

instance Monad Maybe where
  return x = Just x

  Nothing >>= f = Nothing
  Just x  >>= f = f x

Example:

-- Safe division
safeDiv :: Double -> Double -> Maybe Double
safeDiv _ 0 = Nothing
safeDiv x y = Just (x / y)

-- Chaining operations that might fail
compute :: Double -> Double -> Double -> Maybe Double
compute a b c = do
  x <- safeDiv a b
  y <- safeDiv x c
  return y

-- Equivalent to:
compute a b c = safeDiv a b >>= \x -> safeDiv x c

2. List Monad

Represents non-deterministic computations:

instance Monad [] where
  return x = [x]
  xs >>= f = concat (map f xs)  -- Or: concatMap f xs

Example:

-- Generate all pairs
pairs :: [Int] -> [Int] -> [(Int, Int)]
pairs xs ys = do
  x <- xs
  y <- ys
  return (x, y)

-- Result: All combinations
pairs [1,2] [3,4]  -- [(1,3), (1,4), (2,3), (2,4)]

3. State Monad

Encapsulates stateful computations:

newtype State s a = State { runState :: s -> (a, s) }

instance Monad (State s) where
  return a = State $ \s -> (a, s)

  m >>= f = State $ \s ->
    let (a, s') = runState m s
    in runState (f a) s'

Example:

-- Stack operations
type Stack = [Int]

push :: Int -> State Stack ()
push x = State $ \xs -> ((), x:xs)

pop :: State Stack Int
pop = State $ \(x:xs) -> (x, xs)

-- Using the state monad
stackOps :: State Stack Int
stackOps = do
  push 3
  push 5
  a <- pop
  push 7
  b <- pop
  return (a + b)

-- Run: runState stackOps [] = (12, [3])

4. Reader Monad

Provides read-only shared environment:

newtype Reader r a = Reader { runReader :: r -> a }

instance Monad (Reader r) where
  return a = Reader $ \_ -> a
  m >>= f = Reader $ \r -> runReader (f (runReader m r)) r

Example:

-- Configuration reader
type Config = String

greet :: Reader Config String
greet = do
  name <- ask  -- Get the config
  return $ "Hello, " ++ name

-- Run: runReader greet "Alice" = "Hello, Alice"

5. Writer Monad

Accumulates output alongside computation:

newtype Writer w a = Writer { runWriter :: (a, w) }

instance Monoid w => Monad (Writer w) where
  return a = Writer (a, mempty)
  m >>= f = Writer $
    let (a, w1) = runWriter m
        (b, w2) = runWriter (f a)
    in (b, w1 <> w2)

Example:

-- Logging computations
logNumber :: Int -> Writer [String] Int
logNumber n = Writer (n, ["Got number: " ++ show n])

compute :: Writer [String] Int
compute = do
  a <- logNumber 3
  b <- logNumber 5
  tell ["Adding numbers"]
  return (a + b)

-- Run: runWriter compute = (8, ["Got number: 3", "Got number: 5", "Adding numbers"])

6. IO Monad

Handles input/output and side effects:

main :: IO ()
main = do
  putStrLn "What is your name?"
  name <- getLine
  putStrLn $ "Hello, " ++ name

The IO monad enforces that side-effectful operations stay contained and ordered.

Do Notation

The do notation is syntactic sugar for monadic operations:

-- Do notation
example = do
  x <- action1
  y <- action2
  return (x + y)

-- Desugars to
example = action1 >>= \x ->
          action2 >>= \y ->
          return (x + y)

Relationship Between Monad and Applicative

Every monad is an applicative functor:

-- Applicative operations can be defined using monad operations
pure = return

mf <*> mx = do
  f <- mf
  x <- mx
  return (f x)

-- Or: mf <*> mx = mf >>= \f -> mx >>= \x -> return (f x)

However, not every applicative is a monad. Applicatives are less powerful but more general.

When to Use Applicative vs Monad

Applicative: When operations are independent and can be parallelized

-- Independent validations
validateUser = User <$> validateName name
                    <*> validateEmail email
                    <*> validateAge age

Monad: When later operations depend on earlier results

-- Dependent operations
buyItem = do
  account <- getAccount userId
  if balance account >= price
    then deduct price account
    else fail "Insufficient funds"

Monad Transformers

Monad transformers allow combining multiple monadic effects:

newtype StateT s m a = StateT { runStateT :: s -> m (a, s) }

-- Combining State and Maybe
type StateMaybe s a = StateT s Maybe a

-- Example: Stateful computation that might fail
safePop :: StateT [Int] Maybe Int
safePop = StateT $ \xs -> case xs of
  []     -> Nothing
  (y:ys) -> Just (y, ys)

Common transformers:

StateT: Adds state to another monad
ReaderT: Adds read-only environment
WriterT: Adds write-only output
MaybeT: Adds failure handling
ExceptT: Adds exception handling

Kleisli Arrows

Monadic functions have type a -> m b, called Kleisli arrows. These compose using the Kleisli composition operator:

(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> (a -> m c)
f >=> g = \x -> f x >>= g

Properties:

-- Identity
return >=> f  ==  f
f >=> return  ==  f

-- Associativity
(f >=> g) >=> h  ==  f >=> (g >=> h)

This forms a category (the Kleisli category) where:

Objects are types
Morphisms are Kleisli arrows a -> m b
Identity is return
Composition is (>=>)

Free Monads

A free monad builds a monad from any functor:

data Free f a = Pure a | Free (f (Free f a))

instance Functor f => Monad (Free f) where
  return = Pure
  Pure a >>= f = f a
  Free m >>= f = Free (fmap (>>= f) m)

Free monads are useful for building DSLs (domain-specific languages):

-- Define a DSL for console I/O
data ConsoleF next
  = PrintLine String next
  | ReadLine (String -> next)

type Console = Free ConsoleF

printLine :: String -> Console ()
printLine s = Free (PrintLine s (Pure ()))

readLine :: Console String
readLine = Free (ReadLine Pure)

-- Write programs in the DSL
program :: Console ()
program = do
  printLine "What is your name?"
  name <- readLine
  printLine $ "Hello, " ++ name

Comonads

A comonad is the categorical dual of a monad:

class Functor w => Comonad w where
  extract   :: w a -> a           -- Dual of return
  duplicate :: w a -> w (w a)     -- Dual of join
  extend    :: (w a -> b) -> w a -> w b  -- Dual of bind

Example: Non-empty list comonad:

data NonEmpty a = a :| [a]

instance Comonad NonEmpty where
  extract (x :| _) = x

  duplicate xs@(_ :| []) = xs :| []
  duplicate xs@(_ :| (y:ys)) = xs :| [y :| ys]

Comonads model context-dependent computations (like cellular automata, image processing).

Laws and Properties

Functor-Monad Relationship

fmap f m = m >>= (return . f)

Every monad can implement fmap using >>= and return.

Join Definition

join :: Monad m => m (m a) -> m a
join x = x >>= id

Alternative Monad Laws (using join)

Left Identity: join . return = id
Right Identity: join . fmap return = id
Associativity: join . fmap join = join . join

Practical Applications

1. Error Handling

-- Instead of nested checks
result = case parseJSON input of
  Left err -> Left err
  Right val -> case validateUser val of
    Left err -> Left err
    Right user -> Right (processUser user)

-- Use monad
result = do
  val <- parseJSON input
  user <- validateUser val
  return (processUser user)

2. Asynchronous Operations

// JavaScript Promises are monads
async function fetchUserData(id) {
  const user = await fetchUser(id);      // >>= in disguise
  const posts = await fetchPosts(user);
  return posts;
}

3. Parser Combinators

-- Build complex parsers from simple ones
parser :: Parser (String, Int)
parser = do
  name <- word
  spaces
  age <- number
  return (name, age)

Exercises

Verify that the Maybe monad satisfies all three monad laws.
Implement the Either e monad:
```
data Either e a = Left e | Right a
```
Define fmap in terms of return and (>>=) for any monad.
Show that the composition of two monads is not necessarily a monad.
Implement a Tree monad where (>>=) replaces each leaf with a new tree:
```
data Tree a = Leaf a | Node (Tree a) (Tree a)
```
Write a function using the State monad that counts the number of occurrences of a specific element in a list.
Prove that (>=>) is associative and has return as its identity.
Implement the WriterT monad transformer.
Use a free monad to implement a simple calculator DSL with operations for addition, subtraction, and multiplication.
Show that for any monad m, the type m a forms a monoid under the following definition when a is a monoid:
```
instance (Monad m, Monoid a) => Monoid (m a)
```

See:

Monads and applicatives

What is a Monad?

Monads in Programming

The Monad Laws

Common Monads

1. Maybe Monad

2. List Monad

3. State Monad

4. Reader Monad

5. Writer Monad

6. IO Monad

Do Notation

Relationship Between Monad and Applicative

When to Use Applicative vs Monad

Monad Transformers

Kleisli Arrows

Free Monads

Comonads

Laws and Properties

Functor-Monad Relationship

Join Definition

Alternative Monad Laws (using join)

Practical Applications

1. Error Handling

2. Asynchronous Operations

3. Parser Combinators

Exercises

Sessions by Day

Productivity by Hour

Session Completion Rate

Time Spent by Task

Sessions by Day of Week

Session Duration Distribution