Tipo de datos recursivo

Tipo de datos que hace referencia a sí mismo en su definición.

En los lenguajes de programación de computadoras , un tipo de datos recursivo (también conocido como tipo de datos definido recursivamente , definido inductivamente o inductivo ) es un tipo de datos para valores que pueden contener otros valores del mismo tipo. Los datos de tipos recursivos generalmente se ven como gráficos dirigidos ^{[ cita requerida ]} .

Una aplicación importante de la recursividad en 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 del tiempo de ejecución; por el contrario, los requisitos de tamaño de una matriz estática se deben establecer 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 lista , en Haskell :

Lista de datos a = Nil | Contras a ( Listar 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 similar de enlace simple en Java:

 Lista de clase <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 Lista para el resto de la lista (o una referencia nula para indicar que este es el final de la lista).

Tipos de datos mutuamente recursivos

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 de forma recursiva entre sí 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 demuestran teoremas sobre propiedades de árboles), ya que expresa un árbol en términos simples: una lista de un tipo y un par de dos tipos.

Esta definición mutuamente recursiva se puede convertir en una definición recursiva individualmente insertando la definición de un 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 confusa: un árbol consta de un par de un tipo y una lista de otro, que requieren desenredarse para demostrar resultados.

En Standard ML , los tipos de datos de árbol y bosque se pueden definir mutuamente de forma recursiva de la siguiente manera, permitiendo árboles vacíos: ^[1]

tipo de datos  'un  árbol  =  Vacío  |  Nodo  de  'a  *  'a  bosque y  'a  bosque  =  Nil  |  Contras  de  'un  arbol  *  'un  bosque

En Haskell, los tipos de datos de árbol y bosque se pueden definir de manera similar:

Árbol de datos a = Vacío | Nodo ( a , bosque a )         datos Bosque a = Nil | Contras ( Árbol a ) ( Bosque a )          

Teoría

En 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.

Por ejemplo, los números naturales (ver Aritmética de Peano ) pueden definirse mediante el tipo de datos de Haskell:

datos Nat = Cero | 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 ). ${\displaystyle nat=\mu \alpha .1+\alpha }$ ${\displaystyle \mu \alpha .1+\alpha }$

Hay dos formas de tipos recursivos: los llamados tipos isorrecursivos y tipos equicursivos. Las dos formas difieren en cómo se introducen y eliminan los términos de tipo recursivo.

Tipos isorrecursivos

Con los tipos isorrecursivos, el tipo recursivo y su expansión (o desenrollado ) (donde la notación indica que todas las instancias de Z se reemplazan con Y en X) son tipos distintos (y disjuntos) con construcciones de términos especiales, generalmente llamados roll y unroll , que forman un isomorfismo entre ellos. Para ser precisos: y , y estas dos son funciones inversas . ${\displaystyle \mu \alpha .T}$ ${\displaystyle T[\mu \alpha .T/\alpha ]}$ ${\displaystyle X[Y/Z]}$ ${\displaystyle roll:T[\mu \alpha .T/\alpha ]\to \mu \alpha .T}$ ${\displaystyle unroll:\mu \alpha .T\to T[\mu \alpha .T/\alpha ]}$

Tipos equirecursivos

Bajo reglas equicursivas, un tipo recursivo y su desarrollo son iguales ; es decir, se entiende que esas dos expresiones de tipo denotan el mismo tipo. De hecho, la mayoría de las teorías de tipos equicursivos van más allá y esencialmente especifican que dos expresiones de tipo cualesquiera con la misma "expansión infinita" son equivalentes. Como resultado de estas reglas, los tipos equicursivos 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 equicursivos. Dado que la comparación directa no tiene sentido en un tipo equicursivo, se pueden convertir a una forma canónica en tiempo O (n log n), que se puede comparar fácilmente. ^[2] ${\displaystyle \mu \alpha .T}$ ${\displaystyle T[\mu \alpha .T/\alpha ]}$

Los tipos isorrecursivos capturan la forma de definiciones de tipos autorreferenciales (o mutuamente referenciales) que se ven en los lenguajes de programación nominales 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 funcionales, los tipos isorecursivos (en forma de tipos de datos) también son comunes. ^[3]

Sinónimos de tipo recursivo

En TypeScript , se permite la recursividad en los alias de tipo. ^[4] Por lo tanto, se permite el siguiente ejemplo.

tipo Árbol = número | Árbol []; let árbol : Árbol = [ 1 , [ 2 , 3 ]];           

Sin embargo, la recursividad no está permitida en sinónimos de tipo en Miranda , OCaml (a menos que -rectypesse use una bandera o sea un registro o variante) o Haskell; así, por ejemplo, los siguientes tipos de Haskell son ilegales:

tipo Malo = ( Int , Malo ) tipo Malo = Bool -> Malo         

En cambio, deben estar incluidos dentro de un tipo de datos algebraico (incluso si solo tienen un constructor):

datos Bueno = Par Int Bueno datos Bien = Diversión ( Bool -> Bien )           

Esto se debe a que los sinónimos de tipos, 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 comodidad del programador). Pero si esto se intenta con un tipo recursivo, se repetirá infinitamente porque no importa cuántas veces se sustituya el alias, todavía se refiere a sí mismo, por ejemplo, "Malo" 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 tipo isorrecursivo determine cuándo rodar y desenrollar .

Ver también

• Definición recursiva
• tipo de datos algebraicos
• tipo inductivo
• Nodo (informática)

Referencias

1. Harper 1998.
2. "La numeración importa: formas canónicas de primer orden para tipos recursivos de segundo orden". CiteSeerX 10.1.1.4.2276 . 
3. Revisando los subtipos isorrecursivos | Actas de la ACM sobre lenguajes de programación
4. (Más) Alias ​​de tipos recursivos: anuncio de TypeScript 3.7 - TypeScript

Fuentes

• Harper, Robert (1998), Declaraciones de tipos de datos, archivado desde el original el 1 de octubre de 1999