0

SML/njで二分探索木のノード削除機能を実装しようとしています。しかし、制約エラーが発生しているので、理由がわかりません...

datatype 'a tree = Empty | Node of 'a * 'a tree * 'a tree;
datatype 'a stree = STree of ('a * 'a -> bool) * ('a * 'a -> bool) * 'a tree;

fun removeMin Empty = Empty
  | removeMin (Node(_,Empty,r)) = r
  | removeMin (Node(k,l,r)) = Node(k, removeMin l, r);
removeMin: 'a tree -> 'a tree;

fun get_left_most Empty = Empty
  | get_left_most (Node(k,Empty,r)) = Node(k,Empty,r)
  | get_left_most (Node(_,l,_)) = get_left_most l;
get_left_most: 'a tree -> 'a tree;



fun get_key (Node(k, l, r)) = k;
get_key: 'a tree -> 'a;

fun tree_empty Empty = true
  | tree_empty (Node(_,_,_)) = false;
tree_empty: 'a tree -> bool;



fun remove v (STree(f, g, stree2)) =     
    let
        fun remove2 v Empty = Empty
          | remove2 v (Node(k,l,r)) =
            if f(v, k) then 
                if (tree_empty l) then r
                else if (tree_empty r) then l
                else Node(get_key (get_left_most r), l, removeMin r)
            else if g(v, k) then Node(k, (remove2 v l), r)
            else Node(k, l, remove2 v r);
    in
        STree(f, g, (remove2 v stree2))
    end;
remove: 'a -> 'a stree -> 'a stree;

これは私が得ているエラーです:(のためにget_key）

Warning: match nonexhaustive
          Node (k,l,r) => ...

なぜこれが起こっているのか誰かが知っていますか？

4

1 に答える 1

0

=inを使用した比較removeは、ツリーに等価型が含まれている必要があることを意味します（したがって、SMLが推測'した型変数の2文字）が、より一般的であると主張しています。''Zremove: 'a -> 'a stree -> 'a stree;

等価型のみを使用する（つまり、declare remove: ''a -> ''a stree -> ''a stree;）
かremove2、比較ではなくユースケース分析を使用するように再定義する必要があります。

例えば、

| remove2 v (node as Node(k, Empty, Empty)) = if f(v, k) then Empty else node
于 2013-02-26T08:50:22.893 に答える