如何总结此 scala fold_tree 函数中的所有节点

Question

我是 scala 的初学者。我得到了一个 fold_tree_preorder 函数，它在二叉树上实现了高阶函数折叠。树、节点和叶子定义如下

 abstract class Tree[+A]
  case class Leaf[A](value: A) extends Tree[A]
  case class Node[A](value: A, left: Tree[A], right: Tree[A]) extends Tree[A]

这是我得到的功能

  def fold_tree_preorder [Z,A](f:(Z,A)=>Z) (z:Z) (t:Tree[A]) : Z =
    t match {
      case Leaf(value) => f(z, value)
      case Node(value , lt, rt) => {
            val z1 = f(z,value)
            val z2 = fold_tree_preorder (f) (z1) (lt)
            fold_tree_preorder (f) (z2) (rt)

          }
      }

我不确定如何实际调用此函数。我正在尝试执行以下操作：

def count_tree [A](t:Tree[A]) : Int =
    fold_tree_preorder[A,A=>A]((z,a)=>(z+a))(0)(t)

但是我收到类型不匹配错误之类的错误。我也不认为参数本身是正确的，但我什至不确定如何测试输出结果，因为我不知道调用 fold_tree_preorder 函数的正确方法。如何输入正确的语法来调用此函数？

Answer 1

z 是 fold_tree_preorder 函数是您期望的输出类型，即 Int

使用如下函数

假设count_tree计算树的节点数

def count_tree [A](t:Tree[A]) : Int =
    fold_tree_preorder[Int, A]((z,a) => z + 1 )(0)(t)

只要在访问一个节点时在z上加上1来统计节点数

Answer 2

def fold_tree_preorder [Z,A](f:(Z,A)=>Z) (z:Z) (t:Tree[A]) : Z

第一个参数是 f，是一个函数，它获取到目前为止的结果（Z 类型）和树中包含的值 A)

 def count_tree [A](t:Tree[A]) : Int

在您的函数中，您承诺 return 一个基于您不知道其元素类型的树的 Int，参数化为 A。这会引导您将 Int 添加到 A。

求和和计数是不同的东西，如果你决定计算值的个数，你不需要知道任何关于A的事情。如果您决定对这些值求和，您需要知道您为 A.

定义了一个 + 运算符

您可能需要了解有关 Scala 类型的更多信息。 https://twitter.github.io/scala_school/advanced-types.html

如何总结此 scala fold_tree 函数中的所有节点

How to sum up all nodes in this scala fold_tree function

scala

fold