slide /

The Typeclassopedia
John Kodumal, Atlassian
jkodumal@atlassian

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, and monads

*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]) = ...

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

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

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

Monad as Embedded Language

I'll present one 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 Global environment
Validation Descriptive exceptions
List Nondeterministic computation