Hispanopedia Wiki
Articulo de referencia

Familia de tipos

En informática , una familia de tipos asocia tipos de datos con otros tipos de datos , utilizando una función a nivel de tipo definida por una colección abierta de instancias vá...

Hispanopedia WikiContenido en espanolLectura gratuita

En informática , una familia de tipos asocia tipos de datos con otros tipos de datos , utilizando una función a nivel de tipo definida por una colección abierta de instancias válidas de tipos de entrada y los tipos de salida correspondientes. [ 1 ]

Las familias de tipos son una característica de algunos sistemas de tipos que permiten definir funciones parciales entre tipos mediante la coincidencia de patrones . Esto contrasta con los constructores de tipos de datos , que definen funciones inyectivas desde todos los tipos de un tipo particular a un nuevo conjunto de tipos, y con los sinónimos de tipo (también conocidos como typedef ), que definen funciones desde todos los tipos de un tipo particular a otro conjunto de tipos existente utilizando un único caso.

Las familias de tipos y las clases de tipos están estrechamente relacionadas: las clases de tipos normales definen funciones parciales de tipos a una colección de valores con nombre mediante la coincidencia de patrones en los tipos de entrada, mientras que las familias de tipos definen funciones parciales de tipos a tipos mediante la coincidencia de patrones en los tipos de entrada. De hecho, en muchos usos de las familias de tipos existe una única clase de tipos que contiene lógicamente tanto los valores como los tipos asociados a cada instancia. Una familia de tipos declarada dentro de una clase de tipos se denomina tipo asociado . [ 2 ]

Los lenguajes de programación que admiten familias de tipos o características similares incluyen Haskell (con una extensión de lenguaje común), [ 3 ] Standard ML (a través de su sistema de módulos), [ 4 ] Rust , [ 5 ] Scala (bajo el nombre de "tipos abstractos"), [ 6 ] y C++ (a través del uso de typedefs en plantillas). [ 7 ]

Variaciones

La TypeFamiliesextensión del compilador Glasgow Haskell admite tanto familias de sinónimos de tipo como familias de datos . Las familias de sinónimos de tipo son la forma más flexible (pero más difícil de verificar), permitiendo que los tipos en el codominio de la función de tipo sean cualquier tipo con el tipo apropiado . [ 7 ] Las familias de datos, por otro lado, restringen el codominio al requerir que cada instancia defina un nuevo constructor de tipo para el resultado de la función. Esto garantiza que la función sea inyectiva , permitiendo que los contextos de los clientes deconstruyan la familia de tipos y obtengan el tipo de argumento original. [ 1 ]

Motivación y ejemplos

Las familias de tipos son útiles para abstraer patrones donde se repite una "organización" o "estructura" común de tipos, pero con diferentes tipos específicos en cada caso. Los casos de uso típicos incluyen la descripción de tipos de datos abstractos como colecciones genéricas o patrones de diseño como modelo-vista-controlador .

Tipos de datos abstractos autooptimizados

Una de las motivaciones originales para la introducción de los tipos asociados fue permitir que los tipos de datos abstractos se parametrizaran por su tipo de contenido, de modo que la estructura de datos que implementa el tipo abstracto varíe de forma "autooptimizada". [ 2 ] Los parámetros de tipos de datos algebraicos normales solo pueden describir estructuras de datos que se comportan de manera uniforme con respecto a todos los tipos de argumentos. Sin embargo, los tipos asociados pueden describir una familia de estructuras de datos que tienen una interfaz uniforme pero varían en su implementación según uno o más parámetros de tipo. Por ejemplo, [ 2 ] utilizando la notación de tipos asociados de Haskell, podemos declarar una clase de tipos de elementos de matriz válidos , con una familia de datos asociada que representa una matriz de ese tipo de elemento:

clase ArrayElem e donde datos Array e índice :: Array e -> Int -> e

A continuación, se pueden definir instancias para esta clase, que definen tanto la estructura de datos utilizada como las operaciones sobre ella en un único lugar. Para mayor eficiencia, podríamos usar una representación de vector de bits empaquetado para matrices de valores booleanos , mientras que usaríamos una estructura de datos de matriz normal para valores enteros. La estructura de datos para matrices de pares ordenados se define recursivamente como un par de matrices de cada tipo de elemento.

instancia ArrayElem Bool donde data Array Bool = BoolArray BitVector index ( BoolArray ar ) i = indexBitVector ar i instancia ArrayElem Int donde data Array Int = IntArray UIntArr index ( IntArray ar ) i = indexUIntArr ar i instancia ( ArrayElem a , ArrayElem b ) => ArrayElem ( a , b ) donde data Array ( a , b ) = PairArray ( Array a ) ( Array b ) index ( PairArray ar br ) = ( index ar i , index br i )

Con estas definiciones, cuando un cliente hace referencia a una instancia Array (Int, Bool), se selecciona automáticamente una implementación utilizando las instancias definidas.

Una clase para colecciones

Invirtiendo el ejemplo anterior, también podemos usar familias de tipos para definir una clase para tipos de colección, donde la función de tipo asigna cada tipo de colección a su tipo de elemento correspondiente: [ 7 ]

clase Collects c donde tipo Elem c vacío :: c insertar :: Elem c -> c -> c toList :: c -> [ Elem c ] instancia Collects [ e ] donde tipo Elem [ e ] = e vacío = [] insertar = ( : ) toList = id instancia Ord e => Collects ( Set . Set e ) donde tipo Elem ( Set . Set e ) = e vacío = Set . vacío insertar = Set . insertar toList = Set . toList

En este ejemplo, el uso de una familia de sinónimos de tipo en lugar de una familia de datos es esencial, ya que varios tipos de colección pueden tener el mismo tipo de elemento.

Comparación con dependencias funcionales

Las dependencias funcionales son otra característica del sistema de tipos que tiene usos similares a los tipos asociados. Mientras que un tipo asociado agrega una función de tipo con nombre que mapea los parámetros de la clase de tipo contenedora a otro tipo, una dependencia funcional enumera el tipo de resultado como otro parámetro de la clase de tipo y agrega una restricción entre los parámetros de tipo (por ejemplo, "el parámetro a determina de forma única el parámetro b ", escrito ). Los usos más comunes de las dependencias funcionales se pueden convertir directamente a tipos asociados y viceversa. [ 7 ]a -> b

Las familias de tipos se consideran generalmente más fáciles de verificar que las dependencias funcionales. Otra ventaja de los tipos asociados sobre las dependencias funcionales es que estas últimas requieren que los clientes que utilizan la clase de tipos declaren todos los tipos dependientes en sus contextos, incluidos aquellos que no utilizan; dado que los tipos asociados no requieren esto, agregar otro tipo asociado a la clase solo requiere actualizar las instancias de la clase, mientras que los clientes pueden permanecer sin cambios. Las principales ventajas de las dependencias funcionales sobre las familias de tipos radican en su mayor flexibilidad para manejar algunos casos inusuales. [ 8 ]

Referencias

  1. 1 2 Kiselyov, Oleg; Peyton Jones, Simon; Shan, Chung-chieh (2010). "Diversión con funciones de tipo" (PDF) .
  2. 1 2 3 Chakravarty, Manuel MT; Keller, Gabriele ; Peyton Jones, Simon; Marlow, Simon (2005). "Tipos asociados con clases" . Actas del 32.º Simposio Anual ACM SIGPLAN-SIGACT sobre Principios de Lenguajes de Programación . ACM Press: 1–13 .
  3. ↑ "Funciones de tipo, familias de tipos y tipos asociados en GHC: el plan maestro" . Abril de 2019. Consultado el 4 de abril de 2019 .
  4. ↑ Wehr, Stefan; Chakravarty, Manuel MT (2008). "ML Modules and Haskell Type Classes: A Constructive Comparison" . Actas del Sexto Simposio Asiático sobre Lenguajes y Sistemas de Programación . Lecture Notes in Computer Science. Vol. 5356. Springer-Verlag. pp. 188–204 . doi : 10.1007/978-3-540-89330-1_14 . ISBN   978-3-540-89329-5.
  5. ↑ "Elementos asociados - The Rust Reference" . Enero de 2024.
  6. ↑ "Un recorrido por Scala: tipos abstractos" . Consultado el 23 de febrero de 2013 .
  7. 1 2 3 4 Chakravarty, Manuel MT; Keller, Gabriele ; Peyton Jones, Simon (2005). "Sinónimos de tipo asociado" . Actas de la décima conferencia internacional ACM SIGPLAN sobre programación funcional . ACM Press. págs. 241–253 . doi : 10.1145/1086365.1086397 . ISBN  1595930647. S2CID 16406612 . 
  8. ↑ "Familias de tipos (FT) frente a dependencias funcionales (DF)" . Consultado el 4 de abril de 2019 .
  • Documentación de Haskell Wiki sobre el uso de familias de tipos en GHC