Проблема с несоответствием Tycon - PullRequest
Новая
       10

Проблема с несоответствием Tycon

0 голосов
/ 21 сентября 2018

Работа над домашним заданием, которое, по сути, берет дерево, объявление которого: 

datatype a BinTree = 
Leaf of a
| Node of a BinTree * a BinTree;

и возвращает кортеж с высотой int дерева и список значений, которые были сохранены в самом глубокомчасть дерева. 

fun deepest tree = 
case tree of 
Leaf(n) => [n]
| Node(l, r) => if #1(deepest l) > #1(deepest r) then ((#1(deepest l) + 1), #2(deepest l)) else
                if #1(deepest l) < #1(deepest r) then ((#1(deepest r) + 1), #2(deepest r)) else
                (1, #2(deepest l) @ #2(deepest r));

Пытаясь проверить этот код, я получаю следующее сообщение об ошибке: 

stdIn:43.1-47.35 Error: types of rules don't agree [tycon mismatch]
earlier rule(s): 'Z BinTree -> 'Z list
this rule: 'Z BinTree -> [+ ty] * 'Y list
in rule:
Node (l,r) =>
  if (fn <rule>) (deepest <exp>) > (fn <rule>) (deepest <exp>)
  then (<exp> <exp> + 1,(fn <rule>) (deepest <exp>))
  else if <exp> <exp> < <exp> <exp>
       then (<exp> + <exp>,<exp> <exp>)
       else (1,<exp> @ <exp>)
stdIn:21.2-47.35 Error: right-hand-side of clause doesn't agree with 
function result type [type mismatch]
expression:  'Z list
result type:  {1:[+ ty], 2:'X list; 'Y}
in declaration:
deepest =
  (fn tree =>
        (case tree
          of <pat> => <exp>
           | <pat> => <exp>))
stdIn:1.2-47.35 Error: unresolved flex record (need to know the names of ALL 
the fields
in this context)
type: {1:[+ ty], 2:'Y list; 'Z}

Хотя я понимаю, что это конфликт типов, я могуне найти, что это за конфликт, и как это исправить.Любая помощь будет оценена.

Ответы [ 2 ]

0 голосов
/ 23 сентября 2018

Хотя я также предпочитаю case-of , например, molbdnilo для написания этой функции, здесь приведен пример использования let-in-end , чтобы продемонстрировать, что они оба могут использоваться, когдаРезультатом является продукт (кортеж).Поскольку в случае «если-то-еще» есть три случая с тремя различными исходами (dl > dr, dr > dl и dl = dr), использование Int-compare может быть предпочтительным: 

fun deepest (Leaf n) = (1, [n])
  | deepest (Node (l, r)) =
    let val (lcount, ls) = deepest l
        val (rcount, rs) = deepest r
    in case Int.compare (lcount, rcount) of
            GT => (lcount + 1, ls)
          | LT => (rcount + 1, rs)
          | EQ => (lcount + 1, ls @ rs)
    end
0 голосов
/ 21 сентября 2018

Это 

earlier rule(s): 'Z BinTree -> 'Z list

происходит от конечного случая ([n]), что делает его функцией от деревьев до списков.

И это: 

this rule: 'Z BinTree -> [+ ty] * 'Y list

происходит из случая узла, превращая его в функцию из деревьев в пары «типа, поддерживающего сложение» и списков.

Остальные ошибки вызваны тем, что SML не может определить, что #1 и#2 означает при наличии этого конфликта.

Ваш базовый случай неверен - это должна быть пара, а не список.
Глубина в этой паре должна быть 1, а глубина не должнабыть 1 в случае, когда оба поддерева одинаково глубоки.

Вы также вычисляете самые глубокие значения три раза для каждого поддерева в худшем случае и два в лучшем случае.
Лучше рекурсироватьтолько один раз для каждого поддерева.

Примерно так: 

fun deepest (Leaf n) = (1, [n])
  | deepest (Node (l, r)) =
        case deepest l of (dl, ll) =>
        case deepest r of (dr, lr) =>
                      if dl > dr then (dl + 1, ll)
                      else if dr > dl then (dr + 1, lr)
                      else (dl + 1, ll @ lr)
...