Попытки создать общую функцию просуммировать элементы дерева

Question

Я использую дерево, определенное здесь ...

https://gist.github.com/schmmd/1271891

где ...

class Tree[+T] 
case object Empty extends Tree[Nothing] 
case class Node[T](val elem: T, val left: Tree[T], val right: Tree[T]) extends Tree[T] 

Я добавил эту особенность ...

trait sum[T] { 
    def +(value: T): T 
} 

и я определил это дерево ...

val a = Node(1, Node(1, Empty, Node(5, Empty, Empty)), Node(2, Node(3, Empty, Empty), Empty)) 

Тогда я написал эту функцию, чтобы подытожить элементы ...

def sumTree[T <: sum[T]](t: Tree[T]): T = t match { 
    case Empty => 0 
    case Node(e, left, right) => e + sumTree(left) + sumTree(right) 
} 

Вопросы

1) Почему я должен определить черту (предполагая, что я имею правильно определил это), чтобы использовать «+»? Без него компилятор рассматривает это как попытку конкатенации строки.

2) Я не уверен, как обращаться с «пустым». Я хочу обрабатывать «Пусто» как 0 при сопоставлении с образцом, но я не могу из-за общей обработки. Неужели я не могу сделать эту работу с дженериками? Я должен был бы указать тип, который он принимает/возвращает заранее?

Answer 1

Поскольку ваш тип элемента T является общим, вам необходимо предоставить вспомогательную структуру для работы с добавлением. Scala не знает, как добавить два элемента типа T без дополнительной информации. Вот почему вы определяете черту sum. Как вы правильно подозреваете, вам также нужен способ узнать, что такое нулевой элемент. Таким образом, вы предпочли бы использовать что-то вроде этого:

trait Sum[T] { 
    def zero: T 
    def plus(x: T, y: T): T 
} 

Обратите внимание, что мы определяем plus с два операндами. Затем вместо того, чтобы требовать, чтобы T <: Sum[T] был подтипом Sum, вы предоставляете неявное значение (называемое классом типа). Это упрощает использование вашего дерева с произвольными типами, даже если элемент не реализует Sum.

Существуют существующие типы классов, которые могут выполнять эту функцию, которая в основном представляет собой «моноид». Библиотека стандартного класса Scala имеет Numeric, которую вы можете использовать. Это немного больше, чем просто моноид, определяющий несколько арифметических операций, включая zero и plus.

Тогда ваша агрегатная функция становится:

def sumTree[T](t: Tree[T])(implicit num: Numeric[T]): T = t match { 
    case Empty => num.zero 
    case Node(e, left, right) => 
    num.plus(e, num.plus(sumTree(left), sumTree(right))) 
} 

Вы также можете импортировать некоторые синтаксический помощника:

def sumTree[T](t: Tree[T])(implicit num: Numeric[T]): T = t match { 
    case Empty => num.zero 
    case Node(e, left, right) => 
    import num.mkNumericOps 
    e + sumTree(left) + sumTree(right) 
} 

---

Смотрите также:

• Scala equivalent of Java's Number
• http://like-a-boss.net/2012/07/30/ordering-and-ordered-in-scala.html