Как суммировать все узлы этой функции 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) 

Просто добавьте 1 в z при посещении узла для подсчета количества узлов

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 

В функции вашей многообещающей вернуть Int на основе на дереве которого вы не знаете тип элемента, параметризованный как A. Это приведет вас добавить Int в A.

Подсчет и подсчет - это разные вещи, если вы решили подсчитать количество значений, вам не нужно ничего знать о A. Если вы решите суммировать значения, вам необходимо знать, что у вас есть оператор +, определенный для A.

Возможно, вам потребуется узнать больше о типах scala. https://twitter.github.io/scala_school/advanced-types.html