標準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 

コードが間違っていますか？ おかげ

EDIT：私のコードの

セカンドバージョン：

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

あなたのコードの最初のバージョンとの2つの問題：

• あなたが使用されることはありませんあなたのletブロック内の関数を宣言していて、最初の引数が空のリストになるまで、あなたの関数が自分自身を再帰的に呼び出して、あなたのコードはfun makeBST _ _ = EMPTYに簡略化できるので、おそらくSMLはどのタイプがEMPTYであるのか分からないため、受信しているエラーの原因になっている可能性があります。あなたは番目のバージョンを作ったので、単一引用符

けれどもべきである3行目の

二重引用符は、私はあなたが既にこれをキャッチ推測しています。あなたの新しいコードは、それでもまだ正しいわけではありません。この関数の呼び出し結果は、ルートのリストの最初の要素と2つのEMPTYの子を持つツリーです。左と右のサブツリーを比較して、新しい値を適切な場所に追加していますが、問題は、ツリー全体ではなくそのサブツリーのみを返すことです。何がしたいことは以下の通りです：

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;