Inserimento di un valore in un albero ordinato in Haskell

Question

Fondamentalmente ho definito un tipo di dati albero che è definito come segue:

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

ora devo creare una funzione per inserire un valore in un albero ordinato (si non ha bisogno di ordinare l'albero, basta aggiungere il valore). Questo è ciò che mi è venuta in mente finora:

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) 

Tuttavia, quando ho eseguito questo ottengo il seguente messaggio di errore:

non poteva competere con tipo 'a' (una rigida previsto variabile) in base al tipo inferito 'Albero a' 'a' è associato alla firma del tipo per 'insert' in Main.hs: 11: 10 Nel primo argomento di 'Leaf', ovvero 'l' Nel primo argomento di 'Nodo', ovvero '(Leaf l)' Nell'espressione: Nodo (Leaf l) m (insert xr)

Suppongo che sia qualcosa a che fare con i tipi ma non riesco a vedere dove ho messo nessun tipo che non dovrebbe essere lì.

Answer 1

Traducendo approssimativamente da tipo-checker-ese in inglese:

potrebbe non corrispondere previsto tipo 'a' (una variabile rigida)

Ciò significa che si aspettava un arbitrario digitare a, che viene utilizzato anche altrove (quindi "rigido") in modo che non possa prendere qualsiasi vecchio tipo.

contro tipo derivato 'albero un'

Ciò significa che invece ha trovato un Tree contenenti elementi del tipo polimorfico rigido previsto. Questo ovviamente non ha senso, quindi si lamenta.

'a' è associato alla firma del tipo per 'inserire' in Principale.hs: 11: 10

Questo dice solo che il tipo è limitato perché lo hai specificato in quel tipo di firma.

Nel primo argomento di 'Leaf', cioè 'l' Nella prima argomento 'Node', cioè '(Foglia l)' Nell'espressione: Node (Foglio l) m (inserto xr)

Questo è solo per dirvi con quale termine specifico ci si lamenta, con qualche contesto.

Quindi, per sistemare le cose: la variabile l è una Tree a utilizzata in un contesto che richiede solo a. In questo caso, l ha ovviamente il tipo corretto, quindi l'errore è in che modo viene utilizzato. Perché il type checker cercava il tipo a? Perché hai applicato un costruttore di dati Tree. Ma aspetta, lo l è già un Tree a! et voilà, le scaglie cadono dai nostri occhi e la verità è vista.

... che era tutto solo un lungo cammino di spiegare perché risposta rapida-draw Edward Kmett s' è corretto, e che tipo di ragionamento si potrebbe utilizzare per arrivare a una tale risposta.

Answer 2

tuo problema è che

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

dovrebbe probabilmente essere

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

perché l e r sono già Alberi.

Answer 3

l è il primo parametro di Node e quindi è di tipo Tree a (l'intero sottoalbero di sinistra). Leaf d'altra parte prende solo un singolo valore come parametro, non un intero albero. Pertanto Leaf l restituisce un errore di tipo, poiché tenta di creare una foglia da un intero albero. Probabilmente volevi semplicemente l invece di Leaf l in questo posto.

Inoltre, qual è la differenza tra Leaf x e Node Empty x Empty? Sei sicuro di aver bisogno di entrambi i costruttori?