Creación de tipos recursivos polimórficos en Haskell

Question

Estoy intentando crear un tipo de árbol en Haskell. He utilizado este constructor de datos simple para almacenar un árbol en el que cada nodo puede estar vacío, ser una hoja que contenga un número entero o ser un nodo que contenga un número entero con ramas a otras dos hojas/nodos. Esto es lo que tengo:

module Tree (Tree(Empty, Leaf, Node)) where 

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

que funciona bien, pero necesito hacer el tipo de árbol polimórfica. Intenté simplemente reemplazar 'Int' por 'a', pero parece que no funciona. ¿Hay algún otro sistema para hacer estos tipos polimórficos?

Answer 1

De hecho, puede darle al árbol un parámetro de tipo, como en el ejemplo de Alexander Poluektov. ¡Suficientemente simple! Pero ¿por qué detenerse allí? Podemos divertirnos un poco más que eso. En lugar de solo una estructura recursiva con datos polimórficos , puede hacer que la estructura sea polimórfica en la recursión misma!

En primer lugar, abstraiga las referencias del árbol a sí mismo, de la misma manera que abstraer las referencias a Int, reemplazando las referencias recursivas con un nuevo parámetro t. Eso nos deja con esta estructura de datos bastante vagos:

data TNode t a = Empty 
       | Leaf a 
       | Node (t a) a (t a) 
       deriving (Eq, Ord, Show, Read) 

Esto ha sido renombrada como TNode aquí porque no es realmente un árbol más; solo un tipo de datos simple. Ahora, para recuperar la recursividad original y crear un árbol, torcemos TNode alrededor y alimentar a sí mismo:

newtype Tree a = Tree (TNode Tree a) deriving (Eq, Ord, Show, Read) 

Ahora podemos utilizar este Tree de forma recursiva, aunque por desgracia a costa de cierta verborrea adicional, así:

Tree (Node (Tree Empty) 5 (Tree (Leaf 2))) 

Entonces, ¿qué nos da esto, además de escribir extra, usted pregunta? Simplemente que hemos separado la estructura del árbol fundamental tanto de los datos que contiene como del método por el cual se construyen y procesan los datos, lo que nos permite escribir funciones más genéricas para tratar con un aspecto u otro.

Por ejemplo, podemos decorar árboles con datos adicionales o empalmar materiales adicionales en el árbol, sin afectar las funciones de árbol genéricas.Decimos que queríamos dar un nombre a cada pieza del árbol:

newtype NameTree a = NameTree (String, TNode NameTree a) deriving (Eq, Ord, Show, Read) 

Por otro lado, podemos escribir genérica lógica recorrido del árbol:

toList f t = toList' f (f t) [] 
    where toList' f (Node t1 x t2) xs = toList' f (f t1) (x : toList' f (f t2) xs) 
      toList' f (Leaf x) xs = x:xs 
      toList' _ Empty xs = xs 

Dada una función para extraer la corriente TNode de un árbol recursivo, podemos utilizar esto en cualquier estructura:

treeToList = toList (\(Tree t) -> t) 
nameTreeToList = toList (\(NameTree (_, t)) -> t) 

por supuesto, esto probablemente va mucho más allá de lo que está buscando hacer, pero es un buen sabor de lo mucho polimorfismo y el código genérico Haskell permite (más aún, fomenta) que un programador cree.

Answer 2

data Tree a = Empty 
      | Leaf a 
      | Node (Tree a) a (Tree a) 

Answer 3

Sustitución Int con un es un buen comienzo, pero también es necesario para reemplazar cada aparición del Árbol con Tree a (parenthesizing en caso necesario). La parte data Tree necesita a para declarar que Tree tiene un argumento de tipo llamado a. El Node Tree Int Tree necesita significar que los subárboles son ellos mismos del tipo Tree a y no otro tipo de treetype.

Answer 4

tratar de leer un poco acerca de constructor de tipo tipo.

Si usted tiene un tipo polimórfico en función de algunas variables de tipo, entonces su tipo constructor debe tener un tipo que lo refleja.

Por ejemplo, el constructor de tipo MyBool define en:

data MyBool = False | True 

es de tipo *. Es decir, mi constructor de tipos MyBool no toma parámetros para definir un tipo. Si escribo algo como:

data MyMaybe a = Just a | Nothing 

entonces el constructor de tipo MyMaybe tiene *->* tipo, es decir, se necesita un "argumento de tipo" para definir un tipo.

Puede comparar el tipo de tipos de constructores con el funcionamiento del tipo de constructor de datos.

El constructor de datos True puede ser un valor de datos del tipo MyBool por sí mismo, sin ningún parámetro. Sin embargo, el constructor de datos Just es un valor de tipo a -> MyMaybe a, se operar más de un valor de tipo A para crear otro valor de tipo MyMaybe a - como por ejemplo en esta sesión ghci:

> let x = Just 5 
> :t x 
Maybe Int 
> let y = Just 
> :t y 
a -> Maybe a 

Esto es más o menos comparable con la diferencia entre los constructores de tipo MyMaybe y MyBool. Teniendo en cuenta que tienen MyBool tipo *, puede tener valores con el tipo MyBool, sin ningún tipo de parámetro adicional. Pero MyMaybe no es un tipo de por sí - es un constructor de tipos que "funciona" en un tipo para crear otro tipo, es decir, su tipo es * -> *. Y así, no se puede tener cosas del tipo MyMaybe, pero las cosas de tipo MyMaybe Int, MyMaybe Bool, MyMaybe [Int], etc ...

Si un tipo es polimórfico, que tiene que ser al menos de tipo * -> *, pero podría *->*->* ser, como en:

data MyPair a b = Pair a b 

MyPair necesita dos parámetros de tipo para definir un tipo, al igual que en MyPair Int Bool, MyPair Int Int, etc ...hogar del mensaje

La toma es algo así como: como constructores de datos tienen las firmas de tipos, constructores de tipos tienen firmas especie, y esto debe ser tenido en cuenta cuando se planea un nuevo tipo de datos.

http://en.wikipedia.org/wiki/Kind_%28type_theory%29