slide /

The Typeclassopedia

John Kodumal, Atlassian

jkodumal@atlassian

Use left and right arrows to navigate.

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 }

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

What have we gained?

- We can declare instances
*outside*of the types themselves -
`Int`

knows nothing about`Show`

- This is the
*open world assumption* - In Scala, we can
*override*the typeclass instance by putting a new one in scope:def unaryShows(x : Int) : String = { implicit val AltIntShow = new Show[Int] { def shows(i : Int) = (1 to i) map(_ => "|") mkString } shows(x) } println shows(5) // prints '5' println unaryShows(5) // prints '|||||'

`/==`

Subtype polymorphismWhat 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); }

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

*Functional design patterns*- There's mostly* nothing magical about these typeclasses
- In scala, they're provided by a library called scalaz (pronounced scala-zed)
- These examples are based on scalaz 7.0.0
- This is how the hierarchy is defined in Haskell--- it isn't perfect

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

*one exception: `for`

comprehensions and monads

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.

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

- Lists
- Trees
- Maps

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)

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

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

`map(fa)(id) === fa`

(Mapping over the identity function produces the original functor)
`map(fa)(f compose g) === map(map(fa)(g))(f)`

(Mapping over a composed function is the same as mapping over each function)

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.

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

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?

`map`

-like operationLet'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)

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

|@|

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

`Option`

With `point`

, we can express the above example as:

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

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

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:

Monad | Semantics |
---|---|

`Option` |
Anonymous exceptions |

`Reader` |
Read-only environment |

`Validation` |
Descriptive exceptions |

`List` |
Nondeterministic computation |

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

- A data store takes a DB configuration (
`Reader`

), and the connection may fail (`Validation`

) - A computation may be asynchronous (
`Future`

), and may produce multiple results (`List`

) - A remote call may fail if the service is down (
`Validation`

), and we want to log responses (`Writer`

)

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)

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* 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`

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.

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]] = // ??? }

` >>= `

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.