jcazevedo.net

home • about • posts • projects • colophon

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

Solutions to Scala with Cats: Chapter 7

April 5, 2023 ∞

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

Table of Contents

Exercise 7.1.2: Reflecting on Folds

If we use foldLeft with an empty list as the accumulator and :: as the binary operator we get back the reversed list:

val list = List(1, 2, 3, 4)
list.foldLeft(List.empty[Int])((acc, e) => e :: acc)
// Returns List(4, 3, 2, 1).

On the other hand, if we use foldRight with an empty list as the accumulator and :: as the binary operator we get back the same list:

val list = List(1, 2, 3, 4)
list.foldRight(List.empty[Int])(_ :: _)
// Returns List(1, 2, 3, 4).

Exercise 7.1.3: Scaf-fold-ing Other Methods

The following are implementations of the map, flatMap, filter and sum methods for Lists in terms of foldRight:

def map[A, B](list: List[A])(f: A => B): List[B] =
  list.foldRight(List.empty[B])((a, bs) => f(a) :: bs)

def flatMap[A, B](list: List[A])(f: A => List[B]): List[B] =
  list.foldRight(List.empty[B])((a, bs) => f(a) ++ bs)

def filter[A](list: List[A])(f: A => Boolean): List[A] =
  list.foldRight(List.empty[A])((a, as) => if (f(a)) a :: as else as)

def sum[A](list: List[A])(implicit numeric: Numeric[A]): A =
  list.foldRight(numeric.zero)(numeric.plus)

The sum method makes use of the Numeric type class from the Scala standard library. In the spirit of this book, we could also have created an implementation that uses the Monoid type class instead.

Exercise 7.2.2.1: Traversing with Vectors

The result of the provided expression is going to be a Vector of Lists, with each being the pairwise combination of the elements from both Vectors:

Vector(
  List(1, 3),
  List(1, 4),
  List(2, 3),
  List(2, 4)
)

If we use a list of three parameters, we will get back a Vector of Lists again, but this time each list is going to be of three elements and we will have one list per each possible triple combination of elements from each of the Vectors:

Vector(
  List(1, 3, 5),
  List(1, 3, 6),
  List(1, 4, 5),
  List(1, 4, 6),
  List(2, 3, 5),
  List(2, 3, 6),
  List(2, 4, 5),
  List(2, 4, 6)
)

Exercise 7.2.2.2: Traversing with Options

The return type of the process method is Option[List[Int]] and it will return a Some of the provided input if all integers in the list argument are even and None otherwise. Therefore, it will produce the following for the first call:

Some(List(2, 4, 6))

And the following for the second call:

None

Exercise 7.2.2.3: Traversing with Validated

The provided method will return a Valid with the list argument when all integers of it are even or an Invalid with a List of String for each element that is not even otherwise. Therefore, we get the following for the first call:

Valid(List(2, 4, 6))

And the following for the second call:

Invalid(List("1 is not even", "3 is not even"))

Solutions to Scala with Cats: Chapter 6

April 5, 2023 ∞

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

Table of Contents

Exercise 6.3.1.1: The Product of Lists

The reason product for List produces the Cartesian product is because List forms a Monad, and product is implemented in terms of flatMap. So Semigroupal[List].product(List(1, 2), List(3, 4)) is the same as:

for {
  a <- List(1, 2)
  b <- List(3, 4)
} yield (a, b)

Which results in the Cartesian product.

Exercise 6.4.0.1: Parallel List

List does have a Parallel instance. It zips the lists instead of doing the Cartesian product. This can be exhibited by the following snippet:

import cats.instances.list._
import cats.syntax.parallel._

(List(1, 2), List(3, 4)).parTupled
// Returns List((1, 3), (2, 4)).

(List(1, 2), List(3, 4, 5)).parTupled
// Returns List((1, 3), (2, 4)).

Solutions to Scala with Cats: Chapter 5

April 5, 2023 ∞

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

Table of Contents

Exercise 5.4: Transform and Roll Out

We can rewrite Response using a monad transformer as follows:

import cats.data.EitherT
import scala.concurrent.Future

type Response[A] = EitherT[Future, String, A]

We can implement getPowerLevel as follows. Note that we need an implicit ExecutionContext in scope so that we can have an instance of Functor for Future, even if we just create our Futures with Future.successful (which doesn’t need one). We are using the global ExecutionContext for convenience.

import scala.concurrent.ExecutionContext.Implicits.global

def getPowerLevel(autobot: String): Response[Int] =
  powerLevels.get(autobot) match {
    case Some(powerLevel) => EitherT.right(Future.successful(powerLevel))
    case None => EitherT.left(Future.successful(s"Autobot $autobot is unreachable"))
  }

To implement canSpecialMove we can request the power levels of each autobot and check if their sum is greater than 15. We can use flatMap on EitherT which makes sure that errors being raised on calls to getPowerLevel stop the sequencing and have canSpecialMove return a Response with the appropriate error message.

def canSpecialMove(ally1: String, ally2: String): Response[Boolean] =
  for {
    powerLevel1 <- getPowerLevel(ally1)
    powerLevel2 <- getPowerLevel(ally2)
  } yield (powerLevel1 + powerLevel2) > 15

To implement tacticalReport, we need to produce a String from a Future, so we must use Await.

import scala.concurrent.Await
import scala.concurrent.duration._

def tacticalReport(ally1: String, ally2: String): String = {
  Await.result(canSpecialMove(ally1, ally2).value, 5.seconds) match {
    case Left(msg) =>
      s"Comms error: $msg"
    case Right(true) =>
      s"$ally1 and $ally2 are ready to roll out!"
    case Right(false) =>
      s"$ally1 and $ally2 need a recharge."
  }
}

Solutions to Scala with Cats: Chapter 4

April 4, 2023 ∞

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

Table of Contents

Exercise 4.1.2: Getting Func-y

We have pure and flatMap to define map. We want to start from an F[A] and get to an F[B] from a function A => B. As such, we want to call flatMap over the value. We can’t use func directly, though. However, we can produce a function that would lift our value to an F using pure (a => pure(func(a))):

trait Monad[F[_]] {
  def pure[A](a: A): F[A]

  def flatMap[A, B](value: F[A])(func: A => F[B]): F[B]

  def map[A, B](value: F[A])(func: A => B): F[B] =
    flatMap(value)(func.andThen(pure))
}

Exercise 4.3.1: Monadic Secret Identities

pure, map and flatMap for Id can be implemented as follows:

def pure[A](a: A): Id[A] =
  a

def flatMap[A, B](value: Id[A])(func: A => Id[B]): Id[B] =
  func(value)

def map[A, B](value: Id[A])(func: A => B): Id[B] =
  func(value)

Since Id[A] is just a type alias for A, we can notice that we avoid all boxing in the implementations and, due to that fact, flatMap and map are identical.

Exercise 4.4.5: What is Best?

The answer depends on what we are looking for in specific instances, but some things that the previous examples for error handling don’t cover are:

  • We can’t accumulate errors. The proposed examples all fail fast.
  • We can’t tell exactly where the error was raised.
  • It’s not easy to do error recovery.

Exercise 4.5.4: Abstracting

A possible implementation for validateAdult is the following:

import cats.{Applicative, MonadError}

def validateAdult[F[_]](age: Int)(implicit me: MonadError[F, Throwable]): F[Int] =
  if (age >= 18) Applicative[F].pure(age)
  else me.raiseError(new IllegalArgumentException("Age must be greater than or equal to 18"))
}

If age is greater than or equal to 18, we summon an Applicative for F (which we must have in scope due to MonadError) and lift the age to F. If age is less than 18, we use the MonadError instance we have in scope to lift an IllegalArgumentException to F.

Exercise 4.6.5: Safer Folding using Eval

One way to make the naive implementation of foldRight stack safe using Eval is the following:

import cats.Eval

def foldRightEval[A, B](as: List[A], acc: B)(fn: (A, B) => B): B = {
  def aux(as: List[A], acc: B): Eval[B] =
    as match {
      case head :: tail =>
        Eval.defer(aux(tail, acc)).map(fn(head, _))
      case Nil =>
        Eval.now(acc)
    }

  aux(as, acc).value
}

We defer the call to the recursive step and then map over it to apply fn, all within the context of Eval.

Exercise 4.7.3: Show Your Working

A possible rewrite of factorial so that it captures the log messages in a Writer is the following:

import cats.data.Writer

def factorial(n: Int): Writer[Vector[String], Int] = {
  slowly {
    if (n == 0)
      Writer.apply(Vector("fact 0 1"), 1)
    else
      factorial(n - 1).mapBoth { (log, res) =>
        val ans = res * n
        (log :+ s"fact $n $ans", ans)
      }
  }
}

We can show that this allows us to reliably separate the logs for concurrent computations because we have the logs for each instance captured in each Writer instance:

Await.result(Future.sequence(Vector(
  Future(factorial(5)),
  Future(factorial(5))
)).map(_.map(_.written)), 5.seconds)
// Returns Vector(
//   Vector("fact 0 1", "fact 1 1", "fact 2 2", "fact 3 6", "fact 4 24", "fact 5 120"),
//   Vector("fact 0 1", "fact 1 1", "fact 2 2", "fact 3 6", "fact 4 24", "fact 5 120")
// )

Exercise 4.8.3: Hacking on Readers

To create a type alias for a Reader that consumes a Db we want to fix the first type parameter of Reader to Db, while still leaving the result type as a type parameter:

import cats.data.Reader

type DbReader[A] = Reader[Db, A]

The findUsername and checkPassword functions can be implemented as follows:

def findUsername(userId: Int): DbReader[Option[String]] =
  Reader.apply(db => db.usernames.get(userId))

def checkPassword(username: String, password: String): DbReader[Boolean] =
  Reader.apply(db => db.passwords.get(username).contains(password))

The checkLogin method can be implemented as follows:

def checkLogin(userId: Int, password: String): DbReader[Boolean] =
  for {
    usernameOpt <- findUsername(userId)
    validLogin <- usernameOpt.map(checkPassword(_, password)).getOrElse(Reader.apply((_: Db) => false))
  } yield validLogin

We are making use of the findUsername and checkPassword methods. There are two scenarios in which checkLogin can return a false for a given Db: when the username doesn’t exist and when the password doesn’t match.

Exercise 4.9.3: Post-Order Calculator

A possible implementation of evalOne with no proper error handling is the following:

def evalOne(sym: String): CalcState[Int] = {
  def op(f: (Int, Int) => Int): CalcState[Int] = State {
    case y :: x :: rest =>
      val ans = f(x, y)
      (ans :: rest, ans)
    case _ =>
      throw new IllegalArgumentException("Insufficient stack size")
  }

  def num(value: String): CalcState[Int] = State { s =>
    val ans = value.toInt
    (ans :: s, ans)
  }

  sym match {
    case "+"   => op(_ + _)
    case "*"   => op(_ * _)
    case "-"   => op(_ - _)
    case "/"   => op(_ / _)
    case other => num(other)
  }
}

We’re not told which operands to support, so I assumed at least +, *, - and /.

For the evalAll implementation, we’re not told what to do in case the input is empty. I assumed it would be OK to just have an exception thrown (since that was the case before), and relied on reduce over the evalOne calls:

def evalAll(input: List[String]): CalcState[Int] =
  input.map(evalOne).reduce((e1, e2) => e1.flatMap(_ => e2))

The evalInput method can rely on a call to evalAll after splitting the input by whitespaces:

def evalInput(input: String): Int =
  evalAll(input.split("\\s+").toList).runA(Nil).value

Exercise 4.10.1: Branching out Further with Monads

One implementation of Monad for Tree is the following:

implicit val treeMonad: Monad[Tree] = new Monad[Tree] {
  def pure[A](a: A): Tree[A] =
    Leaf(a)

  def flatMap[A, B](fa: Tree[A])(f: A => Tree[B]): Tree[B] =
    fa match {
      case Branch(left, right) =>
        Branch(flatMap(left)(f), flatMap(right)(f))

      case Leaf(value) =>
        f(value)
    }

  def tailRecM[A, B](a: A)(f: A => Tree[Either[A, B]]): Tree[B] =
    flatMap(f(a)) {
      case Left(value) =>
        tailRecM(value)(f)

      case Right(value) =>
        Leaf(value)
    }
}

However, tailRecM isn’t tail-recursive. We can make it tail-recursive by making the recursion explicit in the heap. In this case, we’re using two mutable stacks: one of open nodes to visit and one of already visited nodes. On that stack, we use None to signal a non-leaf node and a Some to signal a leaf node.

implicit val treeMonad: Monad[Tree] = new Monad[Tree] {
  def pure[A](a: A): Tree[A] =
    Leaf(a)

  def flatMap[A, B](fa: Tree[A])(f: A => Tree[B]): Tree[B] =
    fa match {
      case Branch(left, right) =>
        Branch(flatMap(left)(f), flatMap(right)(f))

      case Leaf(value) =>
        f(value)
    }

  def tailRecM[A, B](a: A)(f: A => Tree[Either[A, B]]): Tree[B] = {
    import scala.collection.mutable

    val open = mutable.Stack.empty[Tree[Either[A, B]]]
    val closed = mutable.Stack.empty[Option[Tree[B]]]

    open.push(f(a))

    while (open.nonEmpty) {
      open.pop() match {
        case Branch(l, r) =>
          open.push(r)
          open.push(l)
          closed.push(None)

        case Leaf(Left(value)) =>
          open.push(f(value))

        case Leaf(Right(value)) =>
          closed.push(Some(pure(value)))
      }
    }

    val ans = mutable.Stack.empty[Tree[B]]

    while (closed.nonEmpty) {
      closed.pop() match {
        case None    => ans.push(Tree.branch(ans.pop(), ans.pop()))
        case Some(v) => ans.push(v)
      }
    }

    ans.pop()
  }
}
atom • email • twitter
The source for this site is available on GitHub