规则形状的树折叠左scala实现

Question

我正在尝试foldLeft为规则形状的树实现尾递归函数。该练习来自练习 3.3.5.3 中的“函数式编程的科学”一书。

到现在为止，我能够做功课，但我不知道我在这个功课中遗漏了什么。

规则形状的树有一个定义：

sealed trait RTree[A]
final case class Leaf[A](x: A) extends RTree[A]
final case class Branch[A](xs: RTree[(A,A)]) extends RTree[A]

方法签名和预期结果：

@tailrec
def foldLeft[A,R](t: RTree[A])(init: R)(f: (R,A)=>R): R= ???

foldLeft(Branch(Branch(Leaf(((1,2),(3,4))))))(0)(_+_)
//10

到目前为止最大的问题是我不知道如何匹配和访问Branch. 我只能匹配Leafand Branch（而不是叶子在分支内），因此递归没有结束。

Answer 1

不确定这是否有帮助，但现在我只有非尾递归实现。

def foldLeft[A, R](t: RTree[A])(init: R)(f: (R, A) => R): R = {
      t match {
        case Leaf(value) => f(init, value)
        case Branch(tree) =>
          foldLeft(tree)(init) {
            case (result, (left, right)) => f(f(result, left), right)
          }
      }
    }

更新：正如在此答案的评论部分中所说，这实际上是尾部记录实现，对不起，让您感到困惑。