slide /
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?
Int
knows nothing about Show
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 '|||||'
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); }
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
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:
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
map(fa)(f compose g) === map(map(fa)(g))(f)
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):
Reader
), and the connection may fail (Validation
)Future
), and may produce multiple results (List
)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.