问题 Cats：Monads的非尾递归tailRecM方法


在 猫，使用时创建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 方法 ？

请分享你的想法。


3103
2018-06-12 16:53


起源

答案:

之间的关系 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
}

这显示了如何实现一个 flatMap 从 tailRecM 并暗示建议编译器不会自动执行此类操作。由Monad的用户决定何时使用它是有意义的 tailRecM 过度 flatMap。

这个博客 有很好的scala示例来解释何时 tailRecM 有用的。它遵循 PureScript文章 菲尔·弗里曼最初介绍了这种方法。

它解释了使用的缺点 flatMap 对于 monadic组成：

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（强烈推荐）。


6
2017-07-05 04:50



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

这里 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

对于猫中的任何Monads，tailRecM都不会破坏堆栈（就像它可能是OOM的几乎所有JVM程序一样）。

接着

没有tailRecM（或递归flatMap）是安全的，库就像   iteratee.io无法安全地编写，因为它们需要monadic递归。

和 另一张票 声明客户 cats.Monad 应该知道一些monad没有stacksafe tailRecM 

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


6
2018-06-13 03:09


非常感谢您的回答。我想你已经回答了我的第二个问题。关于第一个的任何想法？ - 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

答案:

之间的关系 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
}

这显示了如何实现一个 flatMap 从 tailRecM 并暗示建议编译器不会自动执行此类操作。由Monad的用户决定何时使用它是有意义的 tailRecM 过度 flatMap。

这个博客 有很好的scala示例来解释何时 tailRecM 有用的。它遵循 PureScript文章 菲尔·弗里曼最初介绍了这种方法。

它解释了使用的缺点 flatMap 对于 monadic组成：

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（强烈推荐）。


6
2017-07-05 04:50



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

这里 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

对于猫中的任何Monads，tailRecM都不会破坏堆栈（就像它可能是OOM的几乎所有JVM程序一样）。

接着

没有tailRecM（或递归flatMap）是安全的，库就像   iteratee.io无法安全地编写，因为它们需要monadic递归。

和 另一张票 声明客户 cats.Monad 应该知道一些monad没有stacksafe tailRecM 

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


6
2018-06-13 03:09


非常感谢您的回答。我想你已经回答了我的第二个问题。关于第一个的任何想法？ - 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

热门问题

不使用eval / new函数的JavaScript模板库 当涉及内部类时，Java继承如何工作 .NET Windows服务的奇怪问题 在.ipa或.app下查找App ID 快速入门XSLT参考[关闭] 如何找出Android应用程序中未使用的资源 Ruby中并发的同步方法[重复] 将std :: chrono :: system_clock :: time_point转换为struct timeval并返回 Google Drive API V3（javascript）更新文件内容 Bootstrap 3.0 - 将元素推到底部 受密码保护的.NET ClickOnce部署？ 如何用postgresql安装wordpress coq Set或Type如何成为命题 硒滚动元素进入（中心）视图 在Spring Transaction JUnit测试中自动装配Hibernate会话的正确方法 Git的Dockerfile策略 如何在FOS_PICKFOLDER中使用IFileDialog，同时仍在对话框中显示文件名 在Firefox扩展中复制Google Chrome浏览器操作弹出效果 CakePHP找到MAX 芹菜 - 完成任务的召唤功能 从使用fmemopen创建的流中读取宽字符 .NET是否为每个程序集创建一个字符串实习池？ DefaultModelBinder不绑定嵌套模型 Navigator.MediaDevices.getUserMedia（）使用了哪些相机通信标准？ 选择命名空间名称时应该知道什么？ cout Swagger Codegen CLI Java客户端 - 如何正确使用它 一个很好的哈希函数用于采访整数，字符串？ Maven 3 ciManagement配置的目的是什么？ 如何通过语言文化获取代码页？
licensed under cc by-sa 3.0 with attribution.
隐私政策 往来