Đệ quy đệ quy trên cây nhị phân ở Scala

Question

Tôi đang cố gắng tìm một hàm đệ quy đuôi gấp cho cây nhị phân. Căn cứ vào định nghĩa sau đây:

// 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] 

Thực hiện một cái đuôi chức năng không đệ quy là khá đơn giản:

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)) 
    } 

Nhưng bây giờ tôi đang phải vật lộn để tìm một cái đuôi chức năng lần đệ quy để các chú thích @annotation.tailrec có thể được sử dụng.

Trong nghiên cứu của mình, tôi đã tìm thấy một số ví dụ về các hàm đệ quy đuôi trên cây có thể, ví dụ: tính toán tổng của tất cả các lá bằng cách sử dụng một ngăn xếp của riêng mà sau đó về cơ bản là một List[Tree[Int]]. Nhưng theo như tôi hiểu trong trường hợp này, nó chỉ hoạt động cho các bổ sung bởi vì nó không quan trọng cho dù bạn đầu tiên đánh giá bên trái hoặc bên phải của nhà điều hành. Nhưng đối với một lần tổng quát thì nó khá liên quan. Để hiển thị tăng thêm của tôi ở đây là một số cây dụ:

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) 

Dựa trên những cây Tôi muốn tạo ra một bản sao sâu với phương pháp lần nhất định như:

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

Và sau đó chứng minh rằng điều kiện bình đẳng giữ cho tất cả các bản sao được tạo:

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) 

Ai đó có thể cho tôi một số gợi ý, vui lòng?

Bạn có thể tìm thấy mã được sử dụng trong câu hỏi này tại ScalaFiddle: https://scalafiddle.io/sf/eSKJyp2/15

Answer 1

Bạn có thể đạt được một cái đuôi giải pháp đệ quy nếu bạn ngừng sử dụng chức năng gọi stack và bắt đầu sử dụng một chồng theo mã của bạn được quản lý và một ắc:

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 

} 

ý tưởng là để tích lũy giá trị từ trái sang phải, theo dõi các mối quan hệ cha mẹ bởi sự ra đời của một nút còn sơ khai và giảm kết quả bằng cách sử dụng chức năng red của bạn bằng cách sử dụng hai yếu tố cuối cùng của ắc bất cứ khi nào một node còn sơ khai được tìm thấy trong cuộc thăm dò.

Giải pháp này có thể được tối ưu hóa nhưng nó đã là một triển khai hàm đệ quy đuôi.

EDIT:

Nó có thể được đơn giản hóa một chút bằng cách thay đổi cấu trúc dữ liệu ắc vào một danh sách xem như một chồng:

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 

}