stringtranslate.com

Tipo de cociente

En el campo de la teoría de tipos en informática , un tipo cociente es un tipo de datos que respeta una relación de igualdad definida por el usuario. Un tipo cociente define una relación de equivalencia sobre elementos del tipo; por ejemplo, podríamos decir que dos valores del tipo son equivalentes si tienen el mismo nombre; formalmente si . En las teorías de tipos que permiten tipos cocientes, se establece un requisito adicional de que todas las operaciones deben respetar la equivalencia entre elementos. Por ejemplo, si es una función sobre valores de tipo , debe darse el caso de que para dos s y , si entonces .Personp1 == p2p1.name == p2.namefPersonPersonp1p2p1 == p2f(p1) == f(p2)

Los tipos cocientes son parte de una clase general de tipos conocidos como tipos de datos algebraicos . A principios de la década de 1980, los tipos cocientes se definieron e implementaron como parte del asistente de prueba Nuprl , en el trabajo dirigido por Robert L. Constable y otros. [1] [2] Los tipos cocientes se han estudiado en el contexto de la teoría de tipos de Martin-Löf , [3] la teoría de tipos dependientes , [4] la lógica de orden superior , [5] y la teoría de tipos de homotopía . [6]

Definición

Para definir un tipo de cociente, normalmente se proporciona un tipo de datos junto con una relación de equivalencia sobre ese tipo, por ejemplo, Person // ==, donde ==es una relación de igualdad definida por el usuario. Los elementos del tipo de cociente son clases de equivalencia de elementos del tipo original. [3]

Los tipos de cociente se pueden utilizar para definir la aritmética modular . Por ejemplo, si Integeres un tipo de datos de números enteros, se puede definir diciendo que si la diferencia es par. Entonces formamos el tipo de números enteros módulo 2: [1]

Integer //

Se puede demostrar que las operaciones sobre números enteros, +, -están bien definidas en el nuevo tipo de cociente.

Variaciones

En las teorías de tipos que carecen de tipos cocientes, se suelen utilizar setoides (conjuntos explícitamente equipados con una relación de equivalencia) en lugar de tipos cocientes. Sin embargo, a diferencia de los setoides, muchas teorías de tipos pueden requerir una prueba formal de que todas las funciones definidas en tipos cocientes están bien definidas . [7]

Propiedades

Los tipos cocientes son parte de una clase general de tipos conocidos como tipos de datos algebraicos . Así como los tipos de producto y los tipos de suma son análogos al producto cartesiano y la unión disjunta de estructuras algebraicas abstractas, los tipos cocientes reflejan el concepto de cocientes teóricos de conjuntos , conjuntos cuyos elementos se dividen en clases de equivalencia mediante una relación de equivalencia dada en el conjunto. Las estructuras algebraicas cuyo conjunto subyacente es un cociente también se denominan cocientes. Ejemplos de tales estructuras cocientes incluyen conjuntos cocientes , grupos , anillos , categorías y, en topología, espacios cocientes . [3]

Referencias

  1. ^ ab Constable, Robert L. (1986). Implementación de las matemáticas con el sistema de desarrollo de pruebas Nuprl. Prentice-Hall. ISBN 978-0-13-451832-9.
  2. ^ Constable, RL (1984). "Matemáticas como programación". En Clarke, Edmund; Kozen, Dexter (eds.). Lógica de programas . Apuntes de clase en informática. Vol. 164. Berlín, Heidelberg: Springer. págs. 116–128. doi :10.1007/3-540-12896-4_359. hdl : 1813/6405 . ISBN. 978-3-540-38775-6.
  3. ^ abc Li, Nuo (15 de julio de 2015). "Tipos cocientes en la teoría de tipos". eprints.nottingham.ac.uk . Consultado el 13 de septiembre de 2023 .
  4. ^ Hofmann, Martin (1995). "Un modelo simple para tipos de cociente". Cálculos Lambda Tipográficos y Aplicaciones . Apuntes de Clases en Ciencias de la Computación. Vol. 902. Berlín, Heidelberg: Springer. págs. 216–234. doi :10.1007/BFb0014055. ISBN. 978-3-540-49178-1.
  5. ^ Homeier, Peter V. (2005). "Una estructura de diseño para cocientes de orden superior". En Hurd, Joe; Melham, Tom (eds.). Demostración de teoremas en lógicas de orden superior . Apuntes de clase en informática. Vol. 3603. Berlín, Heidelberg: Springer. págs. 130–146. doi :10.1007/11541868_9. ISBN. 978-3-540-31820-0.
  6. ^ "El libro de HoTT". Teoría de tipos de homotopía . 2013-03-12 . Consultado el 2023-09-13 .
  7. ^ Hofmann, Martin (1997). "Constructos extensionales en la teoría de tipos intensionales". SpringerLink . doi :10.1007/978-1-4471-0963-1. ISBN 978-1-4471-1243-3.

Véase también