The Typeclassopedia

John Kodumal, LaunchDarkly

john@launchdarkly.com

Use left and right arrows to navigate.

Japanese translation by Shingo Omura is here.

A functor is simply something you can map over. It defines a single method:

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

An instance for Option:

implicit val OptionFunctor = new Functor[Option] {
	def map[A, B](fa: Option[A])(f: A => B) : Option[B] = 
		fa match {
			case Some(a) => Some(f(a))
			case None => None
		}
}

In Haskell, the arguments are reversed:

class Functor f where  
    fmap :: (a -> b) -> f a -> f b	

In the Haskell version, we see how f is lifted into the functor context.

Let's look at something less obvious: Functions!

implicit def FunctionFunctor[R] = new Functor[({type l[a] = R=>a})#l] {
	def map[A, B](fa: R => A)(f: A => B) : R => B = (x => f(fa(x)))
}

Again, the Haskell version makes this much clearer. Start with fmap:

    fmap :: (a -> b) -> f a -> f b	

Substitute r -> a for f a

    fmap :: (a -> b) -> (r -> a) -> (r -> b)	

def fun[A](a : A) : A = ...

What is fun?

val x : List[Int] = ...
def foo[F[_] : Functor](fs : F[Int]): F[Int] = ...

What is foo(x).length?

Consider the following:

def parse(s : String) : Option[Int] = ...

Let's try to add two parsed integers with map:

parse("3").map((x: Int) => (y: Int) =>  x + y) // ???

We're left with an Option[Int => Int]... but what can we do with that?

Let's add the power we need to Functor:

trait Applicative[F[_]] extends Functor {
	def <*>[A, B](fa: F[A])(f : F[A => B]) : F[B]
	// ... there's more to Applicative, to be shown shortly
}

Which makes our previous example look something like:

(parse("3")).<*>(parse("Nope").map(x => (y : Int) => x + y))

(Yuck)

Generalizing a bit, we go from calling a pure function:

f x y z

To calling a function on "effectful" arguments:

f <$> x <*> y <*> z

Scalaz's ApplicativeBuilder improves the situation somewhat:

(parse("3") |@| parse("Nope"))(_ + _)

What if some of the arguments aren't Option?

	(parse("3") |@| 4 /* uh oh, no macaulay for my culkin */) (_ + _)

One small addition to our type class:

trait Applicative[F[_]] extends Functor {
	def <*>[A, B](fa: F[A])(f : F[A => B]) : F[B]
	def point[A](a : A): F[A]
}

Exercise: Define the applicative instance for Option

With point, we can express the above example as:

	(parse("3") |@| 4.point[Option]) (_ + _)

Take our parse example again:

def parse(s : String) : Option[Int] = ...

What if our input String was an optional query parameter?

val x : Option[String] = params.get("x")

We've got an Option[String] and a function String => Option[Int]

When all you have is a map hammer...

x.map(parse) // Option[Option[Int]] ??

Let's add the power we need to Applicative:

trait Monad[F[_]] extends Applicative {
	def >>=[A, B](fa: F[A])(f : A => F[B]) : F[B]
}

This is pronounced bind

It makes our previous example look something like:

params.get("x") >>= parse // Option[Int]

A more complete web-based calculator example:

params.get("x") >>= parse >>= (x => (params.get("y") >>= parse) map (_ + x) )

(Yuck)

The last example hints at a fairly typical pattern:

monadicX >>= (x => monadicY >>= (y => monadicZ map (z => x+y+z))) 

We have nested bind's with a final map

Reformatting it a bit:

monadicX >>= (x => 
monadicY >>= (y => 
monadicZ map (z => 
   x+y+z
))) 

With Scala for comprehensions, this becomes:

for {
	x <- monadicX
	y <- monadicY
	z <- monadicZ
} yield x + y + z

(Much nicer!)

Let's move beyond the Option example. Recall that there is a functor instance for functions:

def map[A, B](fa: R => A)(f: A => B) : R => B = (x => f(fa(x)))
	

What about a monad instance?

implicit def FunctionMonad[R] = new Monad[({type l[a] = R=>a})#l] {
	def >>=[A, B](fa: R => A)(f: A => R => B) : R => B = (x => f(fa(x))(x))
	...
}
		

This is commonly referred to as the Reader monad. It looks a bit inscrutable, so let's see where it may come in handy.

Let's say we need to build absolute URLs for a web app, and the app has a base URL:

def makeAbs(base: AbsURL, url: URL): AbsURL = AbsURL(base + url)

But this leads to a lot of repetition:

val links = Map("self" -> makeAbs(baseURL, "/widgets/523"),
                "parent" -> makeAbs(baseURL, "/widgets") )

Let's redefine makeAbs with Reader:

def makeAbs(url: URL): Reader[AbsURL, AbsURL] = 
	Reader(base => AbsURL(base + url))

All we've done is a syntactic switcharoo, but this lets us write:

(for {
	self   <- makeAbs("/widgets/523")
	parent <- makeAbs("/widgets")
} yield Map("self" -> self, "parent" -> parent))(baseURL)

Think of Reader as a computation with a read-only environment (the argument) that can be supplied to produce a result.

Here's a stab at providing an intuition for monads. Consider:

for {
	x <- monadicX
	y <- monadicY
} yield x + y

Q: What does this code do?

A: Depends on the monad.

A monadic for comprehension is an embedded programming language with semantics defined by the monad:

Let's see why working with stacked monads gets ugly. We'll add a read-only environment to our calculator:

type Env = Map[String, Int]
def lookup(s: String): Reader[Env, Option[Int]] = 
	Reader(env => env.get(s) orElse parse(s))

Now we'll add two numbers, using Reader to avoid repeating the env argument:

for {
 xOpt <- lookup("3")
 yOpt <- lookup("y")
} yield (for {
          x <- xOpt
          y <- yOpt
         } yield x + y)

(Yuck)

We can work this out for functors:

implicit val ComposedFunctor[M: Functor, N: Functor] = new Functor[...] {
	def map[A, B](fa: M[N[A]])(f: A => B) : M[N[B]] = fa.map(_.map(f(_)))
}

It's ironic (like rain on your wedding day), but in general, monads don't compose. Try it:

implicit val ComposedMonad[M: Monad, N: Monad] = new Monad[...] {
	def >>=[A, B](fa: M[N[A]])(f: A => M[N[B]]) : M[N[B]] = // ???
}

Monad transformers represent one solution. A transformer is a "wrapper" around a monadic value:

case class OptionT[F[+_], +A](run: F[Option[A]]) { 
	// More to be shown shortly 
}

The wrapped value will expose the underlying monad's utility functions:

OptionT(List(Some(3), None, Some(4))).getOrElse(0) // List(3, 0, 4)

Most importantly, we'll make the transformer itself a monad:

case class OptionT[F[+_], +A](run: F[Option[A]]) { 
	def >>=[B](f: A => OptionT[F, B])(implicit F: Monad[F]): OptionT[F, B] = 
		new OptionT[F, B](
			self.run >>= (a => a.match {
								case None => F.point(None)
								case Some(s) => f(s).run
							}))  
	...
}

We can stack transformers arbitrarily deep!

scalaz defines transformers for most common monads:

• OptionT
• ListT
• EitherT
• ReaderT, aka Kleisli

Let's clean up our previous example with ReaderT. Recall we had:

for {
 xOpt <- lookup("3") 
 yOpt <- lookup("y") 
} yield (for {
          x <- xOpt
          y <- yOpt
         } yield x + y)

With ReaderT:

for {
	x <- Kleisli(lookup("3"))
	y <- Kleisli(lookup("y"))
} yield x + y

(Much nicer!)

There is a typeclass for monad transformers, which defines a single operation liftM:

trait MonadTrans[F[_[_], _]] {
  def liftM[G[_] : Monad, A](a: G[A]): F[G, A]
}

liftM gives us the ability to "lift" computations in the base monad into the transformed monad:

(for {
	x <- OptionT(List(Some(3), None))
	y <- List(1,2).liftM[OptionT]
} yield x + y).run // List(Some(4), None, Some(5), None)

An alternative formulation of Monad provides some insight into the composition problem. Instead of bind (>>=), it's sufficient to implement a method called join:

trait Monad[F[_]] extends Applicative {
	def join[A](fa: F[F[A]]): F[A]
}
		

Using join, let's try to make a monad for M[N[_]]. Substituting M[N[_]] for F[_], we get:

def join[A](fa: M[N[M[N[A]]]]]): M[N[A]]

(Whew!)

The join methods defined on M and N don't help, because they're "blocked" by the other monad. But what if we could "commute" the monads, or change the sequence of the M's and N's?

def sequence[A](a: M[N[A]]): N[M[A]]

This works! It's possible to define monad composition given the sequence function.

The Traverse typeclass provides exactly this. It gives the ability to commute two functors:

trait Traverse[M[_]] extends Functor {
	def sequence[N[_]: Applicative, A](mna: M[N[A]]): N[M[A]]
}
	

(scalaz uses an alternative formulation based on a function traverse: M[A] => (A => N[B]) => N[M[B]])

Traverse is tremendously handy in its own right. For example, let's turn a list of asynchronous computations into an asynchronous computation of a list:

List(future { doCalc1() }, future { doCalc2() }).sequence // Future[List[Int]]

One of the benefits of living in a typed fantasy land...

Assuming we also have a Traverse requirement on monad N, we can get a composed monad for "free":

implicit val ComposedMonad[M: Monad, N: Monad: Traverse] = new Monad[...] {
	def >>=[A, B](fa: M[N[A]])(f: A => M[N[B]]) : M[N[B]] = // ???
}	

Exercise: Implement >>= for ComposedMonad.

This could be used to supply monad transformer implementations, though the "free" transformer doesn't always give the semantics we want. Note that scalaz doesn't use this "free" formulation.