explanation-functor-monad.md

I think the better approach is to know what is a Functor before asking about Monads.

A Functor is a Higher Kinded Type/Type Constructor/Function at the type level that has a certain shape (that is, it implements a map function). A Functor is also what's known as a typeclass. A Monad is also a typeclass

Typeclasses are a form of ad-hoc polymorphism that let you add functionality to existing code that you may or may not have written.

Here's is the basic definition of a Functor

trait Functor[F[_]] {
    def map[A, B](fa: F[A])(f: A => B): F[B]
}

As you can see F[_] represents a higher kinded type or a function at the type level, it's not a simple proper type like Int or String. Examples of Higher Kinded Types are List, Option, Future, etc. A higher kinded type is a function at the type level, this means you can pass in an argument at the type level so pass A to F[_] where A is a simple proper type, therefore passing A to F[_] results in F[A] which is now a simple proper type.

As you see from the signatures, a Functor (and Monad as well) abstract over Higher Kinded Types

Okay great, what does it mean when you hear a List is a Monad or a Future is a Monad. As Josh Suereth points out, it's actually somewhat incorrect to say a List is a Monad or a Future is a Monad. It's more like a List has a Monad implementation and a Future has a Monad implementation.

Okay I know I switched to Monads but let's get back to Functors. Both List and Future also have Functor implementations.

Let's implement it for List. Remember List is a Higher Kinded Type so it meets the requirements of F[_] defined in the Functor above

implicit val listFunctor = new Functor[List] {
	def map[A, B](fa: List[A])(f: A => B): List[B] = 
		for (each <- fa) yield f(each)
}

Yes I know I cheated by using a for-comprehension (because under the hood it uses flatMaps and maps) and List already possesses .map defined as part of the language.

But now, officially List has a Functor, so you can do listFunctor.map(List(1, 2, 3))(x => x + 1) == List(2, 3, 4)

Yes I know you can do it like List(1, 2, 3).map(x => x + 1) but I'm showing you an illustration

Okay, now let's look at what Monads are (somewhat):

trait Monad[M[_]] extends Functor[M] {
  def flatMap[A, B](ma: M[A])(f: A => M[B]): M[B]
  def pure[A](a: A): M[A]
}

I said somewhat because a Monad is also an Applicative (Applicative is another typeclass) but we won't get into that here As you can see in addition to having map, a Monad posses a flatMap and if you look closely that mapper function f has a type signature of A => M[B] meaning the mapper function produces a result wrapped in a Monad context M. However, if you look at the return type, it's M[B] so what flatMap does is remove nesting. There's also pure which lifts a simple proper type A into a Monadic context.

Let's see an implementation of Monad for List, this time without cheating and using mutation :-(

val listMonad = new Monad[List] {
  override def flatMap[A, B](ma: List[A])(f: (A) => List[B]): List[B] = {
    // pretend I don't already have flatMap
    var list = List.empty[B]
    for (each <- ma) list ++= f(each)
    list
  }

  override def pure[A](a: A): List[A] = List(a)

  override def map[A, B](fa: List[A])(f: A => B): List[B] = {
    var list = List.empty[B]
    for (each <- fa) {
      list =  f(each) +: list
    }
    list
  }
}

Now I didn't have to use mutation, I could have used recursion to perform this implementation. For example, here is a tail recursive version of map. Note that tail recursion means that the recursive call is the last expression that the function does for the recursive case.

def map[A, B](fa: List[A])(f: A => B): List[B] = {
  @tailrec
  def go(lb: List[B], la: List[A]): List[B] = {
    la match {
      case head :: tail => go(f(head) +: lb, tail)
      case Nil => lb
    }
  }
  go(List.empty[B], fa)
}

Okay, let's look at what we can do now that we have a Monad implementation for List

listMonad.pure(1) == List(1)
listMonad.flatMap(List(1, 2, 3, 4))(x => List(x - 1, x + 1)) == List(0, 2, 1, 3, 2, 4, 3, 5)

Notice my mapper function produces nesting and so I used flatMap, if I had used map

listMonad.map(List(1, 2, 3, 4))(x => List(x - 1, x + 1)) == List(List(3, 5), List(2, 4), List(1, 3), List(0, 2))

I would have ended up with nesting. Now you might think that okay cool, flatMap is used to remove nesting. Yes, flatMap is used to remove nesting in Lists. flatMap is more general than that, it can be thought of as sequencing operations in monadic contexts (run computation A and when that finishes run computation B and computation's A result is available to B so B can use it). A great example of this is Futures. You may have a use case where you need to fetch data from two different data sources and you need to do it asynchronously because who blocks these days? One data source gives you Pictures and the other gives you User information. You want to pick out the Pictures belonging to the user. This is how you can do it. Remember Future has a Monad (somewhat, you can formally define it but it is a part of the language).

val webReqUser: Future[User] = ...
val webReqPics: Future[List[Picture]] = ...
val usersPics: Future[List[Picture]] = webReqUser.flatMap(user => 
   // webReqPics.map(...) returns a Future meaning this mapper function produces nesting so we use flatMap 
   webReqPics.map(pics => 
     pics.filter(p => p.user == user)
   )
)

Notice this is a series of flatMaps and maps so you can use a for-comprehension since this is sugar for flatMaps and maps

val usersPics: Future[List[Picture]] = for {
  user <- webReqUser
  pics <- webReqPics
  if pics.filter(p => p.user == user)
} yield pics

The main reasons why Monads, Functors and all these typeclasses are important are because they abide by laws that make your code equationally reasonable

Monoids abstract over simple types like Int, String and Option[Int] and List[Int] but not higher kinded types like List and Option:

trait Monoid[A] {
  def empty: A
  def combine(x: A, y: A): A
}

Notice the lack of a type constructor like F[_] and just the use of a simple type A for the type parameter

Here is an implementation of the Monoid typeclass for Ints under addition:

implicit val intAdditionMonoid: Monoid[Int] = new Monoid[Int] {
  def empty: Int = 0
  def combine(x: Int, y: Int): Int = x + y
}

// Usage
def combineMe(x: Int, y: Int)(implicit monoidEvidence: Monoid[Int]): Int = 
  monoidEvidence.combine(x, y)