Inserción de un valor en un árbol ordenado en Haskell

Question

Básicamente he definido un tipo de datos de árbol que se define de la siguiente manera:

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

ahora tengo que crear una función para insertar un valor en un árbol ordenado (que no tiene que ordenar el árbol, solo agrega el valor). Esto es lo que he encontrado hasta el momento:

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) 

Sin embargo, cuando ejecuto este me sale el siguiente mensaje de error:

no pudo igualar esperada tipo 'A' (una rígida variable) contra el tipo inferido 'Árbol a' 'a' está vinculado por la firma de tipo para 'insertar' en Main.hs: 11: 10 En el primer argumento de 'Leaf', concretamente 'l' En la primera argumento de 'nodo', a saber '(Leaf l)' En la expresión: nodo (Leaf l) m (inserto xr)

supongo que es algo que ver con los tipos, pero no puedo ver dónde he puesto ningún tipo que no deberían estar allí.

Answer 1

La traducción más o menos de tipo ortográfico-ESE en Inglés:

no pudo igualar esperada tipo 'A' (una variable rígida)

Esto significa que se espera una arbitraria tipo a, que también se usa en otros lugares (por lo tanto, "rígido") por lo que no puede simplemente tomar cualquier tipo antiguo.

contra el tipo inferido 'Tree un'

Esto significa que en lugar encontró un Tree elementos que contienen del tipo polimórfico rígido esperado. Obviamente, esto no tiene sentido, por lo que se queja.

'a' está vinculado por el tipo de firma para 'insertar' en Main.hs: 11: 10

Esto solo indica que el tipo está siendo restringido porque usted lo especificó en ese tipo de firma.

en el primer argumento de 'hoja', es decir, 'L' en la primera argumento de 'nodo', a saber '(Leaf l)' En la expresión: Nodo (Leaf l) m (inserto xr)

Esto simplemente le dice de qué término específico se está quejando, con algún contexto.

Por lo tanto, para resolver las cosas: La variable l es un Tree a que se utiliza en un contexto que solo necesita a. En este caso, l obviamente tiene el tipo correcto, por lo que el error está en cómo se usa. ¿Por qué el verificador de tipos buscaba el tipo a? Porque le aplicaste un constructor de datos Tree. Pero espera, l ya es un Tree a! et voila, las escamas caen de nuestros ojos y se ve la verdad.

... que fue toda una forma larga de explicar por qué Edward Kmett tiene una respuesta rápida, y qué tipo de razonamiento se podría usar para llegar a tal respuesta.

Answer 2

Su problema es que

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

probablemente debería ser

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

porque l y r ya son árboles.

Answer 3

l es el primer parámetro de Node y, por lo tanto, es del tipo Tree a (todo el subárbol izquierdo). Leaf, por otro lado, solo toma un valor único como parámetro, no un árbol completo. Por lo tanto, Leaf l da un error de tipo, ya que trata de hacer que una hoja salga de un árbol completo. Probablemente simplemente quería l en lugar de Leaf l en este lugar.

Además, ¿cuál es la diferencia entre Leaf x y Node Empty x Empty? ¿Estás seguro de que necesitas ambos constructores?