Cats: non-tail recursive tailRecM recursive method for Monads

Question

In cats , when Monad is created using the Monad attribute, an implementation of the tailRecM method must be provided.

I have a script below that I found impossible to provide for a recursive tailRecM tail tailRecM

  sealed trait Tree[+A] final case class Branch[A](left: Tree[A], right: Tree[A]) extends Tree[A] final case class Leaf[A](value: A) extends Tree[A] implicit val treeMonad = new Monad[Tree] { override def pure[A](value: A): Tree[A] = Leaf(value) override def flatMap[A, B](initial: Tree[A])(func: A => Tree[B]): Tree[B] = initial match { case Branch(l, r) => Branch(flatMap(l)(func), flatMap(r)(func)) case Leaf(value) => func(value) } //@tailrec override def tailRecM[A, B](a: A)(func: (A) => Tree[Either[A, B]]): Tree[B] = { func(a) match { case Branch(l, r) => Branch( flatMap(l) { case Right(l) => pure(l) case Left(l) => tailRecM(l)(func) }, flatMap(r){ case Right(r) => pure(r) case Left(r) => tailRecM(r)(func) } ) case Leaf(Left(value)) => tailRecM(value)(func) case Leaf(Right(value)) => Leaf(value) } } } 

1) According to the above example, how can this tailRecM method be used to optimize the call to the flatMap method? Is overriding / changing the flatMap method to tailRecM at compile time?

2) If tailRecM not tail recursive as described above, will it still be more efficient than using the original flatMap method?

Share your thoughts.

Answer 1

Sometimes there is a way to replace the call stack with an explicit list.

Here toVisit keeps track of branches that are waiting to be processed.

And toCollect keeps branches waiting for merging until the corresponding branch is processed.

 override def tailRecM[A, B](a: A)(f: (A) => Tree[Either[A, B]]): Tree[B] = { @tailrec def go(toVisit: List[Tree[Either[A, B]]], toCollect: List[Tree[B]]): List[Tree[B]] = toVisit match { case (tree :: tail) => tree match { case Branch(l, r) => l match { case Branch(_, _) => go(l :: r :: tail, toCollect) case Leaf(Left(a)) => go(f(a) :: r :: tail, toCollect) case Leaf(Right(b)) => go(r :: tail, pure(b) +: toCollect) } case Leaf(Left(a)) => go(f(a) :: tail, toCollect) case Leaf(Right(b)) => go(tail, if (toCollect.isEmpty) pure(b) +: toCollect else Branch(toCollect.head, pure(b)) :: toCollect.tail) } case Nil => toCollect } go(f(a) :: Nil, Nil).head } 

---

From a ticket for cats , why use tailRecM

tailRecM will not delete the stack (for example, almost every JVM program can be OOM), for any of Monads in cats.

and then

Without tailRecM (or the recursive flatMap), being safe, libraries like iteratee.io cannot be written safely, as they require monadic recursion.

and another ticket states that cats.Monad customers should know that some monads do not have tailRecM

tailRecM can still be used by those trying to get stack security, as long as they realize that some monads cannot give them them