Tipo de datos recursivo

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

En los lenguajes de programación informática , 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 suelen considerarse como gráficos dirigidos ^{[ cita requerida ]} .

Una aplicación importante de la recursión 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 alcanzar un tamaño arbitrario 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 se utiliza el término "tipo de datos inductivo" para tipos de datos algebraicos que no son necesariamente recursivos.

Ejemplo

Un ejemplo es el tipo de lista , en Haskell :

datos Lista a = Nil | Cons a ( Lista a )         

Esto indica que una lista de a es una lista vacía o una celda cons que contiene una 'a' (la "cabeza" de la lista) y otra lista (la "cola").

Otro ejemplo es un tipo enlazado simple similar en Java:

clase  Lista < E > { E valor ; 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 recursión mutua . El ejemplo básico más importante de esto es un árbol , que se puede definir de forma recursiva mutua en términos de un bosque (una lista de árboles). Simbólicamente:

f: [t[1], ..., t[k]]t: vf

Un bosque f consiste en una lista de árboles, mientras que un árbol t consiste en un par de valores v y un bosque f (sus hijos). Esta definición es elegante y fácil de usar de manera abstracta (por ejemplo, al demostrar 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 recursiva mutua se puede convertir en una definición recursiva simple incorporando en línea la definición de un bosque:

t: v [t[1], ..., t[k]]

Un árbol t consiste en un par de valores v y una lista de árboles (sus hijos). Esta definición es más compacta, pero algo más confusa: un árbol consiste en 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 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 árbol y bosque se pueden definir de manera similar:

Árbol de datos a = Vacío | Nodo ( a , Bosque a )         datos Bosque a = Nil | Cons ( Á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.

Por ejemplo, los números naturales (ver aritmética de Peano ) pueden definirse mediante el tipo de datos 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, se representa mediante 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 }$

Existen dos formas de tipos recursivos: los denominados tipos isorrecursivos y los tipos equirrecursivos. Las dos formas difieren en cómo se introducen y eliminan los términos de un tipo recursivo.

Tipos isorecursivos

En el caso de 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 llamadas roll y unroll , que forman un isomorfismo entre ellos. Para ser precisos: y , y estos 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

Según las reglas de los tipos equirrecursivos, 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 equirrecursivos van más allá y básicamente especifican que dos expresiones de tipo cualesquiera con la misma "expansión infinita" son equivalentes. Como resultado de estas reglas, los tipos equirrecursivos aportan significativamente más complejidad a un sistema de tipos que los tipos isorecursivos. Los problemas algorítmicos como la comprobación de tipos y la inferencia de tipos también son más difíciles para los tipos equirrecursivos. Dado que la comparación directa no tiene sentido en un tipo equirrecursivo, 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 isorecursivos capturan la forma de definiciones de tipos autorreferenciales (o mutuamente referenciales) que se ven en lenguajes de programación nominal orientados a objetos , y también surgen en la semántica de teoría de tipos de objetos y clases . En los lenguajes de programación funcional, los tipos isorecursivos (disfrazados de tipos de datos) también son comunes. ^[3]

Sinónimos de tipo recursivo

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

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

Sin embargo, la recursión no está permitida en sinónimos de tipos en Miranda , OCaml (a menos que -rectypesse use un indicador o sea un registro o variante) o Haskell; por lo que, por ejemplo, los siguientes tipos de Haskell son ilegales:

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

En lugar de ello, deben estar envueltos dentro de un tipo de datos algebraicos (incluso si solo tienen un constructor):

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

Esto se debe a que los sinónimos de tipo, como las definiciones de tipo 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 solo "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, todavía 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 indirección (el tipo de datos algebraicos) para permitir que el sistema de tipo isorrecursivo determine cuándo rodar y desenrollar .

Véase 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 la subtipificación isorecursiva | 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