проверить, является ли дерево полным стандартным мл - PullRequest
Новая
       45

проверить, является ли дерево полным стандартным мл

1 голос
/ 29 марта 2012

Я хочу сделать функцию в стандартном мл, которая проверяет, завершено ли дерево, функция каким-то образом работает, но дает неправильный тип и предупреждает о неисчерпывающих случаях

Деревокод: 

datatype 'data tree = 
  EMPTY
| NODE of 'data tree * 'data * 'data tree;

fun isComplete EMPTY = true
  | isComplete (NODE(x, y, z)) = if (x = EMPTY andalso z <> EMPTY) orelse (x <> EMPTY andalso z = EMPTY) then false else true;

Теперь тип функции выше: ''a tree -> bool, но обязательный тип 'a tree -> bool

У меня предупреждение: 

stdIn:169.8 Warning: calling polyEqual
stdIn:169.26 Warning: calling polyEqual
stdIn:169.45-169.47 Warning: calling polyEqual
stdIn:169.64-169.66 Warning: calling polyEqual
stdIn:124.1-169.94 Warning: match nonexhaustive
          NODE (x,y,z) => ...

В чем проблема?

РЕДАКТИРОВАТЬ:

Благодаря Майклу, я исправил код, и теперь он работает: 

- fun isComplete EMPTY = true
    | isComplete (NODE(EMPTY, _, EMPTY)) = true
    | isComplete (NODE(NODE(x, y, z), _, NODE(a, b, c))) = true
    | isComplete (EMPTY, _, NODE(x, y, z)) = false
    | isComplete (NODE(x, y, z), _, EMPTY) = false;

Ответы [ 2 ]

0 голосов
/ 29 марта 2012

Тип ''a tree -> bool указывает, что a является типом равенства: это должен быть тип, который поддерживает тестирование с использованием равенства.Поскольку вы используете = и <> для проверки x и z, данные дерева должны поддерживать равенство (даже если вы ничего не делаете со значениями).Это корень предупреждения polyEqual.

Предупреждение о неисчерпывающем совпадении более загадочно.Когда я вставляю ваш тип данных и определения функций в Moscow ML, я не получаю предупреждение.Я не думаю, что бы беспокоиться об этом слишком сильно, так как ожидал, что исправление типа также позаботится о предупреждении.

Чтобы получить желаемый тип 'a tree -> bool, я бы предложилизбавиться от if в пользу сопоставления с образцом.Например: 

fun isComplete EMPTY = true
  | isComplete (NODE(EMPTY, _, EMPTY)) = true
  | isComplete (NODE(EMPTY, _, NODE(x,y,z))) = false
  | ... (* fill out the rest of the cases *)

Я предоставлю вам возможность выяснить полный набор дел, так как это выглядит как домашнее задание.

Кстати, я не думаю, что ваш тест на полноту правильный.Подумайте, что происходит, когда ни одно из поддеревьев не является EMPTY: вы называете дерево завершенным, не рассматривая его содержимое.Это не имеет ничего общего с предупреждениями, которые вы видите.

0 голосов
/ 29 марта 2012

Относительно предупреждения polyEqual: в SML / NJ это предупреждение выводится каждый раз, когда вы используете этот оператор, но это не означает, что ваш код неисправен. Вот сообщение в блоге об этом, и в комментариях кто-то объясняет, почему выдается предупреждение: http://abstractfactory.blogspot.fr/2006/05/sml-hacking-tip-turn-off-polyequal.html

...