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)
  }
}

但是类型检查器在这里没有帮助我。如果插入方法(或任何其他方法)中存在错误，则树可能会以不同距离的叶节点结束。是否有可能让类型检查器验证一切是否正确，诉诸一些疯狂的东西(在类型系统中实现 Peano 算法？)或使用像 BranchNode[BranchNode[BranchNode[BranchNode[TwigNode[A]]]]] 这样的丑陋类型?

Answer 1

您想要的功能通常称为 dependent type系统。目前还没有实现该功能的常用编程语言。
尽管您可以在 C++ 中生成或多或少实用的依赖类型系统，但它们看起来有点类似于 BranchNode[BranchNode[BranchNode[BranchNode[TwigNode[A]]]]]
所以除了你已经考虑过的那些丑陋的东西在 Scala 中是实用的。

尽管有一些数学方法可以构建和处理完整的树。但是它们将被省略，因为您对这些不感兴趣是可以预见的。