Unión etiquetada

En informática, una unión etiquetada, también llamada variante, registro de variante, tipo de elección, unión discriminada, unión disjunta, tipo de suma o coproducto, es una estructura de datos utilizada para contener un valor que podría adoptar varios tipos diferentes, pero fijos. Solo uno de los tipos puede estar en uso a la vez y un campo etiqueta indica explícitamente cuál está en uso. Se puede considerar como un tipo que tiene varios "casos", cada uno de los cuales debe manejarse correctamente cuando se manipula ese tipo. Esto es fundamental para definir tipos de datos recursivos, en los que algún componente de un valor puede tener el mismo tipo que ese valor, por ejemplo, al definir un tipo para representar árboles, donde es necesario distinguir subárboles y hojas de múltiples nodos. Al igual que las uniones ordinarias, las uniones etiquetadas pueden ahorrar almacenamiento al superponer áreas de almacenamiento para cada tipo, ya que solo se utiliza una a la vez.

Descripción

Las uniones etiquetadas son más importantes en lenguajes de programación funcionales como ML y Haskell, donde se denominan tipos de datos (ver tipo de datos algebraicos) y el compilador puede verificar que todos los casos de una unión etiquetada son siempre manejados, evitando muchos tipos de errores. Sin embargo, pueden construirse en casi cualquier lenguaje de programación y son mucho más seguras que las uniones sin etiquetar, a menudo llamadas simplemente uniones, que son similares pero no rastrean explícitamente qué miembro de una unión está en uso actualmente.

Las uniones etiquetadas suelen ir acompañadas del concepto de constructor de tipos, que es similar, pero no igual, a un constructor de una clase. Los constructores de tipos producen un tipo de unión etiquetado, dado el tipo de etiqueta inicial y el tipo correspondiente.

Matemáticamente, las uniones etiquetadas corresponden a uniones disjuntas o uniones discriminadas, normalmente escritas con +. Dado un elemento de una unión disjunta A + B, es posible determinar si proviene de A o de B >. Si un elemento se encuentra en ambos, habrá dos copias efectivamente distintas del valor en A + B, una de A y otra de B.

En la teoría del tipo, una unión etiquetada se llama Tipo de suma. Los tipos de suma son el doble de tipos de productos. Las notaciones varían, pero generalmente el tipo de suma A + B viene con dos formas de introducción (inyecciones) inj₁: A → A + B y inj₂: B → A + B. El formulario de eliminación es el análisis de casos, conocido como patrón que coincide en lenguajes de estilo ML: si e tipo A + B y e₁ y e₂ tipo τ τ {displaystyle tau } en virtud de las hipótesis x: A y Sí.: B respectivamente, entonces el término caseeofx⇒ ⇒ e1▪ ▪ Sí.⇒ ⇒ e2{displaystyle {Mathsf {case} e {fnMithsf {}fnh} xRightarrow e_{1}mid Y 'Rightarrow E_{2} tipo τ τ {displaystyle tau }. El tipo de suma corresponde a la disyunción lógica intuitiva bajo la correspondencia Curry-Howard.

Un tipo enumerado puede verse como un caso degenerado: una unión etiquetada de tipos de unidades. Corresponde a un conjunto de constructores nulos y puede implementarse como una variable de etiqueta simple, ya que no contiene datos adicionales además del valor de la etiqueta.

Muchas técnicas de programación y estructuras de datos, incluida la cuerda, la evaluación diferida, la jerarquía de clases (ver más abajo), la aritmética de precisión arbitraria, la codificación CDR, el bit de indirección y otros tipos de punteros etiquetados, etc. Por lo general, se implementan utilizando algún tipo de unión etiquetada.

Una unión etiquetada puede verse como el tipo más simple de formato de datos autodescriptivo. La etiqueta de la unión etiquetada puede verse como el tipo de metadatos más simple.

Ventajas y desventajas

La principal ventaja de una unión etiquetada sobre una unión sin etiquetar es que todos los accesos son seguros y el compilador puede incluso verificar que se manejen todos los casos. Las uniones sin etiquetar dependen de la lógica del programa para identificar correctamente el campo actualmente activo, lo que puede provocar un comportamiento extraño y errores difíciles de encontrar si esa lógica falla.

La principal ventaja de una unión etiquetada sobre un registro simple que contiene un campo para cada tipo es que ahorra almacenamiento al superponer el almacenamiento para todos los tipos. Algunas implementaciones reservan suficiente almacenamiento para el tipo más grande, mientras que otras ajustan dinámicamente el tamaño de un valor de unión etiquetado según sea necesario. Cuando el valor es inmutable, es sencillo asignar tanto almacenamiento como sea necesario.

La principal desventaja de las uniones etiquetadas es que la etiqueta ocupa espacio. Dado que normalmente hay un pequeño número de alternativas, la etiqueta a menudo se puede comprimir en 2 o 3 bits siempre que haya espacio, pero a veces ni siquiera estos bits están disponibles. En este caso, una alternativa útil pueden ser etiquetas plegadas, calculadas o codificadas, donde el valor de la etiqueta se calcula dinámicamente a partir del contenido de la unión. campo. Ejemplos comunes de esto son el uso de valores reservados, donde, por ejemplo, una función que devuelve un número positivo puede devolver -1 para indicar un error, y los valores centinela, que se utilizan con mayor frecuencia en punteros etiquetados.

A veces, las uniones sin etiquetar se utilizan para realizar conversiones a nivel de bits entre tipos, lo que se denomina reinterpretación de conversiones en C++. Las uniones etiquetadas no están destinadas a este fin; normalmente se asigna un nuevo valor cada vez que se cambia la etiqueta.

Muchos lenguajes admiten, hasta cierto punto, un tipo de datos universal, que es un tipo que incluye todos los valores de todos los demás tipos y, a menudo, se proporciona una forma de probar el tipo real de un valor del tipo universal. A veces se las denomina variantes. Si bien los tipos de datos universales son comparables a las uniones etiquetadas en su definición formal, las uniones etiquetadas típicas incluyen un número relativamente pequeño de casos, y estos casos forman diferentes formas de expresar un único concepto coherente, como un nodo de estructura de datos o una instrucción. Además, existe la expectativa de que todos los casos posibles de unión etiquetada se aborden cuando se utilice. Los valores de un tipo de datos universal no están relacionados y no existe una forma factible de tratarlos todos.

Al igual que los tipos de opciones y el manejo de excepciones, las uniones etiquetadas a veces se utilizan para manejar la aparición de resultados excepcionales. A menudo, estas etiquetas se incluyen en el tipo valores reservados y su aparición no se verifica de manera consistente: esta es una fuente bastante común de errores de programación. Este uso de uniones etiquetadas se puede formalizar como una mónada con las siguientes funciones:

retorno:: A→ → ()A+E)=a↦ ↦ valora{displaystyle {text{return}colon Ato left(A+Eright)=amapsto {text{value},a}

Bind:: ()A+E)→ → ()A→ → ()B+E))→ → ()B+E)=a↦ ↦ f↦ ↦ {}erresia=errefa.sia=valora.{displaystyle {text{bind}}colon left(A+Eright)to left(Ato left(B+Eright)to left(B+Eright)=amapsto fmapsto {begin{cases}text{err}},e char{if}f}} a={text{err},ef,a,af} a={text{value}, a'end{cases}}

donde "valor" y "errar" son los constructores del tipo de unión, A y B son tipos de resultados válidos y E es el tipo de condiciones de error. Alternativamente, la misma mónada puede describirse mediante return y dos funciones adicionales, fmap y join:

fmap:: ()A→ → B)→ → ()()A+E)→ → ()B+E))=f↦ ↦ a↦ ↦ {}erresia=errevalor()fa.)sia=valora.{displaystyle {text{fmap}colon (Ato B)to left(left(A+Eright)to left(B+Eright)right)=fmapsto amapsto {begin{cases}text{err},e limit{text{if}} a={text{err},e\{text{value},{text{},f,a',{text{)}}} {if} a={text{value}, {f},}, a'end{cases}}

Únase:: ()()A+E)+E)→ → ()A+E)=a↦ ↦ {}erresia=erreerresia=valor(erre)valora.sia=valor(valora.){displaystyle {text{join}}colon ((A+E)+E)to (A+E)=amapsto {begin{cases}{text{err},e ventaja{mbox{if} a={text{err},e\{text{err},e limit{text{if} a={text{value},{text{},e,{text{)}\\{text{value}},a' limit {text{if} a={text{value},{text{value},a',{text{f}}}}}}f}fnf}f}f}fnMinMinMinMinMinMinMinMinMinMinMinMinMinMinMinMinMinMinMinMinMinMinMinMinMinMinMinMinMinMinMinMinMientras, minMinMientras, mientras, mientras, mientras, mientras, mire, mire, mire, mire, mientras, mire, mientras, mire, mientras, mire, miren, miren, mientras, mientras, miren, miren, mientras,

Ejemplos

Say we wanted to build a binary tree of integers. In ML, we would do this by creating a data type like this:

datatype árbol = Leaf Silencio Node de ()int * árbol * árbol)

Esta es una unión etiquetada con dos casos: uno, la hoja, se usa para terminar una ruta del árbol y funciona de manera muy similar a como lo haría un valor nulo en lenguajes imperativos. La otra rama contiene un nodo, que contiene un número entero y un subárbol izquierdo y derecho. Leaf y Node son los constructores que nos permiten producir un árbol en particular, como por ejemplo:

Node()5, Node()1, Leaf, Leaf), Node()3, Leaf, Node()4, Leaf, Leaf))

que corresponde a este árbol:

Ahora podemos escribir fácilmente una función con seguridad de tipos que, por ejemplo, cuente el número de nodos en el árbol:

diversión Conteo()Leaf) = 0 Silencio Conteo()Node()int, izquierda, derecho) = 1 + Conteo()izquierda) + Conteo()derecho)

Cronología de soporte lingüístico

Década de 1960

In ALGOL 68, tagged unions are called united modes, the tag is implicit, and the case construct is used to determine which field is tagged:

mode node = union (real, int, complex, string);

Ejemplo de uso para union caso de nodo:

nodos n:= "1234";

Caso n dentro()real r): print(("real:", r)),
()int i): print("int:", i)),
()compl c): print("compl:", c)),
()cuerda s): print("string:", s)
 Fuera. print(?:", n))
esac

Tipo shapeKind = ()cuadrado, rectángulo, círculo); forma = récord centerx : entero; centro : entero; Caso especie : shapeKind de cuadrado : ()lado : entero); rectángulo : ()ancho, altura : entero); círculo : ()radio : entero); final;

Tipo Shape_Kind es ()Plaza, Rectángulo, Circle);Tipo Forma ()Tipo : Shape_Kind) es récord Center_X : Integer; Center_Y : Integer; Caso Tipo es cuando Plaza = Lado : Integer; cuando Rectángulo = Width, Altura : Integer; cuando Circle = Radius : Integer; final Caso;final record;-- Cualquier intento de acceder a un miembro que depende de la existencia-- en cierto valor del discriminante, mientras que el-- el discriminante no es el esperado, plantea un error.

enum ShapeKind {} Plaza, Rectángulo, Circle };struct Forma {} int centerx; int centro; enum ShapeKind especie; sindicato {} struct {} int lado; }; * Plaza */ struct {} int ancho, altura; }; * Rectángulo */ struct {} int radio; }; * Circle */ };};int getSquareSide()struct Forma* s) {} afirmación()s-especie == Plaza); retorno s-lado;}vacío setSquareSide()struct Forma* s, int lado) {} s-especie = Plaza; s-lado = lado;}/* y así sucesivamente */

struct pantalla : impulso::static_visitor.vacío■{} vacío operador()(int i) {} std::Cout .. "Es una int, con valor" .. i .. std::endl; } vacío operador()(const std::cuerda" s) {} std::Cout .. "Es una cuerda, con valor" .. s .. std::endl; }};impulso::variante.int, std::cuerda■ v = 42;impulso::apply_visitor()pantalla(), v);impulso::variante.int, std::cuerda■ v = "hola mundo";impulso::apply_visitor()pantalla(), v);

sellado sellado sellado sellado sellado sellado sellado sellado sellado abstracto clase ÁrbolCaso objeto Leaf extensiones ÁrbolCaso clase Node()valor: Int, izquierda: Árbol, derecho: Árbol) extensiones Árbolval árbol = Node()5, Node()1, Leaf, Leaf), Node()3, Leaf, Node()4, Leaf, Leaf))

árbol partido {} Caso Node()x, ¿Qué?, ¿Qué?) = println()"valor de nodo de nivel superior: " + x) Caso Leaf = println()"El nodo de nivel superior es una hoja")}

sellado sellado sellado sellado sellado sellado sellado sellado sellado abstracto clase Forma()centerX: Int, centerY: Int)Caso clase Plaza()lado: Int, centerX: Int, centerY: Int) extensiones Forma()centerX, centerY)Caso clase Rectángulo()longitud: Int, altura: Int, centerX: Int, centerY: Int) extensiones Forma()centerX, centerY)Caso clase Circle()radio: Int, centerX: Int, centerY: Int) extensiones Forma()centerX, centerY)

Tipo Árbol = Silencio Leaf Silencio Node de valor: int * izquierda: Árbol * derecho: ÁrbolDeja árbol = Node()5, Node()1, Leaf, Leaf), Node()3, Leaf, Node()4, Leaf, Leaf))

partido árbol conSilencio Node ()x, _ _) - printfn "valor de nodo de nivel superior: %i" xSilencio Leaf - printfn "El nodo de nivel superior es una hoja"

enum Color {} Rojo; Verde; Azul; Rgb()r:Int, g:Int, b:Int);}

interruptor ()color) {} Caso Rojo: rastro()"El color era rojo"); Caso Verde: rastro()"El color era verde"); Caso Azul: rastro()"El color era azul"); Caso Rgb()r, g, b): rastro()"Color tenía un valor rojo de " +r);}

Tipo ShapeKind = enum skSquare, skRectangle, skCircle Forma = objeto centerX, centerY: int Caso especie: ShapeKind de skSquare: lado: int de skRectangle: longitud, altura: int de skCircle: radio: int

importación Pattyproc # `[A]()a: A): ref A = nuevo()resultado) resultado[] = avariante Lista[A]: Nil Cons()x: A, xs: ref Lista[A])proc listHelper[A]()xs: seq[A]): Lista[A] = si xs.Len == 0: Nil[A]() más: Cons()xs[0], ~listHelper()xs[1 .. xs.alto])proc lista[A]()xs: varargs[A]): Lista[A] = listHelper()@xs)proc suma()xs: Lista[int]): int = ()bloque: partido xs: Nil: 0 Cons()Sí., Ys): Sí. + suma()Ys[]))eco suma()lista()1, 2, 3, 4, 5)

enum Árbol[+T]: Caso Leaf Caso Node()x: Int, izquierda: Árbol[T] derecho: Árbol[T])enum Forma()centerX: Int, centerY: Int): Caso Plaza()lado: Int, centerX: Int, centerY: Int) extensiones Forma()centerY, centerX) Caso Rectángulo()longitud: Int, altura: Int, centerX: Int, centerY: Int) extensiones Forma()centerX, centerY) Caso Circle()radio: Int, centerX: Int, centerY: Int) extensiones Forma()centerX, centerY)

enum Árbol {} Leaf, Node()i64, Recuadro.Árbol■, Recuadro.Árbol■)}

Deja árbol = Árbol::Node() 2, Recuadro::nuevo()Árbol::Node()0, Recuadro::nuevo()Árbol::Leaf), Recuadro::nuevo()Árbol::Leaf)), Recuadro::nuevo()Árbol::Node()3, Recuadro::nuevo()Árbol::Leaf), Recuadro::nuevo()Árbol::Node()4, Recuadro::nuevo()Árbol::Leaf), Recuadro::nuevo()Árbol::Leaf)))));f add_values()árbol: Árbol) - i64 {} partido árbol {} Árbol::Node()v, a, b) = v + add_values()*a) + add_values()*b), Árbol::Leaf = 0 }}¡Afirm_eq!()add_values()árbol), 9);

enum Árbol {} Caso hoja indirectas Caso nodos()Int, Árbol, Árbol)}Deja árbol = Árbol.nodos() 2, .nodos()0, .hoja, .hoja), .nodos()3, .hoja, .nodos()4, .hoja, .hoja))func add_values()¿Qué? árbol: Árbol) - Int {} interruptor árbol {} Caso Deja .nodos()v, a, b): retorno v + add_values()a) + add_values()b) Caso .hoja: retorno 0 }}afirmación()add_values()árbol) == 9)

interfaz Leaf {} especie: "Risas"; }interfaz Node {} especie: "nodo"; valor: Número; izquierda: Árbol; derecho: Árbol; }Tipo Árbol = Leaf Silencio Nodeconst root: Árbol = {} especie: "nodo", valor: 5, izquierda: {} especie: "nodo", valor: 1, izquierda: {} especie: "Risas" } derecho: {} especie: "Risas" } } derecho: {} especie: "nodo", valor: 3, izquierda: {} especie: "Risas" } derecho: {} especie: "nodo", valor: 4, izquierda: {} especie: "Risas" } derecho: {} especie: "Risas" } } }}función visita()árbol: Árbol) {} interruptor ()árbol.especie) {} Caso "Risas": descanso Caso "nodo": consola.log()árbol.valor) visita()árbol.izquierda) visita()árbol.derecho) descanso  } }

Moneda = Anotado[ TipodDict()'Currency' ', {}'dólares ': flotador, Sonríe ': flotador} total=Falso), TaggedUnion,]

utilizando Árbol = std::variante.struct Leaf, struct Node■;struct Leaf{} std::cuerda valor;};struct Node{} Árbol* izquierda = nullptr; Árbol* derecho = nullptr;};struct Transverser{} plantilla.nombre T■ vacío operador()(T" v) {} si constexpr ()std::is_same_v.T, Leaf") {} std::Cout .. v.valor .. "n"; } más si constexpr ()std::is_same_v.T, Node") {} si ()v.izquierda ! nullptr) std::visita()Transverser{} *v.izquierda); si ()v.derecho ! nullptr) std::visita()Transverser{} *v.derecho); } más {} // La expresión !sizeof(T) es siempre falsa static_assert()!tamaño()T), "¡Visitante no agotador!"); }; }};/*Tree forest =... std::visit(Transverser{}, forest);*/