猫：Monads的非尾递归tailRecM方法

Question

在 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方法更有效？

请分享您的想法。

- tharindu_DG

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，来自 cats 的问题单

对于 cats 中的任何一个 Monad 来说，tailRecM 都不会导致栈溢出（尽管像几乎所有 JVM 程序一样，可能会 OOM）。

然后

如果没有安全的 tailRecM（或递归的 flatMap），就无法编写像 iteratee.io 这样的库，因为它们需要单调递归。

还有 另一个问题单 指出，cats.Monad 的客户端应该意识到一些 Monad 没有栈安全的 tailRecM

那些试图获得栈安全性的人仍然可以使用 tailRecM，只要他们明白某些 monad 无法给他们提供栈安全性即可。

- Nazarii Bardiuk

---

非常感谢您的回答。我想您已经回答了我的第二个问题。第一个问题有什么想法吗？ - tharindu_DG

@tharindu_DG 添加了一些关于猫票的链接。 - Nazarii Bardiuk

@NazariiBardiuk 看起来实现是不正确的，它在一个简单的例子上失败了：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

Answer 2

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
}

这篇文章介绍了如何从tailRecM实现flatMap，并暗示编译器不会自动执行此类操作。使用Monad决定何时使用tailRecM而不是flatMap取决于用户。这篇博客提供了很好的Scala示例来解释何时可以使用tailRecM。它遵循Phil Freeman的PureScript文章的内容，该文章最初介绍了这种方法。它解释了使用flatMap进行单调组合的缺点。

以下是使用基于tailRecM的实现：

这保证更加安全的FlatMap类型类，但这意味着每个实例的实现者都需要提供一个安全的tailRecM。

Cats提供的许多方法利用单调组合。因此，即使您没有直接使用它，实现tailRecM也允许与其他monad更有效地组合。在另一篇回答中，@nazarii-bardiuk提供了一个尾递归的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》中被使用（强烈推荐）。

- hjmeijer