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:

  1. An endofunctor $M : \mathcal{C} \to \mathcal{C}$
  2. A natural transformation $\eta : \text{Id}_\mathcal{C} \Rightarrow M$ (called unit or return)
  3. 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:

Equivalently, using join:

The Monad Laws

Monads must satisfy three laws:

  1. Left Identity:

  2. Right Identity:

  3. Associativity:

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

Common Monads

1. Maybe Monad

Handles computations that might fail:

Example:

2. List Monad

Represents non-deterministic computations:

Example:

3. State Monad

Encapsulates stateful computations:

Example:

4. Reader Monad

Provides read-only shared environment:

Example:

5. Writer Monad

Accumulates output alongside computation:

Example:

6. IO Monad

Handles input/output and side effects:

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

Do Notation

The do notation is syntactic sugar for monadic operations:

Relationship Between Monad and Applicative

Every monad is an applicative functor:

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

  • Monad: When later operations depend on earlier results

Monad Transformers

Monad transformers allow combining multiple monadic effects:

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:

Properties:

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:

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

Comonads

A comonad is the categorical dual of a monad:

Example: Non-empty list comonad:

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

Laws and Properties

Functor-Monad Relationship

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

Join Definition

Terminology note: monad join (M (M A) -> M A) is different from order-theoretic join ($a \vee b$), which means least upper bound in a lattice.

Alternative Monad Laws (using join)

  1. Left Identity: join . return = id
  2. Right Identity: join . fmap return = id
  3. Associativity: join . fmap join = join . join

Practical Applications

1. Error Handling

2. Asynchronous Operations

3. Parser Combinators

Exercises

  1. Verify that the Maybe monad satisfies all three monad laws.

  2. Implement the Either e monad:

  3. Define fmap in terms of return and (>>=) for any monad.

  4. Show that the composition of two monads is not necessarily a monad.

  5. Implement a Tree monad where (>>=) replaces each leaf with a new tree:

  6. Write a function using the State monad that counts the number of occurrences of a specific element in a list.

  7. Prove that (>=>) is associative and has return as its identity.

  8. Implement the WriterT monad transformer.

  9. Use a free monad to implement a simple calculator DSL with operations for addition, subtraction, and multiplication.

  10. Show that for any monad m, the type m a forms a monoid under the following definition when a is a monoid:

See:
25
25
Ready to start
Monads and applicatives
Session: 1 | Break: Short
Today: 0 sessions
Total: 0 sessions