Проверка наличия данного значения в двоичном дереве

Question

Я новичок в SML. Я пытаюсь проверить, существует ли данное значение в двоичном дереве или нет. Ниже приведен фрагмент кода. После исполнения он дает

Warning : match nonexhaustive (n,Node (t1, j, t2)) => ... 

Я не могу понять, почему он показывает этот путь. Наверное, я рассмотрел все возможные случаи. Может ли кто-нибудь дать мне подсказку или ссылку, которая будет полезна для удаления этого предупреждения.

datatype inttree = Empty | Node of inttree * int * inttree; 

(*find(n,K) here n is the key that we have to find in inttree K*) 
val rec find = fn(n, Node(t1,j,t2)) => 
    let 
     val t = Node(t1, j, t2) 
     val compare = fn(i,j) => i = j 
     val find' = 
      fn (n,Empty) => false    (* if we have reached the empty node then we are not able to find the key therefore return false *) 
      | (n,Node(t1,j,t2)) => 
       if compare(n,j) 
       then true       (* if value n and j are equal we have found the key n in the tree*) 
       else find(n,t1) orelse find(n,t2) (* if the value is not equal check in left subtree if found return true else check in the right subtree*) 
    in 
     find'(n,t) 
    end; 

Answer 1

Учитывая вашу декларацию типа данных, возможен довольно прямой рекурсивный подход. Так как это, кажется, домашнее задание, я не хочу, чтобы дать полное решение, но здесь это функция, которая имеет такой же вкус:

fun allEven Empty = true 
| allEven (Node(t1,i,t2)) = 
     if i mod 2 = 1 then false 
     else allEven t1 andalso allEven t2; 

Эта функция возвращает истину или ложь в зависимости от наличия или отсутствия всех целых чисел дерево ровное. Это имеет базового случай

allEven Empty = true 

(верно, так как нет нечетных чисел в пустом дереве, чтобы служить в качестве контр-примеров) и рекурсивного случай

allEven (Node(t1,i,t2)) = 
      if i mod 2 = 1 then false 
      else allEven t1 andalso allEven t2; 

Если целого число в узле нечетно , return false - в противном случае верните true, если рекурсивный вызов для обеих ветвей будет равен true.

Типичные пробеги:

- allEven (Node(Node(Empty,3,Empty),5,Node(Node(Empty,6,Empty),7,Empty))); 
val it = false : bool 
- allEven (Node(Node(Empty,4,Empty),2,Node(Node(Empty,6,Empty),8,Empty))); 
val it = true : bool 

Ваша функция должна быть об этом долго и следовать той же основной рекурсивный шаблон.

Answer 2

1. Кроме val rec, вы также можете написать fun и указать аргументы на левой стороне =.

2. Вспомогательная функция compare в значительной степени избыточна. Вы также можете использовать =. Кроме того, что можно было бы назвать функцию сравнения в ML, как правило, один, который возвращает заказ типа , имеющие значения LESS, EQUALS и GREATER:

   - ​Int.compare (3, 5); 
   > val it = LESS : order 
   

3. При написании if ... then true else ... или аналогичное утверждение, которое возвращает тип bool, вы могли бы просто использовать комбинаторы orelse и andalso.Например, вы можете заменить следующее:

   if compare(n,j) 
   then true 
   else find(n,t1) orelse find(n,t2) 
   

   с:

   n = j orelse find (n, t1) orelse find (n, t2) 
   

4. Многое, как встроенные функции List.exists и List.all принимают функцию как предикат и просматривает список в попытке доказать, либо, что существует хотя бы один элемент, для которого это верно, или что это верно для всех элементов, вы можете выполнять функции treeExists и treeForall:

   datatype intTree = Empty | Node of inttree * int * inttree; 
   
   fun treeExists f Empty = false 
       | treeExists f (Node (leftTree, x, rightTree)) = 
       f x orelse treeExists f leftTree orelse treeExists f rightTree 
   
   fun treeForall f Empty = true 
       | treeForall f (Node (leftTree, x, rightTree)) = 
       f x andalso treeForall f leftTree andalso treeExists f rightTree 
   

   Making функции find и allEven теперь стало проще:

   fun find (x, tree) = treeExists (fn y => x = y) tree 
   fun allEven tree = treeForall (fn x => x mod 2 = 0) tree 
   

   поскольку все рекурсии было оставлено на новые функции библиотеки.

   Подобным же образом, вы можете сделать treeMap и treeFold:

   fun treeMap f Empty = Empty 
       | treeMap f (Node (leftTree, x, rightTree)) = ... 
   
   fun treeFold f e Empty = e 
       | treeFold f e (Node (leftTree, x, rightTree)) = ... 
   

   Они могут быть использованы, чтобы найти наибольшее абсолютное значение в дереве:

   fun maxAbsTree tree = 
       treeFold Int.max 0 (treeMap Int.abs tree)