斯卡拉 |在二叉树中折叠

Question

我在我的 scala 代码中实现了一个 fold 方法。我可以用它来确定树的size和depth。
现在我想实现 max 和 map 方法，它们应该像 here.
一样工作不同的是，值保存在分支而不是叶子。
到目前为止，这是我的代码：

sealed trait Tree[+A] {
  def size(): Int = fold(this)(() => 1)((l, r, v) => 1 + l + r)

  def depth(): Int = fold(this)(() => 0)((left: Int, right: Int, v: A) => 1 + (left max right))

  def fold[X, B](t: Tree[X])(f: () => B)(g: (B, B, X) => B): B = t match {
    case Leaf() => f()
    case Branch(left, right, v) => g(fold(left)(f)(g), fold(right)(f)(g), v)
  }
}

case class Leaf[A]() extends Tree[A]

case class Branch[A](left: Tree[A], right: Tree[A], v: A) extends Tree[A]

有人可以帮我吗？

Answer 1

首先，您可以将 fold 放入 Tree 的伴随对象（因为 fold 不使用 this 即 "static"）。

其次，开始为您的案例实施map

def map[A,B](t: Tree[A])(f: A => B): Tree[B] = t match {
  case Leaf() => ???_1
  case Branch(l, r, v) => ???_2 // here l, r are Tree[A]'s i.e. subtrees of t
}

查看在叶子中具有值的树的 implemented 情况。

然后将此实现替换为使用 fold

的实现

def map[B](f: A => B): Tree[B] = 
  fold[A, Tree[B]](this)(() => ???_1_)((l: Tree[B], r: Tree[B], v: A) => ???_2_))
  // here l, r are Tree[B]'s i.e. results of map for subtrees

???_1_ 和 ???_2_ 是 ???_1、???_2，其中您将 map 的递归调用替换为 l、r，这是递归调用的结果。所以 ???_1_ 正好是 ???_1.

斯卡拉 |在二叉树中折叠

Scala | Folding in binary tree

binary-tree

functional-programming

scala