In previous chapters, we see how functors and monads allow us to sequence operations in a program using map and flatMap. Applicative functors are a related abstraction that is less powerful than monads, and are more common.
Methods that define a Functor:
def map[A,B](a: F[A])(f: A => B): F[B]
Methods that define a Monad:
trait Monad[F[_]] extends Functor[F] {
def unit[A](a: => A): F[A]
def flatMap[A,B](ma: F[A])(f: A => F[B]): F[B]
}
And the methods below can be derived from the above methods for Monad's. And since we can implement a map here, we can also extend the Functor trait. (All monads are functors)
def map[A,B](ma: F[A])(f: A => B): F[B] =
flatMap(ma)(a => unit(f(a)))
def map2[A,B,C](ma: F[A], mb: F[B])(f: (A, B) => C): F[C] =
flatMap(ma)(a => map(mb)(b => f(a, b)))
trait Applicative[F[_]] extends Functor[F] {
def map2[A,B,C](fa: F[A], fb: F[B])(f: (A, B) => C): F[C]
def unit[A](a: => A): F[A]
We can also use those primitive types to derive map, so Applicative's are also Functors.
def map[B](fa: F[A])(f: A => B): F[B] =
map2(fa, unit(()))((a, _) => f(a))
All monads are Applicative's, because we can also implement map2 in terms of flatMap.
The name applicative comes from the fact that we can formulate the Applicative interface using an alternate set of primitives, unit and the function apply, rather than unit and map2. (Exercise 12.2)
trait Applicative[F[_]] extends Functor[F] {
def apply[A,B](fab: F[A => B])(fa: F[A]): F[B]
def unit[A](a: => A): F[A]
- Applicative computations have fixed structure and simply sequence effects, whereas monadic computations may choose structure dynamically, based on the result of previous effects.
- Applicative constructs context-free computations, while Monad allows for context sensitivity.
case class Row(date: Date, temperature: Double)
val F: Applicative[Parser] = ... val d: Parser[Date] = ...
val temp: Parser[Double] = ...
val row: Parser[Row] = F.map2(d, temp)(Row(_, _)) val rows: Parser[List[Row]] = row.sep("\n")
val F: Monad[Parser] = ...
val d: Parser[Date] = ...
val temp: Parser[Double] = ...
val header: Parser[Parser[Row]] = ... val rows: Parser[List[Row]] =
F.flatMap (header) { row => row.sep("\n") }
# This flatMap depends on the result of the row and the previous result
Applicative instances compose, but Monad instances do not.
Because Applicative is “weaker” than Monad, this gives the interpreter of applicative effects more flexibility. To take just one example, consider parsing. If we describe a parser without resorting to flatMap, this implies that the structure of our grammar is determined before we begin parsing. Therefore, our inter- preter or runner of parsers has more information about what it’ll be doing up front and is free to make additional assumptions and possibly use a more effi- cient implementation strategy for running the parser, based on this known structure. Adding flatMap is powerful, but it means we’re generating our parsers dynamically, so the interpreter may be more limited in what it can do.
import cats.Monad
import cats.syntax.applicative._ // for pure
import cats.syntax.flatMap._ // for flatMap
import scala.language.higherKinds
// Hypothetical example. This won't actually compile:
def compose[M1[_]: Monad, M2[_]: Monad] = {
type Composed[A] = M1[M2[A]]
new Monad[Composed] {
def pure[A](a: A): Composed[A] =
a.pure[M2].pure[M1]
def flatMap[A, B](fa: Composed[A])
(f: A => Composed[B]): Composed[B] =
// Problem! How do we write flatMap?
???
}
}
If we fix the Monad to Option, we can write flatMap like this (notice how we use None, which is Option-specific)
def flatMap[A, B](fa: Composed[A])
(f: A => Composed[B]): Composed[B] =
fa.flatMap(_.fold(None.pure[M])(f))
Variant of Either that accumulates errors.
We discovered applicative functors by noticing that our traverse and sequence functions (and several other operations) didn’t depend directly on flatMap.
trait Traverse[F[_]] {
def traverse[G[_]:Applicative,A,B](fa: F[A])(f: A => G[B]): G[F[B]] =
sequence(map(fa)(f))
def sequence[G[_]:Applicative,A](fga: F[G[A]]): G[F[A]] =
traverse(fga)(ga => ga)
}
List[Option[A]] => Option[List[A]] (a call to Traverse[List].sequence with Option as the Applicative) returns None if any of the input List is None; otherwise it returns the original List wrapped in Some.
case class OptionT[M[_],A](value: M[Option[A]])(implicit M: Monad[M]) {
def flatMap[B](f: A => OptionT[M, B]): OptionT[M, B] =
OptionT(value flatMap {
case None => M.unit(None)
case Some(a) => f(a).value
})
}
OptionT[List, A]
// Is the same as List[Option[A]]
EitherT[Option, A, B]
// Is the same as Option[Either[A, B]]