Блог

Как новичок в функциональном программировании (OCaml), я столкнулся с этой проблемой.

Я придумал код, показанный ниже:

 let rec height tr =
match tr with
  | Node(d,[]) -> 1 
  | Node(d,[t1]) -> 1   height t1
  | Node(d,[t1;t2]) -> 1   max (height t1) (height t2)
 

Но верхний уровень (utop) для OCaml выдает предупреждение:

 Warning 8: this pattern-matching is not exhaustive.
Here is an example of a case that is not matched:
Node (_, _::_::_::_)
 

И когда я бегу

 let t : int gt =
Node('a',
     [Node('b',[]);
     Node('c',
      [Node('d',
        [Node('e',[])]);
      Node('f',[]);
      Node('g',[])])
     ]);;

height t;;
 

utop выдает исключение о сбое матча.

Я также реализовал это:

 let rec height' tr =
match tr with
  | Node(d,[]) -> 1 
  | Node(d,_::xs) -> 1   max (List.map height' xs) 
 

и он возвращается с

 Line31 |   | Node(d,_::xs) -> 1   max (List.map height' xs) 
                              ^^^^^^^^^^^^^^^^^^^^^^^^^
Error: This expression has type int list -> int list
       but an expression was expected of type int
 

Кроме того, я также попробовал другой способ:

 let rec height tr =
match tr with
  | Node(d,[]) -> 1 
  | Node(d,[t1]) -> 1   height t1
  | Node(d, t1::t2) -> 
  if t2=[]
  then 2
  else
  2   height t2
 

тогда ошибка была:

 Line26 |   2   height t2 
                  ^^
Error: This expression has type 'a gt list
       but an expression was expected of type 'a gt
 

Итак, как я могу преодолеть эту проблему?

Твоя проблема

Ваша height функция ожидает значение типа 'a gt . Когда вы звоните height t2 , t2 это конец списка, который является a gt list . Если вы передадите это height , вы получите несоответствие типов.

Как подойти к этой проблеме

Дано определение дерева:

 type 'a gt = Node of 'a * 'a gt list
 

Написание height функции просто, и я думаю, что вы, возможно, переосмысливаете ее, учитывая количество случаев в вашем сопоставлении шаблонов.

При любой рекурсии ключ является базовым случаем. У тебя есть это:

 let rec height tr =
  match
  | Node (_, []) -> 1
 

Узел с пустым списком имеет высоту 1. Фактические данные в дереве не важны, поэтому мы используем _ их в соответствии с шаблоном.

Единственная другая возможность заключается в том, что список не пуст. Таким образом, мы можем сопоставить шаблон с непустым списком. Опять же, первый узел не имеет значения.

 let rec height tr =
  match
  | Node (_, []) -> 1
  | Node (_, _::xs) -> 2   ...
 

Теперь мы должны превратить a 'a gt list в int. height превратит 'a gt значение в int для меня. Так почему бы мне просто не составить карту xs ?

 let rec height tr =
  match
  | Node (_, []) -> 1
  | Node (_, _::xs) -> 2   List.map height xs
 

Ах, но это превращается xs в ан int list , который мы не можем добавить к ан int . Мы можем суммировать этот список, используя fold_left .

 let rec height tr =
  match
  | Node (_, []) -> 1
  | Node (_, _::xs) -> 
    let sum = List.fold_left ( ) 0 in
    2   sum (List.map height xs)
 

Еще одно

Используя function ключевое слово, мы можем упростить это.

 let rec height =
  function
  | Node (_, []) -> 1
  | Node (_, _::xs) -> 
    let sum = List.fold_left ( ) 0 in
    2   sum (List.map height xs)