在 cats 中,当使用
下面有一个场景,我发现无法提供
Monad
特质创建一个 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
方法调用?在编译时,tailRecM
是否重写/修改了flatMap
方法的实现?
2) 如果tailRecM
不像上面那样是尾递归的,它是否仍然比使用原始的flatMap
方法更有效?
请分享您的想法。
Branch(Branch(Leaf(31), Branch(Leaf(11), Leaf(2))), Leaf(12)).tailRecM[Tree, String](_.map(i => Right(i.toString))) shouldBe tree.map(_.toString)
- Ilya Murzinov