В cats, когда монада создается с использованием признака Monad, должна быть предоставлена реализация метода tailRecM.
У меня есть сценарий ниже, который я обнаружил невозможным для хвостовой рекурсивной реализации 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) Согласно приведенному выше примеру, как этот метод tailRecM можно использовать для оптимизации вызова метода flatMap? Реализация метода flatMap переопределяется/модифицируется tailRecM во время компиляции?
2) Если tailRecM не является хвостовой рекурсией, как указано выше, будет ли он по-прежнему эффективен, чем использование исходного метода flatMap?
Пожалуйста, поделитесь своими мыслями.
