Functions, Products, Coproducts, Functors, and Monads

monads.md

There are a couple of basic constructions from math the end up being data types in (for example) cats in scala. Unfortunately, the names of the data types tend to obscure the underlying mathematical construction IMHO. This is meant to be a short description of a few data types in terms of products, co-products and functions.

Writer

In scala the Tuple2 aka (?,?) is the canoncical product of two types. This is a covariant functor in both of its type parameters. Here's map in the second parameter (for (A,?)).

def map[A,B,C](x: (A,B), f: B => C): (A,C) = (x._1, f(x._2))

If the first parameter is a semigroup then we can define flatten and it is therefore a monad. The writer monad.

def flatten[A: Semigroup, B](x: (A, (A, B))): (A, B) = (x._1 |+| x._1._1, x._1._2)

Yes the code is ugly, but we just combine the only two As that we have; we can do this because A is a Semigroup.

Reader

In scala, Function1 aka ? => ? is the Hom functor. It is a contravariant functor in the first argument and covariant in the second argument. Here's map in the second argument (for A => ?).

def map[A,B,C](x: A => B, f: B => C): A => C = f compose x

We can define flatten making it a monad. The reader monad.

def flatten[A,B](x: A => A => B): A => B = { a => x(a)(a) }

State

In terms of functors this is the composition of Reader and Writer, i.e. A => (A, ?) but we need a definition of flatten to make it a monad. The state monad

def flatten[A,B](x: A => (A, A => (A,B))): A => (A, B) = { a =>
  val (nextA, f) = x(a)
  f(nextA)
}

Either

In scala Either[A,B] is the canonical coproduct. It is a covariant functor in both of its type parameters. Here's map in the second parameter (For Either[A,?].

def map[A,B,C](x: Either[A,B], f: B => C): Either[A,C] = x match {
  case Right(b) => Right(f(b))
  case Left(a) => Left(a)
}

We can define flatten and therefore have a monad.

def flatten[A, B](x: Either[A, Either[A, B]]): Either[A, B] = x match {
  case Left(a) => Left(a)
  case Right(Left(a)) => Left(a)
  case Right(Right(b)) => Right(b)
}

Validated

Same as Either but it's main use is when the left type is a semigroup, which allows a nicer Applicative. The gist is that errors are on the left and we want to accumulate them for anything that happens in parallel. Note that even though it's technically a monad, in cats they call flatMap andThen because the ap that you get for free with flatMap is different that this one that relies on the semigroup structure of A. I'll write it in terms of Either.

def ap[A: Semigroup, B, C](x: Either[A, B], ef: Either[A, B => C]): Either[A,C] = (x, ef) match {
  case (Right(b), Right(f)) => Right(f(b))
  case (Left(a1), Left(a2)) => Left(a1 |+| a2) // Combine multiple errors.
  case (Left(a), _) => Left(a)
  case (_, Left(a)) => Left(a)
}