1

リストと関数を取り、それから 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

コードの何が問題になっていますか? ありがとう

編集：

私のコードの2番目のバージョン:

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;

このコードは私が望む型を生成しましたが、それは正しいですか?

4

1 に答える 1

2

コードの最初のバージョンに関する 2 つの問題:

  • 決して使用されない let ブロックで関数を宣言しており、関数は最初の引数が空のリストになるまで再帰的に自分自身を呼び出すため、コードを単純化しfun makeBST _ _ = EMPTYて . SML は型が何であるかを認識していないためEMPTYです。
  • 単一引用符である必要がある 3 行目の二重引用符

しかし、あなたは 2 番目のバージョンを作成したので、これはもうわかっていると思います。ただし、新しいコードはまだ正しくありません。この関数を呼び出した結果は、リストの最初の要素をルートとし、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;
于 2012-04-01T05:59:14.227 に答える