貓：Monads的非尾遞歸tailRecM方法

在cats中，當使用Monad特徵創建Monad時，應提供方法tailRecM的實現。貓：Monads的非尾遞歸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方法有效嗎？

請分享您的想法。

來源

2017-06-12 tharindu_DG

有時候有一種方法可以用明確的列表替換一個調用堆棧。

這裏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不會吹堆棧（如幾乎每個JVM程序可能OOM），對任何單子的貓。

然後

沒有tailRecM（或遞歸flatMap）是安全的，像庫iteratee.io不能安全地，因爲它們需要單子遞歸編寫。

和another ticket指出的cats.Monad客戶應該知道，有些單子沒有stacksafe tailRecM

tailRecM仍然可以通過那些試圖讓堆棧安全使用，只要它們瞭解某些單子將無法將其給予它們

來源

2017-06-13 03:09:22

非常感謝您的答覆。我想你已經回答了我的第二個問題。任何關於第一個的想法？ –

@tharindu_DG添加了一些鏈接貓的門票 –

貓：Monads的非尾遞歸tailRecM方法

回答

相關問題