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 推断的类型变量中的两个'字符''Z）但您声称它更通用：remove: '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 回答