Creo que puedo ver una analogía que las diapositivas intentaban hacer (y sospecho que este es, de hecho, el concepto que intentaban explicar porque está en el contexto de la teoría del lenguaje de programación):
Los tipos de productos algebraicos son como productos cartesianos , ya que su valor puede ser cualquier combinación de los tipos de los que están compuestos.
Por ejemplo, puede enumerar todos los valores posibles que puede tener una estructura C que contiene un
y un int
tomando el Producto cartesiano de los valores que puede tomar cada tipo: char
: -2147483648, -2147483647,…, -1, 0, 1,…, 2147483646, 2147483647 int
: char
, '\0'
, …, '\1'
, 'a'
, …, 'b'
, '\254'
'\255'
struct { int; char; }
: struct { int; char; }
, { -2147483648, '\0' }
,…, { -2147483648, '\1' }
, { 2147483647, '\254' }
{ 2147483647, '\255' }
Los tipos de suma algebraica son como uniones disjuntas (es decir, uniones de valores disjuntos), ya que su valor puede ser cualquiera de un conjunto de valores mutuamente excluyentes.
Si bien no está del todo claro en un lenguaje como Java, se podría pensar en una superclase abstracta como un tipo de suma. Por ejemplo, si tiene alguna clase abstracta de Java llamada Coin
que es heredada por las clases Quarter
, Dime
, Nickel
y Penny
, puede pensar en una variable de tipo Coin
como una que almacena una (y solo una) de Quarter
, Dime
, Nickel
o Penny
. Estos cuatro niños son mutuamente excluyentes, por ejemplo, si es un Quarter
entonces no es necesariamente ninguno de los otros tres.
La forma en que una clase puede ser un tipo de suma se vuelve mucho más clara si aprende sobre las clases de casos Scala. De lo contrario, el ejemplo de una clase como un tipo de suma es un poco complicado por el hecho de que las clases tienden a tener colecciones de campos y de esa manera actúan también como tipos de productos.
- Alguien me dijo que me especializara en un dominio CS para evitar quedar desempleado cuando envejeciera, ¿es cierto?
- ¿Por qué la mayoría de la gente trata de resolver problemas profundos en la complejidad computacional como P versus NP por combinatoria y no por lógica?
- ¿Cuál es su consejo para alguien que comienza su doctorado en informática teórica?
- ¿Cómo podría implementar un programa que calcule [math] e ^ x [/ math] sumando los primeros 100 términos de su expansión en serie?
- ¿Cuáles son los tiempos de ejecución de varios algoritmos de aprendizaje automático como SVM, redes neuronales, etc. en términos de notación big-O?
Creo que estos podrían ser más claros si utilizamos un lenguaje de programación funcional que los implemente, como OCaml.
En OCaml, un tipo de producto también se denomina “registro” y es bastante similar a una estructura.
Su definición se parece a esto:
type student = { name: string, gpa: float, year: int }
Y su uso se parece a esto:
let s = { name = "Foo Barson"; gpa = 3.7; year = 2 }
Es bastante sencillo.
Un tipo de suma en OCaml se ve un poco diferente. Tiende a ser un concepto nuevo para la mayoría de los programadores y estudiantes de CS porque a menudo no aparece explícitamente en los lenguajes de programación imperativos.
Siguiendo el ejemplo de nuestro estudiante para los tipos de productos, más arriba, consideremos una definición alternativa del campo del year
como un tipo de suma en lugar de un entero:
type year = | Freshman | Sophomore | Junior | Senior | SuperSenior
Esto dice que una variable de tipo year
tiene exactamente uno de estos valores mutuamente excluyentes; estos cinco forman el conjunto completo de valores para este tipo.
Los tipos de suma son muy útiles para la coincidencia de mayúsculas y minúsculas (por ejemplo, declaraciones de
). Por ejemplo, aquí hay una función que devuelve switch
si un estudiante es elegible para tomar una clase que requiere una posición mínima junior (aunque esto es innecesariamente detallado para OCaml del mundo real): true
let eligible (student_year: year): bool = match student_year with | Freshman -> false | Sophomore -> false | Junior -> true | Senior -> true | SuperSenior -> true
La asociación con una Unión disjunta podría ser más clara si considera que los tipos de valores para un tipo de suma podrían ser tipos de suma. Aquí hay un ejemplo más complicado. Avísame si te he perdido.
type literal = | Integer of int | Float of float | String of string type operator = | Plus | Minus | Times | Division type expr = | Literal of literal | UnaryOp of (operator, expr) | BinaryOp of (operator, expr, expr) type stmt = | Assignment of (string, expr) | VoidExpression of expr type line = | Statement of stmt | Expression of expr
Al considerar el conjunto de valores posibles del tipo expr
, debemos tener en cuenta los conjuntos de valores posibles de sus miembros. Específicamente, UnaryOp
y BinaryOp
tienen conjuntos de valores complejos por sí mismos (para operator
y expr
).
Los posibles valores para un expr
es la unión de todos los conjuntos disjuntos que describen sus posibles valores.
Y así ocurre con los tipos stmt
y line
: el conjunto de valores posibles para cada uno se determina tomando la unión de los conjuntos de valores posibles de los valores.