0

課題は、二分探索木から要素を削除する関数を ML でコーディングすることです。コードは次のとおりです。

datatype 'a tree = Lf | Br of 'a * 'a tree * 'a tree;

fun deleteTop (Br(_, Lf, t2)) = t2
  | deleteTop (Br(_, t1, Lf)) = t1
  | deleteTop (Br(_, Br(v, u1, u2), t2)) =
    Br(v, deleteTop (Br(v, u1, u2)), t2);

fun delete (Lf, k : string) = Lf
  | delete (Br((a,b),t1,t2), k) =
    if a=k then deleteTop(Br((a,b),t1,t2))
    else if k<a then Br((a,b),delete(t1,k),t2)
            else Br((a,b),t1,delete(t2,k));

これを Poly/ML にロードすると、deleteTop での不完全なパターン マッチングが警告されますが、delete は deleteTop のみをブランチに渡すため、それは問題ではありません。

val deleteTop = fn: 'a tree -> 'a tree
val delete = fn: (string * 'a) tree * string -> (string * 'a) tree

(string * int) ツリーを作成して実行しました

> delete(a,"they");
Error-Type error in function application.
   Function: delete : (string * 'a) tree * string -> (string * 'a) tree
   Argument: (a, "they") : (string * int) tree * string
   Reason:
      Can't unify (string * 'a) tree with (string * int) tree
      (Different type constructors)
Found near delete (a, "they")
Static Errors

これらの行の 1 つを繰り返します。

Can't unify (string * 'a) tree with (string * int) tree

ML が 'a を int と統合できないのはなぜですか?

4

1 に答える 1

1

を定義してから最上位でツリーと削除を再定義した場合、そのようなメッセージを受け取ることができます。aのツリーがdeleteのツリーと同じではないと不平を言っています。

例えば

> datatype 'a t = T of 'a;
datatype 'a t = T of 'a
> val x = T 1;
val x = T 1: int t
> datatype 'a t = T of 'a;
datatype 'a t = T of 'a
> val T y = x;
Pattern and expression have incompatible types.
   Pattern: T y : 'a t
   Expression: x : int t
   Reason: Can't unify 'a t with int t (Different type constructors)
Found near val T y = x
Static Errors
>
于 2013-11-01T19:58:03.450 に答える