Haskell Binärbaum Prädikat für genetische Sortierung

Question

Wirklich neu zu Haskell und ich kann das nicht herausfinden. Wie überprüfe ich, ob ein Node in einem gegebenen Binärbaum größer ist als seine Kinder?

module IntTree where 

data IntTree = Leaf Int 
      | Node Int IntTree IntTree 
      deriving (Eq,Show) 

t1 :: IntTree 
t1 = Node 1999 (Node 1963 (Leaf 1925) 
          (Leaf 1933)) 
       (Node 1956 (Leaf 1932) 
          (Leaf 1924)) 


t2 :: IntTree 
t2 = Node 1999 (Node 1922 (Leaf 1925) 
          (Leaf 1933)) 
       (Node 1956 (Leaf 1932) 
          (Leaf 1924)) 

descendingTree :: Ord a => IntTree -> Bool 

Die Funktion descendingTree, die ein IntTree bekommen und gibt mir einen Booleschen im Gegenzug, Signalisierung, ob es für jeden Knoten im Baum, dass der Knoten Wert ist größer als seine beiden Kinder Knoten Werte wahr ist; wenn es natürlich Kinder hat. Wie kann ich diese Funktion schreiben?

Answer 1

Die Antwort lautet: langsamdurch direkt Ihre Datentypdefinition folgen.

descendingTree :: IntTree -> Bool  -- no `a`, so no `Ord a` too 
-- data IntTree = Leaf Int 
descendingTree (Leaf i) = leaf i 
--    | Node Int IntTree IntTree 
descendingTree (Node i  lt  rt ) = node i lt rt 

Im Fall ist es ein Blatt, es gibt nichts zu überprüfen:

leaf _ = True 

Im Fall ist es ein Knoten, es immer hat zwei Kinder; Dies wird durch seine Typdefinition gewährleistet. Es gibt einfach keine andere Möglichkeit in dem Typ.

node i lt rt = 

Hier müssen Sie Ihren Test ausfüllen:

 i > value lt && 
     i > value rt && 

die beiden Prüfungen werden durchgeführt werden; Wenn ein Fehler auftritt, schlägt der gesamte Ausdruck && fehl und gibt False zurück. Gut. Was ist, wenn die beiden Tests erfolgreich sind?

 every_node_is_greater .... && 
     every_node_is_greater .... 

Können Sie die Lücken ausfüllen?

Können Sie die Definition für every_node_is_greater schreiben? Musst du?

Natürlich sind die beiden Funktionen leaf und node komplett redundant; sie dienten nur als mentale Trittsteine ​​hier, um den Schreibblock für uns zu entfernen. :) Normalerweise schreiben Sie den Code direkt in die entsprechende Klausel in der descendingTree Definition.

Eine weitere Definition muss hier geschrieben werden, für value, die neue Abstraktion, die wir eingeführt haben, wie wir das Problem Raum erforschten („was passiert, wenn wir einen Weg hatte die wissen,‚Wert‘eines Knotens? Wir werden uns später mit den Einzelheiten befassen ... "). Jetzt ist es endlich an der Zeit, es zu konkretisieren. Wieder folge einfach (und langsam) dem Typ und handle mit den Fällen, die er präsentiert.