표준 ml 목록에서 bst를 만듭니다.

Question

목록 및 기능을 사용하고 BST를 만드는 기능 표준 ml을 만들고 싶습니다. 'a list -> ('a * 'a -> bool) -> 'a tree,하지만 난 그것을 몇 가지 문제가 있어요, 여기에 내가 쓴 코드입니다 : : 함수의 유형입니다

datatype 'data tree = 
    EMPTY 
| NODE of 'data tree * 'data * "data tree; 

fun makeBST [] f = EMPTY 
    | makeBST (x::xs) f = 
    let 
     fun insert EMPTY x = NODE(EMPTY, x, EMPTY) 
      | insert (NODE(left, root, right)) x = 
       if f(x, root) then 
        insert left x 
       else 
        insert right x 
    in 
     makeBST xs f 
    end; 

난이 기능을지고있어 유형은 다음과 같습니다 'a list -> ('b * 'c -> bool) -> 'd tree 나는 그것을 호출 할 때 , makeBST [4, 3, 6, 7, 8, 2, 0, 1] (op <); 나는 다음과 같은 오류가 다음과 같은 :

stdIn:16.1-16.40 Warning: type vars not generalized because of 
    value restriction are instantiated to dummy types (X1,X2,...) 
val it = EMPTY : ?.X1 tree 

코드에 어떤 문제가 있습니까? 감사

편집 : 내 코드의

두 번째 버전 :

fun makeBST [] f = EMPTY 
    | makeBST (x::xs) f = 
     let 
      val tree = EMPTY 
      fun insert EMPTY x = NODE (EMPTY, x, EMPTY) 
       | insert (NODE(left, root, right)) x = 
        if f(x, root) then 
         insert left x 
        else 
         insert right x 
     in 
      insert (makeBST xs f) x 
     end; 

이 코드는 내가 원하는 종류를 생산하지만이 정확한지? 코드의 첫 번째 버전

Answer 1

두 가지 문제 :

• 당신은 사용하지 않고, 첫 번째 인수는 빈리스트가 될 때까지 함수가 자신을 재귀 적으로 호출 결코 당신의하자 블록에서 함수를 선언하고, 따라서 귀하의 코드는 fun makeBST _ _ = EMPTY으로 단순화 될 수 있습니다. 따라서 SML이 EMPTY이되어야 할 유형을 알지 못하기 때문에 발생하는 오류의 원인 일 수 있습니다. 두 번째 버전을 만들었 때문에, 작은 따옴표

에게 비록해야 라인 3

따옴표, 난 당신이 이미 잡은 같은데요. 아직 새 코드가 올바르지 않습니다. 이 함수를 호출 한 결과 목록의 첫 번째 요소가 루트이고 두 개의 자식이 두 개있는 자식 트리입니다. 왼쪽 및 오른쪽 하위 트리를 비교 한 다음 올바른 값으로 새 값을 추가하지만 문제는 전체 트리가 아닌 해당 하위 트리 만 반환한다는 것입니다. 당신이 원하는 것은 다음과 같다 :

fun makeBST [] f = EMPTY 
    | makeBST (x::xs) f = 
     let 
      val tree = EMPTY 
      fun insert EMPTY x = NODE (EMPTY, x, EMPTY) 
       | insert (NODE(left, root, right)) x = 
        if f(x, root) then 
         Node(insert left x, root, right) 
        else 
         Node(left, root, insert right x) 
     in 
      insert (makeBST xs f) x 
     end;