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

Question

我正在尝试实现尾递归 foldLeft用于规则形状的树的函数。该练习来自练习 3.3.5.3 中的“The Science of Functional Programming”一书。

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

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

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 的 case 类中的元素.我只能匹配 Leaf和 Branch (而不是叶子在 Twig 内)，因此递归没有结束。

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

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