スカラ - 設定された深さのツリーにはどのようなタイプを使用しますか？

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++で、多かれ少なかれ、実用的な依存型システムを生成することができますが、彼らはあなたがすでにScalaで実用的であると考えられてきたものを醜いものが、だから、何もしBranchNode[BranchNode[BranchNode[BranchNode[TwigNode[A]]]]]

に多少似ていません。

完全なツリーを構築して処理するいくつかの数学的方法がありますが、しかし、それらのあなたの無関心は予測可能であるため省略されることになります。

Answer 2

この種のものは依存型を必要とし、Scalaではサポートされていません。

ただし、はです。タイプシステムで教会の数字表現を使用してください。