How is List a monad?

Question

I think I have a basic grasp of Monads and monadic operations but am still a bit stuck on understanding how the magic features of a monadic type get added to the underlying type (hope this makes sense).

For example, I was reading about how a List[T] is a monad. But if I flatMap and map over some Lists sequentially in a for comprehension then isn't it really flatMap and map that are providing the monadic magic?

If I create a List<String> then how is the monadic magic added? Or is a List<T> always a monad in Scala because it just happens to be one of those containers that the language already provides in-built monadic support for?

Answer 1

You're exactly right that flatMap and map are providing the "monadic magic." There is fortunately or unfortunately (depending on how much bad code you've seen) no magic in programming. No amount of abstraction will save you (or someone else) from ultimately writing the code that does the thing you want. Abstraction "just" lets you re-use previously written code and clarify your thoughts around a problem. A monad then is just a concept, an idea, an abstraction, etc.

In the case of Scala this is very literally what the compiler does to a for comprehension, which becomes a series of flatMap, map, withFilter, and filter statements.

A monad (in Scala) can be thought of as just a label for the phenomenon where you happen to have a type constructor T[_] and two functions¹

def f0[A](x: T[A], f: X => T[A]): T[A]
def f1[A](x: A): T[A]

By convention, when they see this phenomenon, the Scala community calls f0 flatMap and usually make it a method so that the x is always the parent class instead of a separate argument. There is also a convention to call f1 point or pure (see scalaz or cats). f1 is also usually a method so that it doesn't end up explicitly taking an argument and just uses its parent class as the x.

Whenever anyone says "such-and-such" is a monad, there is always an implied f0 and f1 which the speaker expects the listener to infer. Strictly speaking "List is a monad" is a mild abuse of terminology. It's short-hand for List along with the functions (xs: List[A], f: A => List[A]) => xs.map(f).flatten (which forms f0) and (x: A) => List(x) (which forms f1) form a monad. Or slightly less obtusely, List along with the standard flatMap on lists and the List.apply constructor form a monad.

Therefore there was never any magic. As part of classifying something as a Monad you had to have provided a notion of flatMap and pure.

There are many ways you could turn this abstraction of a monad into code. The naive way (i.e. Scala with no third-party libraries) is to just agree on a common name for f0 and f1 (e.g. flatMap) and just name your methods that have the appropriate type signature those names. That is essentially what scalac expects you to do for for comprehensions. You could go one step further and try to formalize things with a trait or an abstract class. Maybe call it Monad to be cute and have something like the following:

trait Monad[A] {
  def flatMap(f: A => Monad[A]): Monad[A]

  def pure(x: A): Monad[A]
}

Then you might call anything that extends this Monad an implementation of the monad idea (you might imagine something such as class List[A] extends Monad[A]).

For a variety of practical reasons this turns out to be less than satisfactory and so you end up with the usual solution that looks something like (hand-waving away a lot of other complexity)

trait Monad[F[_]] {
  def flatMap[A](f: A => F[A]): F[A]

  def pure[A](x: A): F[A]
}

that gets implemented by implicits.

---

Footnotes:

1. And some laws/conventions governing their interaction. The practical reason for the existence of those laws is to lend sanity to programmer's lives so they know what to expect when someone tells them that these functions are "monadic." These laws are exactly what makes reasoning about constructs such as monads so useful, but I won't delve into them here because they're adequately explained elsewhere.