En informáticos lenguajes de programación , un tipo de datos recursiva (también conocido como un recursivamente definidas , inductivamente definidos o tipo de datos inductiva ) es un tipo de datos para los valores que pueden contener otros valores del mismo tipo. Los datos de tipos recursivos generalmente se ven como gráficos dirigidos .
Una aplicación importante de la recursividad en la informática es la definición de estructuras de datos dinámicas como Listas y Árboles. Las estructuras de datos recursivas pueden crecer dinámicamente hasta un tamaño arbitrariamente grande en respuesta a los requisitos de tiempo de ejecución; por el contrario, los requisitos de tamaño de una matriz estática deben establecerse en el momento de la compilación.
A veces, el término "tipo de datos inductivo" se utiliza para tipos de datos algebraicos que no son necesariamente recursivos.
Ejemplo
Un ejemplo es el tipo de lista , en Haskell :
Lista de datos a = Nulo | Contras a ( Lista a )
Esto indica que una lista de a es una lista vacía o una celda de contras que contiene una 'a' (la "cabeza" de la lista) y otra lista (la "cola").
Otro ejemplo es un tipo de enlace simple similar en Java:
clase Lista < E > { valor E ; Lista < E > siguiente ; }
Esto indica que la lista no vacía de tipo E contiene un miembro de datos de tipo E y una referencia a otro objeto List para el resto de la lista (o una referencia nula para indicar que este es el final de la lista).
Tipos de datos recursivos mutuamente
Los tipos de datos también se pueden definir mediante recursividad mutua . El ejemplo básico más importante de esto es un árbol , que se puede definir recursivamente mutuamente en términos de un bosque (una lista de árboles). Simbólicamente:
f: [t [1], ..., t [k]]t: vf
Un bosque f consta de una lista de árboles, mientras que un árbol t consta de un par de un valor v y un bosque f (sus hijos). Esta definición es elegante y fácil de trabajar de forma abstracta (como cuando se prueban teoremas sobre las propiedades de los árboles), ya que expresa un árbol en términos simples: una lista de un tipo y un par de dos tipos.
Esta definición recursiva mutua se puede convertir en una definición recursiva simple al incluir la definición de bosque:
t: v [t [1], ..., t [k]]
Un árbol t consta de un par de un valor v y una lista de árboles (sus hijos). Esta definición es más compacta, pero algo más desordenada: un árbol consta de un par de un tipo y una lista de otro, que requieren desenmarañarse para probar los resultados.
En el ML estándar , los tipos de datos de árboles y bosques se pueden definir recursivamente de la siguiente manera, lo que permite árboles vacíos: [1]
tipo de datos 'un árbol = Vacío | Nodo de 'a * ' un bosque y 'un bosque = Nil | Contras de 'un árbol * ' un bosque
En Haskell, los tipos de datos de árboles y bosques se pueden definir de manera similar:
árbol de datos a = vacío | Nodo ( a , bosque a )datos Bosque a = Nulo | Contras ( árbol a ) ( bosque a )
Teoría
En la teoría de tipos , un tipo recursivo tiene la forma general μα.T, donde la variable de tipo α puede aparecer en el tipo T y representa el tipo completo en sí.
Por ejemplo, los números naturales (consulte la aritmética de Peano ) pueden estar definidos por el tipo de datos Haskell:
datos Nat = Zero | Succ Nat
En teoría de tipos, diríamos: donde los dos brazos del tipo suma representan los constructores de datos Zero y Succ. Zero no toma argumentos (por lo tanto, representado por el tipo de unidad ) y Succ toma otro Nat (por lo tanto, otro elemento de).
Hay dos formas de tipos recursivos: los denominados tipos isorrecursivos y los tipos equirecursivos. Las dos formas difieren en cómo se introducen y eliminan los términos de un tipo recursivo.
Tipos isorecursivos
Con tipos isorrecursivos, el tipo recursivo y su expansión (o desenrollado ) (Donde la notaciónindica que todas las instancias de Z se reemplazan con Y en X) son tipos distintos (y disjuntos) con construcciones de términos especiales, generalmente llamadas roll y unroll , que forman un isomorfismo entre ellas. Para ser preciso: y , y estas dos son funciones inversas .
Tipos equirecursivos
Bajo reglas equirecursivas, un tipo recursivo y se está desenrollando son iguales , es decir, se entiende que esos dos tipos de expresiones denotan el mismo tipo. De hecho, la mayoría de las teorías de tipos equirecursivos van más allá y esencialmente especifican que dos expresiones de tipos cualesquiera con la misma "expansión infinita" son equivalentes. Como resultado de estas reglas, los tipos equirecursivos aportan significativamente más complejidad a un sistema de tipos que los tipos isorrecursivos. Los problemas algorítmicos como la verificación de tipos y la inferencia de tipos también son más difíciles para los tipos equirecursivos. Dado que la comparación directa no tiene sentido en un tipo equirecursivo, se pueden convertir a una forma canónica en tiempo O (n log n), que se puede comparar fácilmente. [2]
Los tipos equirecursivos capturan la forma de definiciones de tipos autorreferenciales (o mutuamente referenciales) que se ven en los lenguajes de programación procedimentales y orientados a objetos, y también surgen en la semántica teórica de tipos de objetos y clases . En los lenguajes de programación funcional, los tipos isorrecursivos (disfrazados de tipos de datos) son mucho más comunes.
En sinónimos de tipo
La recursividad no está permitida en sinónimos de tipo en Miranda , OCaml (a menos -rectypes
que se use una bandera o sea un registro o variante) y Haskell; por ejemplo, los siguientes tipos de Haskell son ilegales:
type Bad = ( Int , Bad ) type Evil = Bool -> Evil
En su lugar, debe estar envuelto dentro de un tipo de datos algebraicos (incluso si solo tiene un constructor):
datos Bueno = Emparejar Int Buen dato Fino = Divertido ( Bool -> Bien )
Esto se debe a que los sinónimos de tipo, como typedefs en C, se reemplazan con su definición en el momento de la compilación. (Los sinónimos de tipo no son tipos "reales"; son simplemente "alias" para conveniencia del programador). Pero si esto se intenta con un tipo recursivo, se repetirá infinitamente porque no importa cuántas veces se sustituya el alias, se refiere a sí mismo, por ejemplo, "Bad" crecerá indefinidamente: Bad
→ (Int, Bad)
→ (Int, (Int, Bad))
→ ...
.
Otra forma de verlo es que se requiere un nivel de direccionamiento indirecto (el tipo de datos algebraicos) para permitir que el sistema de tipos isorrecursivos descubra cuándo rodar y desenrollar .
Ver también
Notas
- ^ Harper 2000 , " Tipos de datos ".
- ^ "Asuntos de numeración: formas canónicas de primer orden para tipos recursivos de segundo orden". CiteSeerX 10.1.1.4.2276 . Cite journal requiere
|journal=
( ayuda )
Este artículo se basa en material extraído del Diccionario gratuito de informática en línea antes del 1 de noviembre de 2008 e incorporado bajo los términos de "renovación de licencias" de la GFDL , versión 1.3 o posterior.