Cats:Monads的非尾递归tailRecM方法

Question

在cat中,当使用Monadtrait 创建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方法有效吗？

请分享你的想法.

Answer 1

有时候有一种方法可以用显式列表替换调用堆栈.

这里toVisit跟踪等待处理的分支.

并toCollect保留等待合并的分支,直到完成相应的分支处理.

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
}

从猫票为何使用tailRecM

对于猫中的任何Monad,tailRecM都不会打击堆栈(就像它可能是OOM的几乎所有JVM程序一样).

然后

如果没有tailRecM(或递归flatMap)是安全的,那么像iteratee.io这样的库就不能安全地编写,因为它们需要monadic递归.

而另一票规定的客户cats.Monad应该知道,有些单子没有stacksafetailRecM

tailRecM仍然可以被那些试图获得堆栈安全的人使用,只要他们知道某些monad将无法将它们提供给他们

Answer 2

tailRecM和之间的关系flatMap

为了回答第一个问题,以下代码是FlatMapLaws.scala的一部分,来自猫法.它测试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
}

这显示了如何实现flatMapfrom tailRecM并隐式地建议编译器不会自动执行此类操作.它是由单子的用户来决定何时是很有意义的使用tailRecM了flatMap.

这个博客有很好的scala示例来解释什么时候tailRecM有用.它遵循Phil Freeman 的PureScript文章,该文章最初介绍了该方法.

它解释了使用缺点flatMap为一元组成:

Scala的这个特性限制了monadic组合的有用性,其中flatMap可以调用monadic函数f,然后可以调用flatMap等.

与tailRecM基于实现的实现相反:

这保证了FlatMap类型类用户的更高安全性,但这意味着实例的每个实现者都需要提供安全的tailRecM.

猫中提供的许多方法都利用了monadic组合.因此,即使您不直接使用它,实现也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
}

(要点测试)

你可能已经知道了,但你的例子(以及@ nazarii-bardiuk的答案)被用于Noel Welsh和Dave Gurnell的Scala with Cats一书中(强烈推荐).