스칼라 - 설정된 깊이의 나무에 어떤 유형을 사용해야합니까?

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]]]]]

이미 스칼라에서는 이미 생각한 추악한 것들만 실용적입니다.

완전한 나무를 만들고 처리하는 수학적 방법이 있지만. 그러나 그것들에 대한 당신의 무관심은 예측 가능하기 때문에 생략해야합니다.

Answer 2

이런 종류의 객체에는 종속 형식이 필요하며 Scala에서는 지원하지 않습니다.

그러나 은 유형 시스템에서 교회 숫자 표현을 사용하여 수행 할 수 있습니다.