ccarlile/cats.org

## cats.org

      
    Raw
  

              cats.org
            
          
    #+title Introduction to Cats
Introduction to Cats

Cats is a library for Functional Programming in Scala.
Typeclasses

Monoid, Semigroup, FlatMap, etc.
Also provides instances of these typeclasses for scala types that support them, as well as syntax enhancements for ergonomics.
Data Types

OptionT, Validated, etc.
Typeclasses


  The Expression Problem is a new name for an old problem. The goal is to definea datatype by cases, where one can add new cases to the datatype and newfunctions over the datatype, without recompiling existing code, and while retaining static type safety (e.g., no casts).
  
    Phil Wadler
  

Typeclasses are a solution to the expression problem. They enable a “has-a” relationship between functionality and data that implements it, instead of the “is-a” relationship induced in OO.
Anatomy of a Typeclass - the typeclass

A typeclass declares a certain kind of behavior. Here, the type class offers a single operation, write, which takes a parameterized A and writes some Json
// Define a very simple JSON AST
sealed trait Json
final case class JsObject(get: Map[String, Json]) extends Json
final case class JsString(get: String) extends Json
final case class JsNumber(get: Double) extends Json
final case object JsNull extends Json

// The "serialize to JSON" behaviour is encoded in this trait
trait JsonWriter[A] {
  def write(value: A): Json
}
Anatomy of a Typeclass - the implementation

Now that we have some behavior we need to implement, we can define some simple implementaions for our data.
final case class Person(name: String, email: String)

object JsonWriterInstances {
  implicit val stringWriter: JsonWriter[String] =
    new JsonWriter[String] {
      def write(value: String): Json =
        JsString(value)
    }

  implicit val personWriter: JsonWriter[Person] =
    new JsonWriter[Person] {
      def write(value: Person): Json =
        JsObject(Map(
          "name" ->  JsString(value.name),
          "email" -> JsString(value.email)
        ))
    }

  // etc...
}
Anatomy of a typeclass - using the typeclass

Now we can write generic values to JSON, provided we have the appropriate instance of writer available:
object Json {
  def write[A](value: A)(implicit writer: JsonWriter[A]) = writer.write(value)
}
The compiler can find implicit parameters if they are in implicit scope. Implicit scope includes:

  Lexical Scope (imports work)
  Companion objects of the types of the implicit parameter. Given an HKT - F[A], for example - companion object of F and of A are searched
    import JsonWriterInstances._

Json.toJson(Person("Dave", "dave@example.com"))
// res1: Json = JsObject(
//   Map("name" -> JsString("Dave"), "email" -> JsString("dave@example.com"))
// )
    
  
Cats Typeclass heirarchy

Cats uses inheritance between typeclasses to maintain a heirarchy of behavior, induced by notions from category theory and algebra.

A brief tour of the heirarchy - Semigroup

trait Semigroup[A] {
  def combine(x: A, y: A): A
}
A very simple typeclass. Take two values of type A and combine them. combine must be associative, meaning for all a and b:
combine(combine(a,b), c) == combine(a, combine(b, c))

In other words, the order you combine doesn’t matter, as long as the ordering of operands is conserved.
Lots of things are semigroups.
object SemigroupInstances {
  implicit def integerSemigroup: Semigroup[Int] = new Semigroup[Int] {
    def combine(x: Int, y: Int) = x + y
  }

  implicit def stringSemigroup: Semigroup[String] = new Semigroup[String] {
    def combine(x: String, y: String) = ???
  }

  implicit def listSemigroup[A]: Semigroup[List[A]] = new Semigroup[List[A]] {
    def combine(x: List[A], y: List[A]) = ???
  }

  implicit def boolSemigroup: Semigroup[Boolean] = new Semigroup[Boolean] {
    def combine(x: Boolean, y: Boolean) = ???
  }
}
And by importing cats syntax, we have the useful spaceship operator for combination
import cats.implicits._

1 |+| 2
A brief tour of the heirarchy - Monoid

A monoid is a semigroup with a zero, or empty value. Combining the empty value with any other a will give you a
trait Monoid[A] extends Semigroup[A] {
  def empty: A
}
What is the zero for Int, List, and String?
  Harder: What is the zero for Option?
// option monoid, assuming we can combine the inner type:
implicit def optionMonoid[A: Semigroup]: Monoid[Option[A]] = new Monoid[Option[A]] {
  def append(f1: Option[A], f2: => Option[A]) = (f1, f2) match {
    case (Some(a1), Some(a2)) => Some(Semigroup[A].append(a1, a2))
    case (Some(a1), None)     => f1
    case (None, Some(a2))     => f2
    case (None, None)         => None
  }

  def zero: Option[A] = None
}
// Monoid[Option[Int]].empty == None
// Monoid[Option[Int]].combine(Some(1), None) = Some(1)
// Monoid[Option[Int]].combine(Some(1), Some(2)) = Some(3)

// A monoid on higher kinds, so that we don't have to know anything about the inner A
trait MonoidK[F[_]] extends SemigroupK[F] { self =>
  def empty[A]: F[A]
}
// MonoidK[Option].empty[Int] == None
// Some(1) |+| None == None
// Some(1) |+| Some(2) == Some(1)
Trick question: What is the zero for Boolean?
A brief tour of the heirarchy - Functor

In category theory, a functor is a mapping between different categories (types), that follow a couple of laws that help clarify composition. In practice (i.e. while writing programs), a Functor is a type that allows mapping from one type to another.
trait Functor[F[_]] { self =>
  def map[A, B](fa: F[A])(f: A => B): F[B]
}

trait FunctorLaws[F[_]] extends InvariantLaws[F] {
  def covariantIdentity[A](fa: F[A]): IsEq[F[A]] =
    fa.map(identity) <-> fa

  def covariantComposition[A, B, C](fa: F[A], f: A => B, g: B => C): IsEq[F[C]] =
    fa.map(f).map(g) <-> fa.map(f.andThen(g))
}
Lots of things are functors.
A brief tour of the heirarchy - Applicative Functors

Applicative functors allow us to combine values in context. Given an F[A] and F[B],  an attempt to combine these values in context with a vanilla functor will yield F[F[(A, B)]].  While we can use flatten to get to a reasonable F[A], not all data types support it, so in those cases where we can lift values into context we can get by with Applicative
trait Applicative[F[_]] extends Functor[F] {
  def ap[A, B](ff: F[A => B])(fa: F[A]): F[B]

  def pure[A](a: A): F[A]

  def map[A, B](fa: F[A])(f: A => B): F[B] = ap(pure(f))(fa)

  def product[A, B](fa: F[A], fb: F[B]): F[(A, B)] =
    // calling ap[B => (A, B), (A, B)]
    ap(map(fa)(a => (b: B) => (a, b)))(fb)
}
I’ve condensed Applicative and Apply. Use Apply to lift a value into a pure context, use Applicative to combine values
A brief tour of the heirarchy - Monad

Now we have all the ingredients except one to make a monad. We need Flatmap:
trait FlatMap[F[_]] extends Apply[F] {
  def flatMap[A, B](fa: F[A])(f: A => F[B]): F[B]

  def flatten[A](ffa: F[F[A]]): F[A] =
    flatMap(ffa)(fa => fa)
}
And the monad definition falls out simply, assuming our definitions are lawful.
trait Monad[F[_]] extends FlatMap[F] with Applicative[F] {
  override def map[A, B](fa: F[A])(f: A => B): F[B] =
    flatMap(fa)(a => pure(f(a)))
}
We redefine map to be in terms of our lawful flatMap. The monad laws are as follows:
# left identity:
(Monad[F].pure(x) flatMap {f}) === f(x)
# right identity:
(m flatMap {Monad[F].pure(_)}) === m
# associativity:
(m flatMap f) flatMap g === m flatMap { x => f(x) flatMap {g} }
Where Applicative lets us compose values in a context, Monad lets us combine functions that return values in context.
A brief tour of the heirarchy - MonadError/ApplicativeError

Where a functor has one type hole, MonadError and ApplicativeError are both bifunctors, i.e. they have two type holes. The left type is the  context ( the F[_]), the right the error type. Similarly to Applicative and Monoid, these classes let us lift errors into context, and operate on them in context respectively.
trait ApplicativeError[F[_], E] extends Applicative[F] {
    def raiseError[A](e: E): F[A]

    def handleErrorWith[A](fa: F[A])(f: E => F[A]): F[A]
}


trait MonadError[F[_], E] extends ApplicativeError[F, E] with Monad[F] {

  def ensure[A](fa: F[A])(error: => E)(predicate: A => Boolean): F[A] =
    flatMap(fa)(a => if (predicate(a)) pure(a) else raiseError(error))

  // other definitions follow
}

A brief tour of the heirarchy - MonadError/ApplicativeError ctd.

You can fix the Error type to a platform error type, and handle application and implementation erros together:
import cats._

sealed trait AppError extends Throwable

case class User(name: String, age: Int)
case object BadUserId extends AppError

trait FailableAlgebra[F[_]] {
  def getUser(userId: String): F[User]
}

object FailableAlgebra {
  def default[F[_]](implicit ME: MonadError[F, Throwable]) = new FailableAlgebra[F] {
    def getUser(userId: String): F[User] = if (userId.isEmpty) ME.raiseError(BadUserId) else ME.pure(User("Bob Dobbs", Int.MaxValue))
  }
}

object CallSite {
  def callUser(alg: FailableAlgebra[IO])(userId: String): IO[Unit] = alg.getUser(userId).handleErrorWith {
    case e: AppError => e match {
      case BadUserId => IO(println("bad UserID!"))
    }
    case _ = IO(println("good user ID"))
  }
}


A brief tour of the heirarchy - Traverse/Sequence

Traverse and sequence are related functions that can take two different contexts and “invert” them. The standard library includes these functions on Future (an applicative functor) and List (a foldable structure) and cats generalizes them to other such data types.
trait Traverse[F[_]] extends Functor[F] with Foldable[F] with UnorderedTraverse[F] {
  def traverse[G[_]: Applicative, A, B](fa: F[A])(f: A => G[B]): G[F[B]]
}
Passing identity as the second argument to traverse is equivalent to the function sequence. These are a very useful and prevalent patterns.

Data types in Cats - Validated

Consider Either, the bifunctor with right-bias and ability to fail quickly when we want to handle application errors. Becuase it fails quickly (i.e. is a monad), we get the short-circuit logic in the failure mode:
sealed trait AppError
object BadEmail extends AppError
object MalformedPassword extends AppError

case class Credentials(email: String, password: String)
case class User(username: String, age: String)

def wellFormedEmail(creds: Credentials): Either[AppError, String] = Left(BadEmail)
def passwordIsCorrectLength(creds: Credentials): Either[AppError, String] = Left(MalformedPassword)

def validateCredentials(creds: Credentials): Either[AppError, User]

def login(email: String, password: String) = User(???, ???)

for {
  validEmailCreds <- wellFormedEmail(creds)
  validPassword <- passwordIsCorrectLength(creds)
} yield login(validEmailCreds, validPassword)

// Left(BadEmail)
This is due to the definition of flatMap on the Either datatype in the standard library. Cats provides a data type Validated to accumulate errors.
sealed abstract class Validated[+E, +A] extends Product with Serializable {
  // Implementation elided
}

final case class Valid[+A](a: A) extends Validated[Nothing, A]
final case class Invalid[+E](e: E) extends Validated[E, Nothing]
Validated doesn’t have a monadic instance, but it is an applicative functor.
val validatedEmail = wellFormedEmail(creds)
val validatedPassword = passwordIsCorrectLength(creds)

(validEmailCreds.toValidated.toValidatedNel, validCreds.toValidated.toValidatedNel).map2(login(_, _))
// NonEmptyList[AppError](BadEmail, MalformedPassword)
Data types in Cats - Kleisli

Kleisli “is an abstraction over Fucntion1”. It is a case class encoding a computation of type A => F[B]
final case class Kleisli[F[_], -A, B](run: A => F[B])
Kleisli is useful for providing a context to a computation (you can define Reader in terms of Kleisli), and to simplify talking about composition. It’s a monad if the inner type F is a monad.
Other Monads in Cats


  State
  Writer
  The more general IndexedReaderWriterStateT
  Eval

The “Tagless” pattern

Not a cats-provided utility, but enabled by the cats typeclasses. The zen of tagless is a way to separate the description of an algrbra from its implementation while providing some constraints. Let’s consider the following algebra:
trait FomoService[F[_]] {
  def getFriendsEvents(userId: String, stateAbbrev: String): F[List[Friends]]
}
We’re going to have to hit some sort of backing store to get  this data. Say we reach out to a microservice that handles a user’s friends, and a different one that handles events.
trait FriendsService[F[_]] {
  def lookupFriendsByUserId(userId: String): F[List[String]]
}

trait EventsService[F[_]] {
  def getEvents(userIds: List[String]): F[List[Event]]
}
The “Tagless” pattern - ctd

So now we can talk very generally about our implementation of getFriendsEvents:
object FomoService {
  def default[F[_]](
    friendsService: FriendsService[F],
    eventsService: EventsService[F]
  )(implicit M: Monad[F]): FomoService[F] = new FomoService[F] = {
    def getFriendsEvents(userId: String) = for {
      friends <- friendsService.lookupFriendsByUserId(userId)
      events <- eventsService.getEvents(userId)
    } yield events
  }
}

While our backing services can be concretely defined as well:
object FriendsService[F[_]] {
  def fromClient[F](client: Client[F], config: Config) = new FriendsService {
    def lookupFriendsByUserId(userId: String): F[List[String]] =
      client.fetch(config.friendsServicePath)
  }
}
Having these services be the result of a function instead of a dedicated class constructor means the result can be cached without scaffolding a new class. It also allows for some trivial mocking:
def trivial(friends: List[String]) = new FriendsService[IO] { // use abstract F if you desire
  def lookupFriendsByUserId = IO(friends)
}
By writing the app in an abstract F, you can compose an entire app without committing strictly to an effect type until the very top.