einen Wert in einer geordneten Struktur in Haskell Einfügen

Question

Im Prinzip habe ich einen Baum-Datentyp definiert ist, die wie folgt definiert ist:

data Tree a = Empty 
| Leaf a 
| Node (Tree a) a (Tree a) 
deriving (Eq, Ord, Show) 

nun eine Funktion I haben zu schaffen, einen Wert in einer geordneten Baum einzufügen (it muss den Baum nicht sortieren, addiere einfach den Wert). Dies ist, was ich mit so weit habe kommen:

insert :: a -> Tree a -> Tree a 
insert x Empty  = Leaf x 
insert x (Leaf m) | m < x  = Node (Leaf x) m Empty 
        | otherwise = Node Empty m (Leaf x) 
insert x (Node l m r) | x > m  = Node (Leaf l) m (insert x r) 
         | otherwise = Node (insert x l) m (Leaf r) 

Allerdings, wenn ich diese laufen bekomme ich folgende Fehlermeldung:

nicht Typ Könnte übereinstimmen erwartet ‚a‘ (ein starres Variable) gegen abgeleitete Art 'Baum a' 'a' ist durch die Typ Unterschrift für 'einfügen' bei Main.hs: 11: 10 Im ersten Argument von 'Leaf', nämlich 'l' In der ersten Argument von 'Knoten', nämlich '(Blatt 1)' In dem Ausdruck: Knoten (Blatt l) m (Einfügen xr)

Ich nehme an, es ist etwas mit Typen zu tun, aber ich kann nicht sehen, wo ich irgendwelche Typen, die nicht da sein sollte, gesetzt habe.

Answer 1

grob aus Übersetzen ins Englische Art-checker-ese:

nicht 'a' (a starre Variable)

Das bedeutet, dass es erwartete einen beliebigen erwarteten Typ Könnte übereinstimmen Geben Sie a, das ist auch anderswo verwendet (daher "starr"), so dass es nicht jeden alten Typ nehmen kann.

gegen abgeleiteten Typen ‚Baum a‘

Das bedeutet, dass, statt sie ein Tree enthaltenden Elemente des erwarteten starren polymorphen Typs gefunden. Dies macht offensichtlich keinen Sinn, so beschwert es sich.

'a' ist an die Typ-Signatur für 'insert' bei Main gebunden.hs: 11: 10

Dies sagt nur, dass der Typ eingeschränkt ist, weil Sie es in dieser Typ-Signatur angegeben haben.

im ersten Argumente von 'Leaf', nämlich 'l' in dem ersten Argumente des 'Knoten', nämlich '(Blatt l)' In dem Ausdruck: Knoten (Blatt-L) m (insert xr)

Dies ist nur sagen Sie, welchen spezifischen Begriff es beschwert, mit einigen Kontext.

Also, Dinge zu sortieren: Die Variable l ist eine Tree a wird in einem Kontext verwendet, die nur a benötigt. In diesem Fall hat l offensichtlich den richtigen Typ, so ist der Fehler in wie es verwendet wird. Warum suchte der Typ-Checker nach Typ a? Weil Sie einen Tree Datenkonstruktor darauf angewendet haben. Aber warten Sie, l ist bereits ein Tree a! et voila, die Skalen fallen aus unseren Augen und die Wahrheit wird geschaut.

... das war alles nur ein langwieriger Weg zu erklären, warum Edward Kmett ist schnell Zieh Antwort richtig ist, und welche Art von Argumentation man verwenden könnte auf eine solche Antwort zu gelangen.

Answer 2

Ihr Problem ist, dass

insert x (Node l m r) | x > m  = Node (Leaf l) m (insert x r) 
         | otherwise = Node (insert x l) m (Leaf r) 

wahrscheinlich

insert x (Node l m r) | x > m  = Node l m (insert x r) 
         | otherwise = Node (insert x l) m r 

weil l und r sind bereits Bäume sein sollte.

Answer 3

l ist der erste Parameter von Node und so ist es vom Typ Tree a (der gesamte linke Teilbaum). Leaf dagegen nimmt nur einen einzelnen Wert als Parameter, nicht einen ganzen Baum. Daher gibt Leaf l einen Typfehler, da es versucht, ein Blatt aus einem ganzen Baum zu machen. Wahrscheinlich wollten Sie einfach l anstelle von Leaf l an diesem Ort.

Was ist der Unterschied zwischen Leaf x und Node Empty x Empty? Sind Sie sicher, dass Sie beide Konstruktoren benötigen?