2017-09-27 16 views
1

Ich habe diese Implementierung eines binären Suchbaum in HaskellGHCI Endlosschleife in binärer Suchbaum

data BST = Nil | Node (BST) Int (BST) deriving Show 

emptyTree :: BST 
emptyTree = Nil 

isEmptyTree :: BST -> Bool 
isEmptyTree Nil = True 
isEmptyTree _ = False 

leftChild :: BST -> BST 
leftChild Nil = Nil 
leftChild (Node l k r) = l 

rightChild :: BST -> BST 
rightChild Nil = Nil 
rightChild (Node l k r) = r 

root :: BST -> Int 
root Nil = error "Empty Tree" 
root (Node l k r) = k 

insert_r :: BST -> Int -> BST 
insert_r Nil k = Node Nil k Nil 
insert_r [email protected](Node l x r) k 
    | k < x = Node (insert_r l k) x r 
    | k > x = Node l x (insert_r r k) 
    | otherwise = n 

Ich versuche, es zu testen, einige Werte in den Baum eingefügt wird. Dies ist ein Beispiel Prüfablauf:

t = Nil 
t = insert_r t 2 
t = insert_r t 3 
t = insert_r t 1 

Wenn ich versuche, dies in GHCi zu laufen, zur Zeit „t“ Wert zu prüfen, erhalte ich eine Endlosschleife. Wenn ich jedoch das Ergebnis jeder Einfügung einer neuen Variablen zuweisen, wie folgt aus:

v = insert_r t 2 
u = insert_r v 1 

den Wert von „u“ Überprüfung funktioniert perfekt. Hat das mit Haskells fauler Bewertung zu tun, oder bin ich etwas falsch in der BST-Implementierung?

Antwort

7

All diese Dinge über Ihren Baum ist ganz unabhängig von der Ursache hier, dass Haskells = ist kein Zuweisungsoperator, sondern eine Definition. Wichtig ist, dass eine Rekursion möglich ist, die es einem Wert erlaubt, sich auf sich selbst zu beziehen, zum Beispiel xs = 1 : xs, was eine unendliche Liste von 1s ergibt.

Sie bauen also nicht inkrementell einen Baum über drei Insertionen auf, sondern definieren drei nicht verwandte Bäume, die jeweils selbstreferenziell und daher kreisförmig sind. Sie hätten das gleiche Problem, wenn Sie einfach x = x geschrieben haben.

Wenn Sie Schritte in einer Berechnung benennen möchten, müssen Sie jedem einen anderen Namen geben, da Sie vorhandene Bindungen nicht ändern können.