• Rewrite introduction to Applicative in terms of product
• Rewrite |@| stuff in terms of CartesianBuilder

Part I

• 2.5.5 or pg 261 - Wouldnt it make more sense to use a Semigroup and NonEmptyList instead of Monoid? Having an empty Order doesnt make much sense.
• Table on p. 50 type variance : if type is invariant, surely the type class variance does not inherit (column 1 in the table should be no/no). Also, example with Option/Some demonstrates this.
• p. 81 Diagram supposed to show many-to-one flatMap is actually many-to-many, contrary to the description.
• Suggestion for section on eval monad. Use call to 'current time' instead of a constant, in order to demonstrate differences between models.
• p. 110 : "We need to have a monoid in scope", however, the example imports applicative instead.
• Writer monad exercise crashes, when sequencing futures (no idea why):
  Welcome to Scala 2.12.3 (Java HotSpot(TM) 64-Bit Server VM, Java 1.8.0_101)

java.lang.NoClassDefFoundError: Could not initialize class $line13.$read$$iw$$iw$$iw$$iw$$iw$$iw$$iw$$iw$
        at scala.runtime.java8.JFunction0$mcI$sp.apply(JFunction0$mcI$sp.java:12)
        at scala.concurrent.Future$.$anonfun$apply$1(Future.scala:653)
        at scala.util.Success.$anonfun$map$1(Try.scala:251)
        at scala.util.Success.map(Try.scala:209)
        at scala.concurrent.Future.$anonfun$map$1(Future.scala:287)
        at scala.concurrent.impl.Promise.liftedTree1$1(Promise.scala:29)
        at scala.concurrent.impl.Promise.$anonfun$transform$1(Promise.scala:29)
        at scala.concurrent.impl.CallbackRunnable.run(Promise.scala:60)
        at scala.concurrent.impl.ExecutionContextImpl$AdaptedForkJoinTask.exec(ExecutionContextImpl.scala:140)
        at java.util.concurrent.ForkJoinTask.doExec(Unknown Source)
        at java.util.concurrent.ForkJoinPool$WorkQueue.runTask(Unknown Source)
        at java.util.concurrent.ForkJoinPool.runWorker(Unknown Source)
        at java.util.concurrent.ForkJoinWorkerThread.run(Unknown Source)
java.lang.NoClassDefFoundError: Could not initialize class $line13.$read$$iw$$iw$$iw$$iw$$iw$$iw$$iw$$iw$
        at scala.runtime.java8.JFunction0$mcI$sp.apply(JFunction0$mcI$sp.java:12)
        at scala.concurrent.Future$.$anonfun$apply$1(Future.scala:653)
        at scala.util.Success.$anonfun$map$1(Try.scala:251)
        at scala.util.Success.map(Try.scala:209)
        at scala.concurrent.Future.$anonfun$map$1(Future.scala:287)
        at scala.concurrent.impl.Promise.liftedTree1$1(Promise.scala:29)
        at scala.concurrent.impl.Promise.$anonfun$transform$1(Promise.scala:29)
        at scala.concurrent.impl.CallbackRunnable.run(Promise.scala:60)
        at scala.concurrent.impl.ExecutionContextImpl$AdaptedForkJoinTask.exec(ExecutionContextImpl.scala:140)
        at java.util.concurrent.ForkJoinTask.doExec(Unknown Source)
        at java.util.concurrent.ForkJoinPool$WorkQueue.runTask(Unknown Source)
        at java.util.concurrent.ForkJoinPool.runWorker(Unknown Source)
        at java.util.concurrent.ForkJoinWorkerThread.run(Unknown Source)
java.util.concurrent.TimeoutException: Futures timed out after [5 seconds]
  at scala.concurrent.impl.Promise$DefaultPromise.ready(Promise.scala:255)
  at scala.concurrent.impl.Promise$DefaultPromise.result(Promise.scala:259)
  at scala.concurrent.Await$.$anonfun$result$1(package.scala:215)
  at scala.concurrent.BlockContext$DefaultBlockContext$.blockOn(BlockContext.scala:53)
  at scala.concurrent.Await$.result(package.scala:142)
  ... 42 elided

• page 120 "we can test that them"
• page 121 "a computation of a result" --> "result of a computation" ?
• page 125 parentheses missing "we can evaluate ( 1 + 2) * 3"
• page 128 "should recusively call itself as long as the result of f returns a Right" but the example implies this should be Left
• page 276 If tailRecM is not tail-recursive, will it still be stack-safe? Explain this.
• Cartesian chapter : needs to be updated for 1.0.0, where builder |@| has been removed. Also pg. 183.
• pg 185 7.2.2.3 "gere's an example"
• pg 186 "OF"

Chapter 6 has it that:

Applicative extends Semigroupal and Functor. It provides a way
of applying functions to parameters within a context. Applicative is
the source of the pure method we introduced in Chapter 4.

That is not quite correct. Applicative extends Apply and not Semigroupal and Functor as stated above. Even though this can be said to be the case indirectly since Apply extends Semigroupal and Functor, but stating it as above could lead to confusions.

It is better to state that Applicative extends Apply and Apply then extends Semigroupal and Functor

Tail-recursive tailRecM implementation from the solution doesn't work as expected, it fails on a simple example:

val tree: Tree[Int] = Branch(Branch(Leaf(31), Branch(Leaf(11), Leaf(2))), Leaf(12))
tree.tailRecM[Tree, String](_.map(i => Right(i.toString))) shouldBe tree.map(_.toString)

Branch(Branch(Leaf(11),Leaf(2)),Leaf(12)) was not equal to Branch(Branch(Leaf(31),Branch(Leaf(11),Leaf(2))),Leaf(12))
ScalaTestFailureLocation: TreeStackSafeTailRecMTest at (specs.scala:329)
Expected :Branch(Branch(Leaf(31),Branch(Leaf(11),Leaf(2))),Leaf(12))
Actual   :Branch(Branch(Leaf(11),Leaf(2)),Leaf(12))

here is the trace of open and closed:

open: List(Branch(Branch(Leaf(Right(31)),Branch(Leaf(Right(11)),Leaf(Right(2)))),Leaf(Right(12))))
closed: List()

open: List(Branch(Leaf(Right(31)),Branch(Leaf(Right(11)),Leaf(Right(2)))), Leaf(Right(12)))
closed: List()

open: List(Branch(Leaf(Right(11)),Leaf(Right(2))), Leaf(Right(12)))
closed: List(Leaf(31))

open: List(Leaf(Right(2)), Leaf(Right(12)))
closed: List(Leaf(11), Leaf(31))

open: List(Leaf(Right(12)))
closed: List(Branch(Leaf(11),Leaf(2)), Leaf(31))

open: List()
closed: List(Branch(Branch(Leaf(11),Leaf(2)),Leaf(12)), Leaf(31))

Hello. I'm using the latest develop branch, and if I try to build the html version I have a missing npm things:

advanced-scala (develop)$ ./go.sh
root@2360fc30a214:/source# sbt
Getting org.scala-sbt sbt 0.13.11 ...
:: retrieving :: org.scala-sbt#boot-app
	confs: [default]
	49 artifacts copied, 0 already retrieved (17330kB/320ms)
Getting Scala 2.10.6 (for sbt)...
:: retrieving :: org.scala-sbt#boot-scala
	confs: [default]
	5 artifacts copied, 0 already retrieved (24494kB/132ms)
[info] Loading project definition from /source/project
[info] Set current project to root (in build file:/source/)
> html
Running "less:main" (less) task
>> FileError: 'bootstrap/less/grid.less' wasn't found. Tried - node_modules/underscore-ebook-template/lib/css/common/bootstrap/less/grid.less,src/css/bootstrap/less/grid.less,node_modules/underscore-ebook-template/lib/css/bootstrap/less/grid.less,node_modules/bootstrap/less/grid.less,bootstrap/less/grid.less in node_modules/underscore-ebook-template/lib/css/common/main.less on line 13, column 1:
>> 12 @import "bootstrap/less/code.less";
>> 13 @import "bootstrap/less/grid.less";
>> 14 @import "bootstrap/less/tables.less";
Warning: Error compiling node_modules/underscore-ebook-template/lib/css/html/main.less Use --force to continue.

Aborted due to warnings.
[success] Total time: 5 s, completed Jan 17, 2017 9:40:59 AM

I only found this out after removing my current node_modules folder and npm install-ing again.

I'm not sure if this is worth a clarification, but I've had a bit of head scratching with this one.

If you create the BoundedSemiLattice[Int] instance in a worksheet outside the BoundedSemiLattice companion object, it'll get picked up as Monoid[Int] by the increment method. The increment method will not work properly. While I really liked this excercise, it can be a bit confusing since it requires a Monoid[Int] with the add behavior for increment and it requires a BoundedSemiLattice[Int] (which happens to be also a Monoid[Int]) with the max behavior for the merge operation.

Chapter 1 introduces the basic patterns we'll be building on:

• algebraic data types and structural recursion;
• sequencing computations (map, flatMap, and fold); and
• type classes

This should look very much like the material in Essential Scala. These should be briefly introduced, with possibly more material on type classes than the others. Essential Scala of course provides more information.

There are two other patterns to cover:

• type aliases, covered in #6; and
• type wrappers (AnyVals)

Following build instruction have got three output formats, and epub (in opposite to others) doesn't contain images.

• Functor example (see below)
• Traverse (see below)

Functor

Not sure if I am correct but your solution 10.3.1 for “This Functor is Totally Valid” I believe is missing an import for the Functor syntax package so that you can call the success constructor with map function

import cats.Functor
// import cats.Functor

import cats.syntax.functor._
//import cats.syntax.functor._

implicit val resultFunctor = new Functor[Result] {
  def map[A, B](result: Result[A])(func: A => B): Result[B] =
    result match {
      case Success(value)          => Success(func(value))
      case Warning(value, message) => Warning(func(value), message)
      case Failure(message)        => Failure(message)
    }
}
// resultFunctor: cats.Functor[Result] = $anon$1@40bb1ee8

Traverse

In the last paragraph of section 4.3.1 “The Monad Type Class” you reference: "sequence requires an instance of cats.Traversable to be in scope" ... I think the trait is cats.Traverse

Associativity is about 3 variables being composed twice where order of binary operation is not important e.g. a*(b*c) = (a*b)*c

Here we see only two variables in the discussion:
Page 98:
“Associativity: flatMapping over two functions f and g is the same as flatMapping over f and then flatMapping over g:

m.flatMap(f).flatMap(g) == m.flatMap(x => f(x).flatMap(g))

Had we used FP syntax Monad[_].flatMap(f) instead (with no m), we would see more explicitly and naturally three identifiers f, g, and h (not sure of final correct wording) operating twice on operator flatMap. Algebraic laws in the math world have no concern for the OO syntax, which is a programming construct, hence I think it's more natural to introduce 3 identifiers f, g, and h here instead of m, f, and g.

Perhaps it would make sense to state this law using the two distinct notations?

An info callout should be enough:

<div class="callout callout-info">
...
</div>

https://twitter.com/philip_schwarz/status/946863214897266691

On the book web page there is mention of Supplemental but it's not at all clear how to access it?

Essential Interpreters covers the construction of interpreters in three styles: classic untyped interpreters, monadic interpreters, and composable interpreters using the free monad. Interpreters are the primal functional programming pattern. To quote Haskell luminary Don Stewart “almost all designs fall into the ‘compiler’ or ‘interpreter’ pattern, using a model of the data and functions on that data”.

Is this supposed to be available to early-access subscribers?

I think that backlinks from solutions should lead each one to its corresponding subsection of exercise, but not to the beginning of whole exercise.

For example: A.3 Printable Library Part 3 backling should lead to Better Syntax subsection instead of 1.1.4 Exercise: Printable Library

I'm working through the book with scala 2.12 and cats 1.0.0-MF (stop me there if this is known to be a bad idea). There seems to be an issue with scala 2.12's use of lambdas (I'm guessing) and cats function Functor instances; following the examples doesn't work.

scala> import cats.instances.function._
import cats.instances.function._

scala> import cats.syntax.functor._
import cats.syntax.functor._

scala> val func1 = (x: Int) => x.toDouble
func1: Int => Double = $$Lambda$1019/1377456236@4eb1943b

scala> val func2 = (y: Double) => y * 2
func2: Double => Double = $$Lambda$1020/1094732450@b267745

scala> func1.map(func2)
<console>:20: error: value map is not a member of Int => Double
       func1.map(func2)
             ^

But if I alias a new type I can get and use the Functor instance.

scala>  type F1[X] = Function1[Int, X]
defined type alias F1

scala> val func3 = Functor[F1].map(func1)(func2)
func3: F1[Double] = scala.Function1$$Lambda$1187/903151311@4d4ae76

scala> func3(1)
res14: Double = 2.0

scala> func2(func1(1))
res15: Double = 2.0

Typographical Conventions

Problem with link example:

CDRTs (GCounter and other simple types) make a good monoid case study.

See https://gist.github.com/noelwelsh/8c85f6283e06ecad971d342cda7f77fa for example code.

Mention:

• this is where flatMap comes from;
• this is why we write import cats.syntax.flatMap._
• an example of FlatMap that isn't a Monad (if such a thing exists).

either remove the subsection, which is empty, or introduce a description of the missing exercise.

4.1 What is a Monad?

Every monad is also a functor (see below for proof), so we can rely on
both flatMap and map to sequence computations that do and and don’t
introduce a new monad. Plus, if we have both flatMap and map we can
use for comprehensions to clarify the sequencing behaviour:

A simplifying change to tailrecM was made last December and it fails to compile. Formal parameter to tailrecM has been arg but it has been referred to as a, which does not match. Using both a as below (or both arg) fixes the issue. This compilation break prevents from creating pdf file using sbt all.

import cats.Monad

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

  def flatMap[A, B](tree: Tree[A])
      (func: A => Tree[B]): Tree[B] =
    tree match {
      case Branch(l, r) =>
        Branch(flatMap(l)(func), flatMap(r)(func))
      case Leaf(value)  =>
        func(value)
    }

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

Some less experienced readers who have never seen a for comprehension de-sugared will block at this first comment touching on the topic:

“Plus, if we have both flatMap and map we can use for comprehensions to clarify the sequencing behaviour:”

You de-sugar a few pages later on in context of Futures. I'd argue the de-sugaring should be shown at the very first opportunity such as this intro sentence that links flatMap and map with the Scala for comprehension.

“Equivalently we could say that B is a subtype of A if there exists a function A => B.”

I don't buy that one and it makes me confused. Say B is a car and A is a vehicle, B is subtype of A but I don't know of functions from vehicles to cars, in particular from a AB-320 or BA-747 to a car. Also the existence of a function between A and B is not relevant to A and B being subtypes of each other but that function is only relevant in the context of relationship of types F[A] and F[B].

What follows in the same section 3.6 reads fine to me but not that specific sentence.

See also Cats' contravariant.md for a discussion (which also is unclear with A <: B meaning A subtype of B or A having fewer instances than B and yet the code above it has B extending A): Subtyping relationships are "lifted backwards" by contravariant functors, such that if F is a lawful contravariant functor and A <: B then F[B] <: F[A], which is expressed by Contravariant.narrow.

Sam Halliday explains better contravariant, covariant, and invariant in FP for mortals, showing that covariant and contravariant extend invariant (see https://leanpub.com/fpmortals/read#leanpub-auto-variance and the nice picture with trait hierarchy where a lower node extends a node depicted higher); he also explains that a 'covariant functor' is just a regular functor as per common usage.

This chapter does make clear that we could use the term "Functor" for 3 type classes, but much much too late (explain this much sooner to avoid confusing the reader): contravariant, covariant, and invariant with covariant being the classical common usage people know (applicative and monad) and that effectively "functor" is sometimes taken to mean "covariant" but at other times the collection of the 3 type classes.

B.3 Adding All The Things

import cats.Monoid
import cats.syntax.semigroup._

val qwe = def add (items: List[Int] ): Int =
items.foldLeft (Monoid[Int].empty) (_ |+| _)

will not compile without

import cats.instances.int._

1.3.1 Equality, Liberty, and Fraternity

The interface syntax, defined in [cats.syntax.equal][cats.syntax.equal],
provides two methods for performing type-safe equality checks pro-
vided there is an instance Eq[A] in scope:

Submitted by a reader:

I’m reading the pre-release edition (which is great) and your emails are mentioned there in case the readers spot a mistake.
On chapter 3.1 (Examples of Functors), there’s an example about option that says:

We expect map on Option to behave in the same way as List:

 Option(123).map(_ * 4).map(_ + 4)
// res4: Option[Int] = Some(496)

Option(123).map(x => (x * 2) + 4)
// res5: Option[Int] = Some(250)

The first example should actually be Option(123).map(_ * 2).map(_ + 4) so that:
a. It would be consistent with the list example which is just above it
b. it would match the second example and show that fa.map(g(f(_))) == fa.map(f).map(g)

For this ticket, just add the headings and anchors:

• Concept of Foldable
• Foldable in Cats
• Foldable instances
• Foldable methods requiring no other type class instances:
  • find, exists, forall, toList, isEmpty, nonEmpty
• Foldable methods requiring a Monoid or Semigroup:
  • combineAll/fold, foldLeft/reduceLeftToOption, foldMap
• Definition of Eval
  • Evaluation strategies (Erik Osheim talk)
  • Examples of different evaluation strategies
  • Trampolining
• Foldable methods requiring an Eval:
  • foldRight, reduceRightToOption
  • Examples of folding with different evaluation strategies

Bug spot from @micahkim23 on Gitter:

In the Advanced Scala Cats book, the solution 12.4.4 Safer Folding Using Eval, the example at the end is wrong

foldRight((1 to 100000).toList, 0)(_ + _)
// res22: Int = 705082704

Summing up 1 to 100000 should equal 100000* 100001/2, should probably use a Long here

In section 6.2, The Apply syntax is introduced before Apply typeclass.

It felt a little bit disorientating to read about an apply syntax just after reading about Semigroupal. Without specifically pointing out that this comes from the yet to be discussed typeclass. What makes it even more confusing is that, as you would agree, apply is easily ambiguous in Scala. So what not initially sure if the apply in apply syntax refers to some syntax that builds upon Scala native apply features.

Would suggest that the normal flow of discussing the typeclass and then the syntax they introduced be kept here as it helps with the pedagogy.

When trying out the example in 3.7.2 Invariant in Cats:

import cats.Monoid
import cats.instances.string._ // for Monoid
import cats.syntax.invariant._ // for imap
import cats.syntax.semigroup._ // for |+|

implicit val symbolMonoid: Monoid[Symbol] =
  Monoid[String].imap(Symbol.apply)(_.name)

I get:

<console>:22: error: value imap is not a member of cats.kernel.Monoid[String]
       Monoid[String].imap(Symbol.apply)(_.name)

Adding the following import:

import cats.instances.monoid._

Seems to fix it.

There seems to be a problem with the way the epub version of the book is prepared. I have tried it with both Calibre and Mac OS X's built-in ebook reader, and they give the same strange results (but work fine when I try them with other epubs I own).

It’s as though Calibre thinks the pages are wider than they are, so as you turn the pages, the margin moves to the left, splitting the page in half. Here is a screenshot of page 3:

Notice that part of the next page is showing on the right. And when I advance the page I get this:

Notice that the page number in the upper left now says 3.9 / 351 instead of 4 / 351. And when I advance the page again:

4.7 now instead of 5. Next comes 5.6, then 6.4, 7.3, 8.1, and finally it gets lapped at 9.0. It seems to be advancing about 0.85 pages at a time.

As far as I can tell there is no way to convince these epub readers to view the pages correctly, so as it stands the epub format is unusable. (Feel free to correct me if there is a way!)

Noel had this to say about the problem: "Without looking into it further, which I don't have time to do right now, I don't have any ideas why this is happening. If the HTML output is also messed up, that could be the cause. Otherwise it might be ePub specific, and I don't recall how the ePub build works off the top of my head."

I checked the HTML version; it seems fine, so this is indeed epub-specific.

invariant.md
3.6 CONTRAVARIANTANDINVARIANTFUNCTORS (Page 69)
"Rather than writing out the complete definition from scratch (new Printable[Box] etc...), create your instance using the contramap method of one of the instances above."

Might be more clear to say something like:
"Rather than writing out the complete definition from scratch (new Printable[Box] etc...), create your instance [,in a generic way,] using the contramap method [that will work for any instance]."

In the orange callout section in section 3.6.2.1 you have the following:

Subtyping can be viewed as a conversion. If B is a subtype of A, we can
always convert a B to an A.

Equivalently we could say that B is a subtype of A if there exists a function A => B.

Those two statement sounds contradictory. First one says B is a Subtype of A if we can convert a B to an A, so It would be expected the function signature in the second line to be B => A. Instead of B => A.

This is a typo that affects comprehensibility, as it became really difficult to understand exactly the point being made due to this typo.

3.7.1.1 Invariant in Cats

Also in 3.7.1 Contravariant in Cats

page 165

• readName will take a Map[String, String] parameter, extract the "name" field, check the relevant validation rules, and return an Either[List[String, String]];
• readAge will take a Map[String, String] parameter, extract the "age" field, check the relevant validation rules, and return an Either[List[String, Int].

return types brackets need rebalancing. First line has a misplaced closing bracket, second line is missing one.

first should be Either[List[String], String], second should be Either[List[String], Int]

Parallel is a type class that maps monads to equivalent applicatives. For example, there is an instance of Parallel to map between instances of Either and Validated.

There seem to be three key bits of syntax related to Parallel: parMapN, parSequence, and parTraverse. These combine instances of the monad by converting them to the equivalent applicative and back again:

import cats.instances.list._ // for Monoid
import cats.instances.parallel._ // for Parallel
import cats.syntax.parallel._

val either1: Either[List[String], Int] = Left(List("error1"))
val either2: Either[List[String], Int] = Left(List("error2"))
val either3: Either[List[String], Int] = Left(List("error3"))

(either1, either2, either3).parMapN(_ + _ + _)
// Left(List("error1", "error2", "error3"))

  implicit val catPrintable: Printable[Cat] =
    (cat: Cat) => {
      import PrintableInstances._
      import PrintableSyntax._
      val name  = cat.name.format // compiler error on String
      val age   = cat.age.format // works fine on Int
      val color = cat.color.format // compiler error on String
      s"$name is a $age year-old $color cat"
    }

I suggest to rename format to fmt to avoid the conflict.

"Next define a method parseInt that consumes an Int and parses it as a String."

This should be "consumes a String and parses it as an Int"

https://github.com/underscoreio/scala-with-cats/blob/develop/src/pages/type-classes/implicits.md

Should the None case write null?

Under the section "Controlling Instance Selections", it recaps 3 cases for addition of variance annotations:

A type with an unannotated parameter Foo[A] is invariant in A .
This means there is no rela onship between Foo[B] and Foo[C]
no ma er what the sub- or super-type rela onship is between B
and C .
• A type with a parameter Foo[+A] is covariant in A .
If C is a subtype of B , Foo[C] is a subtype of Foo[B] .
• A type with a parameter Foo[-A] is contravariant in A .
If C is a supertype of B , Foo[C] is a subtype of Foo[B] .

Should the last statement be

If C is a supertype of B , Foo[C] is a supertype of Foo[B] .

I saw the discussion in #80 but I think it needs a separate issue ticket.

I find the whole tailRecM topic in the Monads chapter very confusing and misleading. So misleading that I misunderstood its real purpose and even had to rewrite this post from scratch.

First of all, it is unclear what tailRecM is used for and how it saves a developer from StackOverflowError.
Although it is mentioned that tailRecM is needed for stack-safe nested calls to flatMap, e.g. for folding over large lists, there's no further explanation in section 7.1.

Actually tailRecM is used for monadic operations such as foldM and whileM, which are not covered in the book. Probably it's no use to implement tailRecM in section 4.10, especially in such a tricky (and buggy) way. We don't even show what problem it solves. Why confuse readers?

Maybe we'd better keep it unimplemented here and return back to this function in section 7.1?
There we may introduce the monadic fold and add an exercise to implement tailRecM for some monad, e.g. Tree from section 4.10.

The example below may be used as an explanation of foldM and tailRecM:

// let's create 3 optional values
val op1 = Some(1)
val op2 = Some(2)
val op3 = Some(3)

// we can sum them up using for-comprehension
val res1 =
  for {
    i <- op1
    j <- op2
    k <- op3
  } yield i + j + k
// res1: Option[Int] = Some(6)

// which is equivalent to nested flatMaps
val res2 =
  op1.flatMap(i =>
    op2.flatMap(j =>
      op3.map(k => i + j + k)
    )
  )
// res2: Option[Int] = Some(6)

// but if we have an arbitrary list of options, we cannot write an explicit for
def listOfOptions(n: Int): List[Option[Int]] =
  (1 to n).map(Option(_)).toList

// and that's where we need `foldM` function, which uses `tailRecM` under the hood
val res3 = listOfOptions(3).foldM(0)((s, o) => o.map(s + _))
// res3: Option[Int] = Some(6)

// and it is stack-safe for (almost?) all monads in Cats including Option
val res4 = listOfOptions(10000).foldM(0)((s, o) => o.map(s + _))
// res4: Option[Int] = Some(50005000)

Secondly, I found a flaw in the stack-safe tailRecM version for Tree added to section 4.10 by @davegurnell. I know this solution was proposed by @nbardiuk on StackOverflow, so I invite Nazarii to join the discussion.

The implementation uses lists to store tree elements, but it loses the original tree structure, so the resulting tree is always left-skewed. A correct implementation must give the same result of folding trees as for-comprehension does. The naive tailRecM implementation works correctly, but it is not tail recursive. We either need to fix the tricky implementation and put it in the Foldable chapter as an exercise solution or choose another (simpler) monad for the exercise.

Example implementations of tailRecM in Cats (using mutable builders) make me think it's a much harder problem.

• Introduce Traverse
• Introduce traverse and sequence

Every monad is also a functor (see below for proof), so we can rely on both flatMap and map to sequence computations that do and don't introduce a new monad.

Seeing the proof as exercise on page 99, 4 pages later, is too difficult to follow, state explicitly that this is the subject of section/exercise 4.1.2 using a hyperlink.

I also have no idea what the second part of the sentence is trying to convey (computations that do what?). This sentence needs to be removed or reworked.

2.6.1 Type Class Variance