बिल्लियों: मोनाड्स के लिए गैर पूंछ रिकर्सिव 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 ऐसी शाखाएं रखता है जो संबंधित शाखा समाप्त होने तक विलय होने की प्रतीक्षा कर रहे हैं।

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 सकता है) उड़ा नहीं होगा monads से किसी के लिए।

और फिर

tailRecM (या पुनरावर्ती flatMap) के बिना

सुरक्षित किया जा रहा है, तरह पुस्तकालयों iteratee.io सुरक्षित रूप से लिखा नहीं किया जा सकता क्योंकि वे monadic प्रत्यावर्तन की आवश्यकता है।

और another ticket कहा गया है कि cats.Monad के ग्राहकों पता है कि कुछ monads नहीं है होना चाहिए stacksafe tailRecM

tailRecM फिर भी वे के रूप में, उन है कि ढेर सुरक्षा प्राप्त करने के लिए कोशिश कर रहे हैं के द्वारा प्रयोग किया जा सकता है ताकि लंबे समय तक समझें कि कुछ monads उन्हें