scala - 猫: Non tail recursive tailRecM method for Monads

在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方法调用？ flatMap方法的实现是否在编译时被tailRecM覆盖/修改了？

2)如果tailRecM并非如上所述的尾部递归，那么它仍然比使用原始flatMap方法更有效吗？

请分享您的想法。

最佳答案

tailRecM和flatMap之间的关系

为了回答您的第一个问题，以下代码是FlatMapLaws.scala的cats-laws的一部分。它测试flatMap和tailRecM方法之间的一致性。

/**
 * It is possible to implement flatMap from tailRecM and map
 * and it should agree with the flatMap implementation.
 */
def flatMapFromTailRecMConsistency[A, B](fa: F[A], fn: A => F[B]): IsEq[F[B]] = {
  val tailRecMFlatMap = F.tailRecM[Option[A], B](Option.empty[A]) {
    case None => F.map(fa) { a => Left(Some(a)) }
    case Some(a) => F.map(fn(a)) { b => Right(b) }
  }

  F.flatMap(fa)(fn) <-> tailRecMFlatMap
}

这显示了如何从flatMap实现tailRecM，并暗含暗示编译器不会自动执行此操作。由Monad的用户决定何时才应使用tailRecM而不是flatMap。

This blog有很好的scala示例，可以解释tailRecM何时有用。它遵循最初介绍该方法的Phil Freeman的PureScript article。

它解释了使用flatMap进行单声道合成的弊端:



与基于tailRecM的实现相反:



猫中提供的许多方法都利用了单调成分。因此，即使您不直接使用它，实现tailRecM也可以与其他monad进行更有效的合成。

树的放大

在另一个答案中，@ nazarii-bardiuk提供了tailRecM的实现，该实现是尾递归的，但未通过上述的flatMap/tailRecM一致性测试。递归后无法正确重建树结构。下面是一个固定版本:

def tailRecM[A, B](arg: A)(func: A => Tree[Either[A, B]]): Tree[B] = {
  @tailrec
  def loop(toVisit: List[Tree[Either[A, B]]],
           toCollect: List[Option[Tree[B]]]): List[Tree[B]] =
    toVisit match {
      case Branch(l, r) :: next =>
        loop(l :: r :: next, None :: toCollect)

      case Leaf(Left(value)) :: next =>
        loop(func(value) :: next, toCollect)

      case Leaf(Right(value)) :: next =>
        loop(next, Some(pure(value)) :: toCollect)

      case Nil =>
        toCollect.foldLeft(Nil: List[Tree[B]]) { (acc, maybeTree) =>
          maybeTree.map(_ :: acc).getOrElse {
            val left :: right :: tail = acc
            branch(left, right) :: tail
          }
        }
    }

  loop(List(func(arg)), Nil).head
}

(gist with test)

您可能知道，但是您的示例(以及@ nazarii-bardiuk的答案)在Noel Welsh和Dave Gurnell的Scala with Cats书中使用(强烈推荐)。

关于scala - 猫: Non tail recursive tailRecM method for Monads，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/44504790/