- `Writer w a` supports monadic logging
  - `w` is the monoid type parameter that is `mappend`ed to with every bind
  - `a` is the type parameter that contains the result
  - "Writer of w with result a"
  - In `Control.Monad.Writer`
  - If you want to log diagnostic messages, `[String]` can be the left type
- Difference lists
  - Are *functions* that prepend some list to their arguments.
  - Example of difference list: `(xs++)` (is implementation of `toDiffList`)
  - Identity difference list: `([]++)` or `id`
  - `mappend` is simply represented as function composition. `f >>= g = f . g`, where both sides are diff lists.
  - Exist to allow for *efficient concatenation*
    - If you used `Writer [String]` to log a bunch of messages sequentially, you would be doing something like:
      - `(((a ++ b) ++ c) ++ d) ++ e`
      - Which would be inefficient because with `++` the lhs has to be rewalked, resulting in quadratic behavior. (*inside-out*, left-associative evaluation)
    - With `DiffList String` you get something like `a . b . c . d . e`.
      - When you convert it to a regular list via `fromDiffList xs` or `xs []`, the list held by `e` is prepended first, then the list by `d`, then `c`, etc.
        - This results in *outside-in*, right-associative evaluation: `(++) a' $ (++) b' $ (++) c' $ (++) d' $ (++) e' []`
          - Which means linear behavior
- Functions are monads
  - `h >>= f = \w -> f (h w) w`
  - Very useful to think of a function as a box containing some value, with the context that is needs to be applied to get at that value.
  - Their monad instance is in `Control.Monad.Instances`
    - Referred to as "reader monad"?
- State monad
  - A *stateful computation* (such as `random`) is a function that takes some state, and contains a pair containing a value and some new state.
    - `statefulComputation :: s -> (a, s)`
    - Stateful computations can be thought of as values with context, too.
      - The actual value is the result
      - The context is we have to provide some initial state to get that result, and also get a final state back along with the result.
  - The `State` monad is a `newtype` wrapper around `s -> (a, s)`.
  - Bind implementation can be thought of as: given some initial state, invoke the stateful computation and get an `(a, s)`, get the rest of the code to execute via invoking the rhs with the result `a`, and then invoke that code with the new state `s`.
    - Can also view `f` (the rhs) as a continuation? Do the stateful computation and invoke `f` with `a` and `s`?
  - `State s a`, `s` is the state and `a` is the result
    - To be clear, the `State` monad is a wrapper over *code* to be executed. `s` is the state itself.
  - `get`: takes the current state and presents it as the result. `get = State $ \s -> (s, s)`
  - `put`: replaces the current state with another state. `put newState = State $ \s -> ((), newState)`
    - Notice that the previous state, the bound parameter `s`, is ignored
  - `State` is a perfect wrapper for `random`. `state random`
    - Can be used by i.e. a function with type `State StdGen (Bool, Bool, Bool)` for flipping 3 coins
- `Either a` is a monad, conditional on `(Error a)`
  - It has a special implementation for `fail`: `fail msg = Left (strMsg msg)`
    - `strMsg` is a function defined by `Error` types and creates an error of type `a` from a string