jcazevedo.net

home • about • posts • archive • projects • colophon

Book Review: "Scala with Cats"

October 2, 2023 ∞

Scala with Cats is a book about the Cats library, which provides abstractions for functional programming in the Scala programming language. The book provides an introduction not only to the Cats library but also to some category theory structures. It’s divided in two major sections: “Theory” and “Case Studies”. The “Theory” section starts with a chapter dedicated to the way Cats is designed around type classes and how type classes are encoded in the Scala programming language. The section follows with dedicated chapters for different algebraic data structures, some functional programming constructs and how they are implemented in Cats: Monoids, Semigroups, Functors, Monads, Monad Transformers, Semigroupal, Applicative, Foldable and Traverse. The “Case Studies” section ties it all up with 4 practical applications of the previously introduced structures and constructs: testing asynchronous code, map reduce, data validation and CRDTs.

I worked through the book in March and April this year and found it engaging and with a fast pace. Laws are presented and explained in terms of Scala code. The exercises complement the content of the book well, particularly the ones in the “Case Studies” section, which showcase the applications of everything that was introduced in the “Theory” section.

I would recommend the book to anyone with moderate knowledge of the Scala programming language who wants to learn more about typed functional programming in general and about the Cats library in particular.

If you’re interested in my solutions to the book’s exercises, they are available in the following posts:

March 25, 2023
Solutions to "Scala with Cats": Chapter 1
April 3, 2023
Solutions to "Scala with Cats": Chapter 2
April 3, 2023
Solutions to "Scala with Cats": Chapter 3
April 4, 2023
Solutions to "Scala with Cats": Chapter 4
April 5, 2023
Solutions to "Scala with Cats": Chapter 5
April 5, 2023
Solutions to "Scala with Cats": Chapter 6
April 5, 2023
Solutions to "Scala with Cats": Chapter 7
April 7, 2023
Solutions to "Scala with Cats": Chapter 8
April 7, 2023
Solutions to "Scala with Cats": Chapter 9
April 8, 2023
Solutions to "Scala with Cats": Chapter 10
April 8, 2023
Solutions to "Scala with Cats": Chapter 11

Solutions to "Scala with Cats": Chapter 11

April 8, 2023 ∞

These are my solutions to the exercises of chapter 11 of Scala with Cats.

Table of Contents

Exercise 11.2.3: GCounter Implementation

GCounter can be implemented as follows:

final case class GCounter(counters: Map[String, Int]) {
  def increment(machine: String, amount: Int): GCounter =
    GCounter(counters.updatedWith(machine)(v => Some(v.getOrElse(0) + amount)))

  def merge(that: GCounter): GCounter =
    GCounter(that.counters.foldLeft(counters) { case (acc, (k, v)) =>
      acc.updatedWith(k)(_.map(_ max v).orElse(Some(v)))
    })

  def total: Int =
    counters.values.sum
}

Exercise 11.3.2: BoundedSemiLattice Instances

The following are possible implementations of BoundedSemiLattice for Ints and Sets. As described in the problem statement, we don’t need to model non-negativity in the instance for Ints:

import cats.kernel.CommutativeMonoid

trait BoundedSemiLattice[A] extends CommutativeMonoid[A] {
  def combine(a1: A, a2: A): A
  def empty: A
}

object BoundedSemiLattice {
  implicit val intBoundedSemiLattice: BoundedSemiLattice[Int] =
    new BoundedSemiLattice[Int] {
      def combine(a1: Int, a2: Int): Int = a1 max a2
      def empty: Int = 0
    }

  implicit def setBoundedSemiLattice[A]: BoundedSemiLattice[Set[A]] =
    new BoundedSemiLattice[Set[A]] {
      def combine(a1: Set[A], a2: Set[A]): Set[A] = a1 union a2
      def empty: Set[A] = Set.empty[A]
    }
}

Exercise 11.3.3: Generic GCounter

The following is a possible implementation of a generic GCounter that uses instances of CommutativeMonoid and BoundedSemiLattice:

import cats.kernel.CommutativeMonoid
import cats.syntax.foldable._
import cats.syntax.semigroup._

final case class GCounter[A](counters: Map[String, A]) {
  def increment(machine: String, amount: A)(implicit m: CommutativeMonoid[A]): GCounter[A] =
    GCounter(counters |+| Map(machine -> amount))

  def merge(that: GCounter[A])(implicit b: BoundedSemiLattice[A]): GCounter[A] =
    GCounter(counters |+| that.counters)

  def total(implicit m: CommutativeMonoid[A]): A =
    counters.values.toList.combineAll
}

Exercise 11.4: Abstracting GCounter to a Type Class

The implementation of an instance of the GCounter type class for Map closely resembles the original GCounter implementation:

import cats.kernel.CommutativeMonoid
import cats.syntax.foldable._
import cats.syntax.semigroup._

trait GCounter[F[_, _], K, V] {
  def increment(f: F[K, V])(k: K, v: V)(implicit m: CommutativeMonoid[V]): F[K, V]
  def merge(f1: F[K, V], f2: F[K, V])(implicit b: BoundedSemiLattice[V]): F[K, V]
  def total(f: F[K, V])(implicit m: CommutativeMonoid[V]): V
}

object GCounter {
  implicit def mapInstance[K, V]: GCounter[Map, K, V] =
    new GCounter[Map, K, V] {
      def increment(f: Map[K, V])(k: K, v: V)(implicit m: CommutativeMonoid[V]): Map[K, V] =
        f |+| Map(k -> v)

      def merge(f1: Map[K, V], f2: Map[K, V])(implicit b: BoundedSemiLattice[V]): Map[K, V] =
        f1 |+| f2

      def total(f: Map[K, V])(implicit m: CommutativeMonoid[V]): V =
        f.values.toList.combineAll
    }
}

Exercise 11.5: Abstracting a Key Value Store

The following is a possible implementation of an instance of the KeyValueStore type class for Map:

trait KeyValueStore[F[_, _]] {
  def put[K, V](f: F[K, V])(k: K, v: V): F[K, V]
  def get[K, V](f: F[K, V])(k: K): Option[V]
  def values[K, V](f: F[K, V]): List[V]

  def getOrElse[K, V](f: F[K, V])(k: K, default: V): V =
    get(f)(k).getOrElse(default)
}

object KeyValueStore {
  implicit val mapInstance: KeyValueStore[Map] =
    new KeyValueStore[Map] {
      def put[K, V](f: Map[K, V])(k: K, v: V): Map[K, V] =
        f + (k -> v)

      def get[K, V](f: Map[K, V])(k: K): Option[V] =
        f.get(k)

      def values[K, V](f: Map[K, V]): List[V] =
        f.values.toList
    }
}

Solutions to "Scala with Cats": Chapter 10

April 8, 2023 ∞

These are my solutions to the exercises of chapter 10 of Scala with Cats.

Table of Contents

Exercise 10.3: Basic Combinators

The and method of Check will create a new Check that calls apply on both instances. However, we soon hit the problem of what to do if they both return a Left:

def and(that: Check[E, A]): Check[E, A] =
  new Check[E, A] {
    def apply(value: A): Either[E, A] = {
      val selfCheck = self.apply(value)
      val thatCheck = that.apply(value)
      // How to combine if both fail?

      ???
    }
  }

We need a way to combine values of type E, which hints towards the need for a Semigroup instance for E. We’re assuming that we don’t want to short-circuit but rather accumulate all errors.

For the and implementation, we follow the algebraic data type style that is recommended by the book:

import cats.Semigroup
import cats.syntax.either._
import cats.syntax.semigroup._

sealed trait Check[E, A] {
  import Check._

  def and(that: Check[E, A]): Check[E, A] =
    And(this, that)

  def apply(a: A)(implicit s: Semigroup[E]): Either[E, A] =
    this match {
      case Pure(func) =>
        func(a)

      case And(left, right) =>
        (left(a), right(a)) match {
          case (Left(e1), Left(e2)) => (e1 |+| e2).asLeft
          case (Left(e),  Right(_)) => e.asLeft
          case (Right(_), Left(e))  => e.asLeft
          case (Right(_), Right(_)) => a.asRight
        }
    }
}

object Check {
  final case class And[E, A](left: Check[E, A], right: Check[E, A]) extends Check[E, A]

  final case class Pure[E, A](func: A => Either[E, A]) extends Check[E, A]

  def pure[E, A](f: A => Either[E, A]): Check[E, A] =
    Pure(f)
}

Validated is a more appropriate data type to accumulate errors than Either. We can also rely on the Applicative instance for Validated to avoid the pattern match:

import cats.Semigroup
import cats.data.Validated
import cats.syntax.apply._

sealed trait Check[E, A] {
  import Check._

  def and(that: Check[E, A]): Check[E, A] =
    And(this, that)

  def apply(a: A)(implicit s: Semigroup[E]): Validated[E, A] =
    this match {
      case Pure(func) =>
        func(a)

      case And(left, right) =>
        (left(a), right(a)).mapN((_, _) => a)
    }
}

object Check {
  final case class And[E, A](left: Check[E, A], right: Check[E, A]) extends Check[E, A]

  final case class Pure[E, A](func: A => Validated[E, A]) extends Check[E, A]

  def pure[E, A](f: A => Validated[E, A]): Check[E, A] =
    Pure(f)
}

The or combinator should return a Valid if the left hand side is Valid or if the left hand side is Invalid but the right hand side is Valid. If both are Invalid, it should return an Invalid combining both errors. Due to the latter, we can’t rely on orElse but rather have a slightly more complicated implementation:

import cats.Semigroup
import cats.data.Validated
import cats.syntax.apply._
import cats.syntax.semigroup._

sealed trait Check[E, A] {
  import Check._

  def and(that: Check[E, A]): Check[E, A] =
    And(this, that)

  def or(that: Check[E, A]): Check[E, A] =
    Or(this, that)

  def apply(a: A)(implicit s: Semigroup[E]): Validated[E, A] =
    this match {
      case Pure(func) =>
        func(a)

      case And(left, right) =>
        (left(a), right(a)).mapN((_, _) => a)

      case Or(left, right) =>
        left(a) match {
          case Validated.Valid(a)    => Validated.Valid(a)
          case Validated.Invalid(el) =>
            right(a) match {
              case Validated.Valid(a)    => Validated.Valid(a)
              case Validated.Invalid(er) => Validated.Invalid(el |+| er)
            }
        }
    }
}

object Check {
  final case class And[E, A](left: Check[E, A], right: Check[E, A]) extends Check[E, A]

  final case class Or[E, A](left: Check[E, A], right: Check[E, A]) extends Check[E, A]

  final case class Pure[E, A](func: A => Validated[E, A]) extends Check[E, A]

  def pure[E, A](f: A => Validated[E, A]): Check[E, A] =
    Pure(f)
}

Exercise 10.4.2: Checks

With our previous Check renamed to Predicate, we can implement the new Check with the proposed interface as follows, using an algebraic data type approach as before:

import cats.Semigroup
import cats.data.Validated

sealed trait Check[E, A, B] {
  import Check._

  def apply(a: A)(implicit s: Semigroup[E]): Validated[E, B]

  def map[C](func: B => C): Check[E, A, C] =
    Map[E, A, B, C](this, func)
}

object Check {
  final case class Map[E, A, B, C](check: Check[E, A, B], func: B => C) extends Check[E, A, C] {
    def apply(a: A)(implicit s: Semigroup[E]): Validated[E, C] =
      check(a).map(func)
  }

  final case class Pure[E, A](pred: Predicate[E, A]) extends Check[E, A, A] {
    def apply(a: A)(implicit s: Semigroup[E]): Validated[E, A] =
      pred(a)
  }

  def pure[E, A](pred: Predicate[E, A]): Check[E, A, A] =
    Pure(pred)
}

flatMap is a bit weird to implement because we don’t have a flatMap for Validated. Fortunately, we have flatMap in Either and a withEither method in Validated that allows us to apply a function over an Either that gets converted back to a Validated.

sealed trait Check[E, A, B] {
  // ...

  def flatMap[C](func: B => Check[E, A, C]) =
    FlatMap[E, A, B, C](this, func)

  // ...
}

object Check {
  // ...

  final case class FlatMap[E, A, B, C](check: Check[E, A, B], func: B => Check[E, A, C])
      extends Check[E, A, C] {
    def apply(a: A)(implicit s: Semigroup[E]): Validated[E, C] =
      check(a).withEither(_.flatMap(b => func(b)(a).toEither))
  }

  // ...
}

andThen gets implemented very similarly to flatMap, except that we don’t use the output of the first Check to decide which other Check to use. The next Check is already statically provided to us:

sealed trait Check[E, A, B] {
  // ...

  def andThen[C](that: Check[E, B, C]): Check[E, A, C] =
    AndThen[E, A, B, C](this, that)

  // ...
}

object Check {
  // ...

  final case class AndThen[E, A, B, C](left: Check[E, A, B], right: Check[E, B, C])
      extends Check[E, A, C] {
    def apply(a: A)(implicit s: Semigroup[E]): Validated[E, C] =
      left(a).withEither(_.flatMap(b => right(b).toEither))
  }

  // ...
}

Exercise 10.4.3: Recap

The helper predicates that are introduced in this exercise make use of a lift method on Predicate that we haven’t implemented yet. Its implementation can be something like the following:

object Predicate {
  // ...

  def lift[E, A](e: E, func: A => Boolean): Predicate[E, A] =
    pure(a => if (func(a)) Validated.Valid(a) else Validated.Invalid(e))

  // ...
}

A Check for username can be implemented as follows, making use of the longerThan and alphanumeric predicates.

val usernameCheck = Check.pure(longerThan(3) and alphanumeric)

A Check for the email address can be implemented as follows. We first check that the string contains at least one @, then split the string, check each of the sides and combine them back at the end:

val emailAddressCheck = {
  val checkLeft =
    Check.pure(longerThan(0))

  val checkRight =
    Check.pure(longerThan(3) and contains('.'))

  val checkLeftAndRight =
    Check.pure(Predicate.pure[Errors, (String, String)] { case ((left, right)) =>
      (checkLeft(left), checkRight(right)).mapN((_, _))
    })

  Check
    .pure(containsOnce('@'))
    .map({ str =>
      val Array(left, right) = str.split("@")
      (left, right)
    })
    .andThen(checkLeftAndRight)
    .map({ case ((left, right)) => s"$left@$right" })
}

Exercise 10.5: Kleislis

The run method on Predicate must return a A => Either[E, A]. We must rely on the existing apply method so we also need a Semigroup instance for E:

sealed trait Predicate[E, A] {
  // ...

  def run(implicit s: Semigroup[E]): A => Either[E, A] =
    a => apply(a).toEither

  // ...
}

Our checks don’t change much. We have decided to implement the email address check slightly differently here, applying the checks directly in the split step:

val usernameCheck = checkPred(longerThan(3) and alphanumeric)

val emailAddressCheck = {
  val checkLeft: Check[String, String] =
    checkPred(longerThan(0))

  val checkRight: Check[String, String] =
    checkPred(longerThan(3) and contains('.'))

  val split: Check[String, (String, String)] =
    check(_.split('@') match {
      case Array(name, domain) =>
        Right((name, domain))

      case _ =>
        Left(error("Must contain a single @ character"))
    })

  val join: Check[(String, String), String] =
    check({ case (l, r) => (checkLeft(l), checkRight(r)).mapN(_ + "@" + _) })

  split andThen join
}

Solutions to "Scala with Cats": Chapter 9

April 7, 2023 ∞

These are my solutions to the exercises of chapter 9 of Scala with Cats.

Table of Contents

Exercise 9.2: Implementing foldMap

The signature of foldMap can be as follows. We add Monoid as a context bound for B:

def foldMap[A, B: Monoid](as: Vector[A])(f: A => B): B = ???

To implement the body of foldMap, we have moved the Monoid from a context bound to an implicit parameter list for easier access:

def foldMap[A, B](as: Vector[A])(f: A => B)(implicit monoid: Monoid[B]): B =
  as.map(f).foldLeft(monoid.empty)(monoid.combine)

On the code above, we have done both steps separetely for clarity (the map and the foldLeft), but we could have made the calls to func directly in the combine step of foldLeft.

Exercise 9.3.3: Implementing parallelFoldMap

We can implement parallelFoldMap as follows:

def parallelFoldMap[A, B: Monoid](values: Vector[A])(func: A => B): Future[B] = {
  val batches = Runtime.getRuntime().availableProcessors()
  val groups = (values.length + batches - 1) / batches
  val futures = values.grouped(groups).map(as => Future(foldMap(as)(func)))
  Future.sequence(futures).map(_.foldLeft(Monoid[B].empty)(Monoid[B].combine))
}

We determine the amount of batches in which to split our work based on the number of CPUs we have available. We then determine the size of our groups by dividing the length of our input by the number of batches we’re going to run, rounding up. We spawn a Future with foldMap for each group and join them via Future.sequence, reducing the results of each batch with the Monoid instance we have in scope for B.

Exercise 9.3.4: parallelFoldMap with more Cats

To implement parallelFoldMap using Foldable and Traverse we import the respective instances from cats.instances.vector and the syntax extension methods that allow us to call foldMap and traverse directly on Vector instances:

import cats.instances.vector._
import cats.syntax.foldable._
import cats.syntax.traverse._

def parallelFoldMap[A, B: Monoid](values: Vector[A])(func: A => B): Future[B] = {
  val batches = Runtime.getRuntime().availableProcessors()
  val groups = (values.length + batches - 1) / batches

  values
    .grouped(groups)
    .toVector
    .traverse(group => Future(group.foldMap(func)))
    .map(_.combineAll)
}

Solutions to "Scala with Cats": Chapter 8

April 7, 2023 ∞

These are my solutions to the exercises of chapter 8 of Scala with Cats.

Table of Contents

Exercise 8.1: Abstracting over Type Constructors

To write a trait definition for UptimeClient that abstracts over the return types, we can add a type constructor F[_] as a type parameter:

trait UptimeClient[F[_]] {
  def getUptime(hostname: String): F[Int]
}

We can then extend it with two traits that bind F to Future and Id respectively:

trait RealUptimeClient extends UptimeClient[Future]

trait TestUptimeClient extends UptimeClient[Id]

To make sure that the code compiles, we write out the method signatures for getUptime in each case:

trait RealUptimeClient extends UptimeClient[Future] {
  def getUptime(hostname: String): Future[Int]
}

trait TestUptimeClient extends UptimeClient[Id] {
  def getUptime(hostname: String): Id[Int]
}

We can now have a TestUptimeClient as a full class based on Map[String, Int] with no need for relying on Future:

class TestUptimeClient(hosts: Map[String, Int]) extends UptimeClient[Id] {
  def getUptime(hostname: String): Id[Int] =
    hosts.getOrElse(hostname, 0)
}

Exercise 8.2: Abstracting over Monads

We can rewrite the method signatures of UptimeService so that it abstracts over the context as follows:

class UptimeService[F[_]](client: UptimeClient[F]) {
  def getTotalUptime(hostnames: List[String]): F[Int] =
    ???
}

To get the previous implementation working, we need to not only prove the compiler that F has an Applicative, but also add a few syntax imports so that we can call traverse and map:

import cats.Applicative
import cats.instances.list._
import cats.syntax.functor._
import cats.syntax.traverse._

class UptimeService[F[_]: Applicative](client: UptimeClient[F]) {
  def getTotalUptime(hostnames: List[String]): F[Int] =
     hostnames.traverse(client.getUptime).map(_.sum)
}
atom • email • twitter
The source for this site is available on GitHub