scala - 对Tree Fold实现的理解

Question

我是 scala 新手，现在已经了解了它的基础知识。由于我的互联网研究，我发现了这个blog关于逆 B 树的帖子。我确实理解其中的大部分内容，但是这一部分:

def fold[A, B](t:Tree[A] , z:B)(f:(B,A,B) => B): B = t match {
  case EmptyTree => z
  case Node(x,l,r) => f ( fold( l , z )(f) , x , fold( r , z )(f) )
}

这个(f:(B,A,B) => B)是什么意思？另外，为什么我需要将其括在此处 f ( Fold( l , z )(f) , x , Fold( r , z )(f) ) 以及递归调用之后？

Answer 1

在 Scala 中，fold 通常作为“简化为单个值”表达式的简写提供，否则该表达式将通过模式匹配来完成。

例如，Option#fold本质上是

// in Option[A]
def fold[B](ifEmpty: => B)(f: A => B): B = this match {
  case None => ifEmpty
  case Some(a) => f(a)
}

和Either#fold本质上是

// in Either[A, B]
def fold[C](fa: A => C, fb: B => C): C = this match {
  case Left(a) => fa(a)
  case Right(b) => fb(b)
}

和List.foldLeft本质上是

def foldLeft[B](z: B)(op: (B, A) => B) = this match {
  case Nil => z
  case head :: tail => tail.foldLeft(op(z, head))(op) // recursion!
}

(免责声明:我没有从 Scala 源代码中获取这些内容，这只是我自己对这些方法的理解)

fold 的总体目标是根据 f 函数将集合(即 Option/Seq/Either/Tree)减少为单个值你传递给它。 f 是一个匿名函数，通常充当“值可用时的转换”或“将下一个输入与上一个/递归结果组合”操作。

就博客文章中的 Tree 类而言，Tree 是一种递归数据结构，因此自然地将其简化为单个值将涉及一些递归。这就是为什么您会在 fold 实现中看到 fold( l , z )(f) 和 fold( r , z )(f) 。这些正在计算节点的左子树和右子树的折叠结果(类型为B)。然后使用 f 将这些结果与节点自身的值(A 类型)结合起来。

它可能有助于重新排列和重命名事物:

def fold[A, B](tree: Tree[A], ifEmpty: B)(combine: (B, A, B) => B): B = t match {
  case EmptyTree => ifEmpty
  case Node(value, left, right) =>
    // recurse into `left` and `right`
    val leftResult = fold(left, ifEmpty)(combine)
    val rightResult = fold(right, ifEmpty)(combine)
    combine(leftResult, value, rightResult)
}

在博文中，作者定义了 def size 作为 fold 的示例用法:

def size[T] (tree: Tree[T]) =
  fold(tree, 0: Int){(l,x,r) => l + r + 1}

这可能更有意义

def size[T](tree: Tree[T]): Int =
  fold(tree, 0){ (leftSize, x, rightSize) => leftSize + rightSize + 1 }

博客文章的结论在其 fold 调用中使用 B = Tree[A] 来完成树反转。 combine(即f)函数采用已经反转的左子树和右子树，并构造一个新的节点，将它们放在相反的位置。 fold 实现负责递归，只调用 f/combine 函数将事物组合在一起。