स्कैला

Question

में एक बाइनरी पेड़ पर पूंछ रिकर्सिव फोल्ड एक बाइनरी पेड़ के लिए एक पूंछ रिकर्सिव फोल्ड फ़ंक्शन ढूंढने की कोशिश कर रहा हूं। निम्नलिखित परिभाषा को देखते हुए:

// From the book "Functional Programming in Scala", page 45 
sealed trait Tree[+A] 
case class Leaf[A](value: A) extends Tree[A] 
case class Branch[A](left: Tree[A], right: Tree[A]) extends Tree[A] 

एक गैर पूंछ पुनरावर्ती क्रिया को लागू करने के लिए काफी स्पष्ट है:

def fold[A, B](t: Tree[A])(map: A => B)(red: (B, B) => B): B = 
    t match { 
    case Leaf(v)  => map(v) 
    case Branch(l, r) => 
     red(fold(l)(map)(red), fold(r)(map)(red)) 
    } 

लेकिन अब मैं एक पूंछ पुनरावर्ती गुना समारोह को खोजने के लिए इतना है कि एनोटेशन @annotation.tailrec इस्तेमाल किया जा सकता संघर्ष कर रहा हूँ।

मेरे शोध के दौरान मुझे कई उदाहरण मिल गए हैं जहां पेड़ पर पूंछ रिकर्सिव फ़ंक्शन उदा। अपने स्वयं के ढेर का उपयोग करके सभी पत्तियों की गणना की गणना करें जो मूल रूप से List[Tree[Int]] है। लेकिन जहां तक ​​मैं इस मामले में समझता हूं यह केवल जोड़ों के लिए काम करता है क्योंकि यह महत्वपूर्ण नहीं है कि आप पहले ऑपरेटर के बाएं या दाएं हाथ का मूल्यांकन करें या नहीं। लेकिन एक सामान्यीकृत फोल्ड के लिए यह काफी प्रासंगिक है। यहाँ मेरी उत्कटता दिखाने के लिए कुछ उदाहरण के पेड़ हैं:

val oldNewPairs = 
    trees.map(t => (t, fold(t)(Leaf(_): Tree[Int])(Branch(_, _)))) 

और फिर सबूत समानता के शर्त यह है कि:

val leafs = Branch(Leaf(1), Leaf(2)) 
val left = Branch(Branch(Leaf(1), Leaf(2)), Leaf(3)) 
val right = Branch(Leaf(1), Branch(Leaf(2), Leaf(3))) 
val bal = Branch(Branch(Leaf(1), Leaf(2)), Branch(Leaf(3), Leaf(4))) 
val cmb = Branch(right, Branch(bal, Branch(leafs, left))) 
val trees = List(leafs, left, right, bal, cmb) 

उन पेड़ों के आधार पर मैं की तरह दिया गुना विधि के साथ एक गहरी प्रतिलिपि बनाना चाहते हैं सभी बनाई गई प्रतियों के लिए है:

val conditionHolds = oldNewPairs.forall(p => { 
    if (p._1 == p._2) true 
    else { 
    println(s"Original:\n${p._1}\nNew:\n${p._2}") 
    false 
    } 
}) 
println("Condition holds: " + conditionHolds) 

क्या कोई मुझे कुछ पॉइंटर्स दे सकता है, कृपया?

आप कर सकते हैं ScalaFiddle पर इस सवाल में इस्तेमाल किया कोड को खोजने: https://scalafiddle.io/sf/eSKJyp2/15

Answer 1

यदि आप समारोह कॉल स्टैक का उपयोग कर बंद करो और एक ढेर अपने कोड द्वारा प्रबंधित और एक संचायक का उपयोग शुरू एक पूंछ पुनरावर्ती समाधान तक पहुँच सकता है:

def fold[A, B](t: Tree[A])(map: A => B)(red: (B, B) => B): B = { 

    case object BranchStub extends Tree[Nothing] 

    @tailrec 
    def foldImp(toVisit: List[Tree[A]], acc: Vector[B]): Vector[B] = 
    if(toVisit.isEmpty) acc 
    else { 
     toVisit.head match { 
     case Leaf(v) => 
      val leafRes = map(v) 
      foldImp(
      toVisit.tail, 
      acc :+ leafRes 
     ) 
     case Branch(l, r) => 
      foldImp(l :: r :: BranchStub :: toVisit.tail, acc) 
     case BranchStub => 
      foldImp(toVisit.tail, acc.dropRight(2) ++ Vector(acc.takeRight(2).reduce(red))) 
     } 
    } 

    foldImp(t::Nil, Vector.empty).head 

} 

विचार बाएं से दाएं मूल्यों जमा, एक ठूंठ नोड की शुरूआत से अपने पिता होने के संबंध का ट्रैक रखने और परिणाम को कम करने के संचायक के अंतिम दो तत्वों का उपयोग कर अपने red समारोह का उपयोग कर रहा है, जब भी एक ठूंठ नोड अन्वेषण में पाया जाता है।

इस समाधान को अनुकूलित किया जा सकता है लेकिन यह पहले से ही एक पूंछ पुनरावर्ती कार्य कार्यान्वयन है।

संपादित करें:

यह थोड़ा एक ढेर के रूप में देखा एक सूची संचायक डेटा संरचना को बदलने के द्वारा सरल किया जा सकता:

def fold[A, B](t: Tree[A])(map: A => B)(red: (B, B) => B): B = { 

    case object BranchStub extends Tree[Nothing] 

    @tailrec 
    def foldImp(toVisit: List[Tree[A]], acc: List[B]): List[B] = 
    if(toVisit.isEmpty) acc 
    else { 
     toVisit.head match { 
     case Leaf(v) => 
      foldImp(
      toVisit.tail, 
      map(v)::acc 
     ) 
     case Branch(l, r) => 
      foldImp(r :: l :: BranchStub :: toVisit.tail, acc) 
     case BranchStub => 
      foldImp(toVisit.tail, acc.take(2).reduce(red) :: acc.drop(2)) 
     } 
    } 

    foldImp(t::Nil, Nil).head 

}