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:
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.
importscala.concurrent.ExecutionContext.Implicits.globaldefgetPowerLevel(autobot:String):Response[Int]=powerLevels.get(autobot)match{caseSome(powerLevel)=>EitherT.right(Future.successful(powerLevel))caseNone=>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.
To implement tacticalReport, we need to produce a String from a Future, so
we must use Await.
importscala.concurrent.Awaitimportscala.concurrent.duration._deftacticalReport(ally1:String,ally2:String):String={Await.result(canSpecialMove(ally1,ally2).value,5.seconds)match{caseLeft(msg)=>s"Comms error: $msg"caseRight(true)=>s"$ally1 and $ally2 are ready to roll out!"caseRight(false)=>s"$ally1 and $ally2 need a recharge."}}
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))):
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:
importcats.{Applicative,MonadError}defvalidateAdult[F[_]](age:Int)(implicitme:MonadError[F, Throwable]):F[Int]=if(age>=18)Applicative[F].pure(age)elseme.raiseError(newIllegalArgumentException("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:
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:
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:
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:
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:
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.
Note that the implementation above is not stack-safe, but I didn’t worry to much
about it. We can check that the implementation works as expected by using map
over some Tree instances:
On the above, we won’t be able to call map directly over instances of Branch
or Leaf because we don’t have Functor instances in place for those types. To
make the API more friendly, we can add smart constructors to Tree (i.e.
branch and leaf methods that return instances of type Tree).
Exercise 3.6.1.1: Showing off with Contramap
To implement the contramap method, we can create a Printable instance that
uses the format of the instance it’s called on (note the self reference) and
uses func to transform the value to an appropriate type:
For this exercise, rather than defining instances for the proposed types, I
defined instances for Cats’ Monoid directly. For that purpose, we need to
import cats.Monoid.
For the Boolean type, we can define 4 monoid instances. The first is boolean
or, with combine being equal to the application of the || operator and
empty being false:
The fourth is boolean exclusive nor (the negation of exclusive or), with
combine being equal to the negation of the application of the ^ operator and
empty being true:
To convince ourselves that the monoid laws hold for the proposed monoids, we can
verify them on all instances of Boolean values. Since they’re only 2 (true
and false), it’s easy to check them all:
Set intersection only forms a semigroup for sets, since we can’t define an
identity element for the general case. In theory, the identity element would be
the set including all instances of the type of elements in the set, but in
practice we can’t produce that for a generic type A:
The exercise is clearly hinting us towards using a monoid, but the first step
can be defined in terms of Int only. The description doesn’t tell us what we
should do in case of an empty list, but, since we’re in a chapter about monoids,
I assume we want to return the identity element:
Changing the code above to also work with Option[Int] and making sure there is
no code duplication can be achieved by introducing a dependency on a Monoid
instance:
With the above in place we continue to be able to add Ints, but we’re also now
able to add Option[Int]s, provided we have the appropriate Monoid instances
in place:
To be able to add Order instances without making any modifications to add,
we can define a Monoid instance for Order. In this case, we’re piggybacking
on the Monoid instance for Double, but we could’ve implemented the sums and
the production of the identity element directly: