1

我想在标准 ml 中创建一个函数来检查树是否完整，该函数以某种方式工作，但它给了我错误的类型和非详尽情况的警告

树代码：

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;
4

2 回答 2

0

关于 polyEqual 警告：在 SML/NJ 中，每次使用此运算符时都会打印此警告，但这并不意味着您的代码有问题。这是一篇关于它的博客文章，在评论中有人解释了为什么给出警告： http: //abstractfactory.blogspot.fr/2006/05/sml-hacking-tip-turn-off-polyequal.html

于 2012-03-29T15:32:20.733 回答
0

''a tree -> booltype 表示它a是一个相等类型：它必须是支持用equals 进行测试的类型。由于您使用=and<>来测试xand z，因此树数据必须支持相等性（即使您没有对这些值做任何有趣的事情）。这是polyEqual警告的根源。

非详尽的匹配警告更令人费解。当我将您的数据类型和函数定义粘贴到莫斯科 ML 中时，我没有收到警告。我认为我不会太担心它，因为我希望修复类型也能处理警告。

要获得所需的 type '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：您在不考虑内容的情况下称树完成。不过，这与您看到的警告没有任何关系。

于 2012-03-29T17:26:53.370 回答