猫：Monad 的非尾递归 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方法调用？ flatMap 方法的实现是否在编译时由 tailRecM overridden/modified？

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
}

从cats ticket为什么要用tailRecM

tailRecM won't blow the stack (like almost every JVM program it may OOM), for any of the Monads in cats.

然后

Without tailRecM (or recursive flatMap) being safe, libraries like iteratee.io can't safely be written since they require monadic recursion.

和 another ticket 声明 cats.Monad 的客户应该知道一些 monad 没有堆栈安全 tailRecM

tailRecM can still be used by those that are trying to get stack safety, so long as they understand that certain monads will not be able to give it to them

Answer 2

`tailRecM` 和 `flatMap`

之间的关系

回答你第一个问题，以下代码是FlatMapLaws.scala, from 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。

This blog has nice scala examples to explain when tailRecM comes in useful. It follows the PureScript article 作者 Phil Freeman，最初介绍了该方法。

它解释了将 flatMap 用于 单子组合的缺点:

This characteristic of Scala limits the usefulness of monadic composition where flatMap can call monadic function f, which then can call flatMap etc..

与基于 tailRecM 的实现相比：

This guarantees greater safety on the user of FlatMap typeclass, but it would mean that each the implementers of the instances would need to provide a safe 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 一书中使用（强烈推荐）。

猫：Monad 的非尾递归 tailRecM 方法

Cats: Non tail recursive tailRecM method for Monads

recursion

functional-programming

scala

scala-cats

`tailRecM` 和 `flatMap`

树的实现

猫：Monad 的非尾递归 tailRecM 方法

Cats: Non tail recursive tailRecM method for Monads

recursion

functional-programming

scala

scala-cats

tailRecM 和 flatMap

树的实现

`tailRecM` 和 `flatMap`