überprüfen, ob ein Baum vollständig ist Standard ml

Question

Ich möchte eine Funktion in Standard ml, die überprüft, ob ein Baum abgeschlossen ist oder nicht, funktioniert die Funktion irgendwie funktioniert, aber es gibt mir den falschen Typ und eine Warnung von nicht erschöpfenden Fällen

der Baum Code:

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; 

nun den Typ der obigen Funktion ist: ''a tree -> bool aber die erforderliche Typ ist 'a tree -> bool

die Warnung I ist mit bin:

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) => ... 

Was ist das Problem, das ich habe?

EDIT:

Dank Michael, fest ich den Code und jetzt funktioniert es:

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

Answer 1

Der ''a tree -> bool Typ gibt an, dass a eine Gleichheit Art: es muss ein Typ sein, den Test mit equals unterstützt. Da Sie = und <> verwenden, um x und z zu testen, müssen die Baumdaten die Gleichheit unterstützen (auch wenn Sie mit den Werten nichts Interessantes tun). Dies ist die Wurzel der polyEqual Warnung.

Die nicht erschöpfende Übereinstimmung Warnung ist rätselhafter. Wenn ich Ihre Datentyp- und Funktionsdefinitionen in Moskau ML einfüge, bekomme ich nicht eine Warnung erhalten. Ich glaube nicht, dass ich mir zu viele Gedanken darüber machen würde, da ich davon ausgehe, dass ich den Typ reparieren würde, um mich auch um die Warnung zu kümmern.

Um den gewünschten Typ 'a tree -> bool zu erhalten, würde ich empfehlen, die if zugunsten der Mustererkennung loszuwerden. Zum Beispiel:

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

Ich überlasse es Ihnen, die ganze Reihe von Fällen herauszufinden, da dies wie Hausaufgaben aussieht.

Übrigens glaube ich nicht, dass Ihr Test für die Vollständigkeit korrekt ist. Überlegen Sie, was passiert, wenn keiner der Unterzweige EMPTY lautet: Sie rufen den Baum vollständig auf, ohne den Inhalt zu berücksichtigen. Dies hat jedoch nichts mit den Warnungen zu tun, die Sie sehen.

Answer 2

bezüglich der polyEqual Warnung: in SML/NJ diese Warnung jedes Mal wenn Sie diesen Operator verwenden gedruckt wird, aber Das bedeutet nicht, dass Ihr Code fehlerhaft ist. Hier ist eine Blog-Post über sie, und in den Kommentaren jemand erklärt, warum die Warnung gegeben: http://abstractfactory.blogspot.fr/2006/05/sml-hacking-tip-turn-off-polyequal.html