Wie schreibe ich BST Suchfunktion in Standard ML?

Question

Erforderlich ist es, eine Funktion searchBST vom Typ ''a tree -> (''a * ''a -> bool) -> ''a -> bool zu schreiben, die ein nst nach einem gegebenen Datenelement durchsucht. Verwendung:

datatype 'data tree = Empty 
        | Node of 'data tree * 'data * 'data tree 

Auch wir nicht jeden Knoten im Baum suchen, sondern nur diejenigen Knoten, die gemäß der Definition, könnte das Element enthalten die wir suchen.

Die Funktion, die I-Typ ist von (int * int tree -> bool) schrieb, und ich würde irgendwelche Tipps schätzen darauf in den erforderlichen Typ

datatype 'data tree = Empty 
        | Node of 'data tree * 'data * 'data tree; 

fun searchBST (x, Empty) = false 
    | searchBST (x, Node(l, parent, r)) = 
     if x = parent then true 
     else 
     if x< parent then searchBST(x, l) 
     else searchBST(x,r) 

Answer 1

Ihr fehlen diesen Teil in Ihrem Code "(‚‘a *‚‘eine Umwandlung -> bool) "nimm es in Betracht, arbeite an den Tupeln, dann würde dein Code funktionieren. Die zwei "a" sind das Element, nach dem Sie suchen, und das Element vom Knoten.

Answer 2

Wenn etwas den Typ ''a * ''a -> bool hat, dann ist es immer (99,9% der Fälle) eine Prädikatfunktion. Dies wird stark durch die Tatsache angedeutet, dass das Argument Tupel ''a * ''a ein Gleichheitstyp ist (daher die Doppelmarkierung und keine einzelne Markierung als "normal").

Da Sie eine Suchfunktion erstellen, ist Ihre Prädikatfunktion am ehesten diejenige, die verwendet werden sollte, um zu definieren, nach welchem ​​Element Sie suchen. Es könnte jedoch auch der Fall sein, dass definiert wird, ob sich das gewünschte Element im linken oder rechten Teil des Baums befindet. Normalerweise wäre es dann aber eine Bestellfunktion mit dem Typ ''a * ''a -> order gewesen. Solch eine Ordnungsfunktion wäre in jedem praktischen Fall besser gewesen, weil Sie dann in der Lage wären, die Reihenfolge der Elemente (die Gleichheit einschließen) anstatt der harten Codierung a kleiner als zu abstrahieren, was dann Ihre Funktion dazu zwingen würde, nur an Ganzzahlen zu arbeiten (es sei denn, Sie geben anotate zu einem anderen Zahlentyp wie reals) statt ''a (Gleichheit) ein.

So was Sie wan't (um die gewünschte Art zu bekommen), etwas von der Form ist:

fun searchBST t p x = 

wo t der Baum ist, p ist Ihre Prädikatfunktion und x ist der Wert, den Sie ‚wan t zu finden. Was Sie eigentlich vermissen, ist die Verwendung der Prädikatfunktion im Test, anstatt sie direkt zu tun.

fun searchBST Empty _ _ = false 
    | searchBST (Node(l, d, r)) p x = 
    case (p(x, d), x < d) of 
     (true, _) => true 
     | (_, true) => searchBST l p x 
     | (_, false) => searchBST r p x