猫：Monadsの非テール再帰的tailRecMメソッド

Question

catsでは、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は、対応するブランチが処理されるまで、マージするのを待っているブランチを保持します。 cats ticketなぜtailRecMが猫にモナドのいずれかのために、（ほぼすべてのJVMプログラムのようにそれがOOM場合があります）スタックを爆破しませんtailRecM

を使うから

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（または再帰的flatMap）がなければ、その後

は、 のようなライブラリがiteratee.ioは安全に書き込むことができません。

とanother ticketはcats.Monadのクライアントは、いくつかのモナドが持っていないことを認識すべきであると述べてstacksafe tailRecM

tailRecMはまだ彼ら限りは、スタックの安全性を取得しようとしているもので使用することができます特定のモナドがそれを与えることができないことを理解してください。