Scala - What type should I use for trees of a given depth?

Question

Suppose I want to create trees of a certain set depth, i.e. the length of the path from the top of the tree to any leaf node is some fixed number. Ideally, a type checker can verify that these trees are created and used correctly. For my problem, I implemented something like:

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

But type checking doesn't help me here. If there is an error in the insertion method (or any other method), the tree may end up with leaf nodes at different distances. Is it possible to get a validation type check so that everything is correct by resorting to something crazy (using Peano arithmetic in a type system?) Or having ugly types such as BranchNode[BranchNode[BranchNode[BranchNode[TwigNode[A]]]]] ?

Answer 1

This function is often referred to as a dependent type . And at the moment there is no common programming language used with the implemented function. Although you can create more or less practical systems of dependent types in C ++, they will look somewhat similar to BranchNode[BranchNode[BranchNode[BranchNode[TwigNode[A]]]]]

So, nothing but those ugly things you've already covered are practical in Scala.

Although there are some mathematical methods for constructing and processing full trees. But they must be omitted because your disinterest in them is predictable.

Answer 2

This type of thing requires dependent types and is not supported by Scala.

However, you can do this using a church numeric representation in a type system.