slide /

The Typeclassopedia
John Kodumal, Atlassian
jkodumal@atlassian

Use left and right arrows to navigate.
Japanese translation by Shingo Omura is here.

Typeclasses: Open-world interfaces

Typeclasses are akin to Java interfaces, but more flexible.

We declare them in scala with traits:

trait Show[A] {
	def shows(a: A): String
}

Note the subtle difference compared to the mix-in "interface" style:

trait Show {
	def shows(): String
}	

We also need a way to add a type to the class:

implicit val IntShow = new Show[Int] {
	def shows(a: Int) = a.toString
}

Using a typeclass

We use scala implicits:

def shows[A](a : A)(implicit shower: Show[A]) = shower.shows(a)

Or alternatively, using context bounds:

def shows[A : Show](a : A) = implicitly[Show[A]].shows(a)

(implicitly is part of predef: def implicitly[A](implicit a : A) = a)

Scalaz pimps a set of common typeclasses for us, so we can just do:

3.shows // must have a "Show[Int]" instance in scope, or will fail to type check

The Open-World Assumption

What have we gained?

Typeclasses /== Subtype polymorphism

What we can't do with Scala's typeclasses (not easily at least):

interface Show {
	String show();
}

class Foo extends Show {
	public String show() {
		return "a foo";
	}
}

class Bar extends Show {
	public String show() {
		return "a bar";
	}
}

List[Show] showList = new ArrayList(new Foo(), new Bar(), new Foo());

for (String s : showList) {
	System.out.println(s.show);
}

The Typeclassopedia

A set of interrelated typeclasses that have proven handy for structuring functional code:

We'll cover functors, applicative functors, monad, monad transformers, and traversable

*one exception: for comprehensions and monads

Introducing Functor

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.

Fun with Functions as Functors

"Thing you can map over" leads to obvious examples:

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)))
}
Pop quiz: I defined map in a slightly funky way. What simple concept is this expressing?

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)	

Aside: This is where the "box" analogy starts falling apart, and we start throwing around vague terms like "computational context"...

Functor Laws

There are some additional constraints on Functors that make them "behave appropriately":

These laws prevent ridiculous definitions of map, and make it possible to predict how functions behave.

Note that these laws are not enforced by the type system.

Aside: Parametricity

With great weakness comes great power...

Ben "Pierce" Parker

Mo' power, mo' problems...

Biggie Smalls
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?

Introducing Applicative Functor

You can get pretty far on map alone... but sometimes you need more.

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?

We'll need a more powerful map-like operation

Applicative Functors

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)

Applicative Syntax

In Haskell, things look a little more obvious:

(+) <$> parse("3") <*> parse("Nope") 

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"))(_ + _)

|@|

(The Macaulay Culkin Function)

More on Applicatives

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]) (_ + _)

A Tutorial on Monads

Yes, it's a trap

Introducing Monads

As before, we'll introduce a new task and see what goes wrong...

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]] ??

Monads

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)

Syntactic Sugar to the Rescue

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!)

A Monad Hidden in Plain Sight

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.

Motivating the Reader Monad

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.

Monad as Embedded Language

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:

Monad Semantics
Option Anonymous exceptions
Reader Read-only environment
Validation Descriptive exceptions
List Nondeterministic computation

Languages with Multiple Effects

In the real world, we have to deal with multiple monads (effects):

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)

...all the way down

They see me composin'... they hatin'

Life would be easier if monads composed. Given monads M[_] and N[_], is M[N[_]] a monad?

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

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!

De-turtling our previous example

scalaz defines transformers for most common monads:

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!)

The Monad Transformer Typeclass

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)

Another take on composing monads

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]
}
		
Exercise: Define >>= using join and map

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.

Introducing Traverse

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...

Monad composition for free

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.