Получение выражения не соответствует ошибке

Question

Я пытаюсь реализовать функцию удаления узла для двоичного дерева поиска в 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) => ... 

Кто-нибудь знает, почему это происходит?

Answer 1

Ваше сравнение с использованием = в remove означает, что дерево должно содержать типа равенства (отсюда два ' символов в переменной ''Z типа, SML выведенного), но вы утверждали, что это более общее: remove: 'a -> 'a stree -> 'a stree;.

Вам нужно либо использовать только типы равенства (то есть объявить remove: ''a -> ''a stree -> ''a stree;)
или переопределять remove2 использовать случай анализа вместо сравнения.

Например,

| remove2 v (node as Node(k, Empty, Empty)) = if f(v, k) then Empty else node