檢查一棵樹是否完整標準ml

我想用標準ml來做一個函數來檢查一棵樹是否完整，這個函數在某種程度上可以工作，但是它給了我一個錯誤的類型和一個非窮舉情況的警告檢查一棵樹是否完整標準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;

來源

2012-03-29 hakuna matata

編輯代碼仍然不正確。它不是遞歸的。左側和右側的節點可能不完整。 – Milwaukoholic 2014-10-23 01:53:48

的''a tree -> bool類型表明a是平等型：它必須是支持與equals測試類型。由於您使用的是=和<>來測試x和z，樹數據必須支持相等（即使您沒有對值做任何有趣的事情）。這是polyEqual警告的根源。

非窮舉匹配警告更令人費解。當我將你的數據類型和函數定義粘貼到莫斯科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時會發生什麼情況：您在不考慮內容的情況下調用樹。不過，這與您所看到的警告沒有任何關係。

來源

2012-03-29 17:26:53

我使用SML/NJ我不知道是否因爲即時通訊使用它我有警告。無論如何，感謝提示我現在正在處理它謝謝邁克爾 – 2012-03-29 17:32:32

@ aizen92我沒有安裝SML/NJ，所以很不幸我無法在那裏測試它。當你認爲'if'，'andalso'和'orelse'實際上只是模式匹配的特殊情況時，SML/NJ和MosML似乎只是將'if'表達式轉化爲具有不同結構的模式匹配，只有一個其中詳盡無遺。基本結論：支持模式匹配！ – 2012-03-29 17:41:01

關於polyEqual警告：在SML/NJ此警告打印您使用該運營商每次，但這並不意味着你的代碼有問題。下面是關於它的博客文章，並在評論中有人解釋了爲什麼給出警告：http://abstractfactory.blogspot.fr/2006/05/sml-hacking-tip-turn-off-polyequal.html

來源

2012-03-29 15:32:20 Alex

好吧，但匹配非詳盡，我錯過了什麼情況？ – 2012-03-29 15:57:12

我真的不知道，我現在也沒有翻譯... – Alex 2012-03-29 16:22:11

檢查一棵樹是否完整標準ml

回答

相關問題