Прежде всего, я верю и, если можно так выразиться, вы проделали очень хорошую работу. Я могу предложить пару небольших изменений в вашем коде:
abstract class Tree
case class Node(value: Int, left: Tree, right: Tree) extends Tree
case object Nil extends Tree
- Дерево не обязательно должно быть case-классом, кроме того, использование case-класса в качестве неконечного узла устарело из-за возможного ошибочного поведения автоматически сгенерированных методов.
Nil является синглтоном и лучше всего определяется как case-объект вместо case-class. Дополнительно рассмотрим квалификационный суперкласс Tree с sealed. sealed сообщает компилятору, что класс может быть унаследован только из одного и того же исходного файла. Это позволяет компилятору выдавать предупреждения всякий раз, когда следующее выражение соответствия не является исчерпывающим - другими словами, не включает все возможные случаи.
Запечатанное абстрактное дерево класса
Следующая пара улучшений может быть внесена в sumTree:
def sumTree(t: Tree) = {
// create a helper function to extract Tree value
val nodeValue: Tree=>Int = {
case Node(v,_,_) => v
case _ => 0
}
// parametrise fold with Tree to aid type inference further down the line
fold[Tree](t,Nil,(acc,l,r)=>Node(acc + nodeValue(l) + nodeValue(r) ,l,r))
}
nodeValue вспомогательная функция также может быть определена как (альтернативная нотация, которую я использовал выше, возможна, потому что последовательность падежей в фигурных скобках рассматривается как литерал функции):
def nodeValue (t:Tree) = t match {
case Node(v,_,_) => v
case _ => 0
}
Следующим небольшим улучшением является параметризация fold метода с Tree (fold[Tree]). Поскольку средство вывода типа Scala последовательно обрабатывает выражение слева направо, сообщая заранее, что мы будем иметь дело с древовидной структурой, мы опускаем информацию о типе при определении литерала функции, который передается в fold далее.
Итак, вот полный код, включая предложения:
sealed abstract class Tree
case class Node(value: Int, left: Tree, right: Tree) extends Tree
case object Nil extends Tree
object Tree {
def fold[B](t: Tree, e: B, n: (Int, B, B) => B): B = t match {
case Node(value, l, r) => n(value,fold(l,e,n),fold(r,e,n))
case _ => e
}
def sumTree(t: Tree) = {
val nodeValue: Tree=>Int = {
case Node(v,_,_) => v
case _ => 0
}
fold[Tree](t,Nil,(acc,l,r)=>Node(acc + nodeValue(l) + nodeValue(r) ,l,r))
}
}
Рекурсия, с которой вы столкнулись, является единственным возможным направлением, которое позволяет вам пройти по дереву и создать модифицированную копию неизменяемой структуры данных. Любые конечные узлы должны быть созданы в первую очередь перед добавлением в корень, потому что отдельные узлы дерева являются неизменяемыми, и все объекты, необходимые для построения узла, должны быть известны до построения: конечные узлы должны быть созданы до того, как вы сможете создать корневой узел.