Scala - Какой тип я должен использовать для деревьев заданной глубины?

Question

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

import collection.mutable.HashMap

abstract class TreeNode[A, B] {
  def insert(data: B, path: List[A])
}

class TwigNode[A, B] extends TreeNode[A, B] {
  val hm = new HashMap[A, B]

  def insert(data: B, path: List[A]) {
    hm(path.head) = data
  }
}

class BranchNode[A, B](depth: Int) extends TreeNode[A, B] {
  val hm = new HashMap[A, TreeNode[A, B]].withDefaultValue(
    if (depth == 2)
      new TwigNode[A, B]
    else
      new BranchNode[A, B](depth - 1)
    )

  def insert(data: B, path: List[A]) {
    hm(path.head).insert(data, path.tail)
  }
}

Но проверка типов здесь мне не помогает. Если есть ошибка в методе вставки (или любом другом методе), дерево может закончить с листовыми узлами на разных расстояниях. Можно ли заставить средство проверки типов проверить, все ли правильно, прибегнуть к чему-то сумасшедшему (реализовать арифметику Пеано в системе типов?) Или иметь уродливые типы, такие как BranchNode[BranchNode[BranchNode[BranchNode[TwigNode[A]]]]]?

Answer 1

Требуемую функцию часто называют зависимым типом системой. И на данный момент не существует общепринятого языка программирования с этой функцией. Хотя вы можете создавать более или менее практичные системы зависимых типов в C ++, они будут выглядеть примерно так: BranchNode[BranchNode[BranchNode[BranchNode[TwigNode[A]]]]]

Так что ничего, кроме тех уродливых вещей, которые вы уже рассмотрели, практично в Scala.

Хотя есть некоторые математические методы для построения и обработки целых деревьев. Но они должны быть опущены, потому что ваш интерес к ним предсказуем.

Answer 2

Этот тип требует зависимых типов и не поддерживается Scala.

Тем не менее, вы можете сделать это, используя церковное представление чисел в системе типов.