Tipos de datos para la especificación

Vamos a contar con muchos tipos de datos, algunos conocidos y otros nuevos. En particular, tenemos:

• $Z$ : Números enteros

• $R$ : Números reales

• $B o o l$ : Tipo booleano, verdadero, falso e indefinido.

• $C h a r$ : Caracter, denota una letra del alfabeto

Cada uno de estos tipos van a tener sus operaciones para poder trabajar con ellos, y la mayoría ya los conocemos, de hecho, pero eso lo veremos en profundidad mas adelante.

Los tipos numéricos cuentan con las operaciones algebraicas ya conocidas. Podemos sumarlas, restarlas, multiplicarlas, dividirlas, tomar valor absoluto, evaluar modulo, entre muchas otras. También podemos utilizar sumatorias y productorias, tanto con los enteros como con los reales.

Los valores de tipo $b o o l e a n o$ se comportan siguiendo la lógica trivaluada. Operaciones como el y lógico, $o l o g i c o$ , o la $n e g a c i o n$ están mas que disponibles, entre otras.

Por ultimo, los caracteres son las letras del alfabeto, tanto mayúsculas como minúsculas. Nos van a ser útiles para la manipulación de textos.

Datos compuestos

Numerados

Los tipos enumerados, por otro lado, son un conjunto de constantes que construimos nosotros. Como tal no hay tipos enumerados preexistentes, los vamos inventando a medida que los necesitemos. Existe, para tener en cuenta, la convención de escribir sus valores en mayúsculas, ya que son datos inmutables y que no van a cambiar, así las diferenciamos de otras variables. Para definir el tipo Día, por ejemplo, escribiríamos:

enum Día{LUN, MAR, MIER, JUE, VIE, SAB, DOM}

Equivalentemente a los $c h a r$ , los tipo enumerados poseen funciones de orden y comparación. Por ejemplo, podemos consultar que día es el que está en la posición 2, o en que posición está determinado día. Noten que el índice de posiciones empieza en 0.

ord(LUN) = 0
Día(2) = MIE
MAR < JUE = True

Vectores

Continuando con los tipos de datos, tenemos la $u p l a$ , o $n - u p l a$ , o $t u p l a$ . Le digan como le digan, en definitiva, se trata de un ”vector” de datos, que pueden ser distintos o no. Algo importante, es que las tuplas tienen un tamaño fijo: no podemos agregar ni quitar elementos. Se definen $T_{0} \times T_{1} \times \dots \times T_{n}$ , donde $T_{i}$ es el tipo de en la posición $i$ . Por ejemplo, $Z \times Z$ define el conjunto de vectores de dos dimensiones de los enteros, es decir los $(x, y)$ , donde tanto $x$ e $y$ son enteros. También podemos combinar tipos, como $Z \times C h a r$ , es decir, vectores de la forma (n; a), donde n es un entero y a algún caracter de los que vimos antes.

Podemos acceder a cualquier posición del vector utilizando la notación $(a_{0}, a_{1}, \dots, a_{n})_{m}$ , donde $0 \leq m < n$ , en caso contrario se indefine.

\begin{aligned} (12, T r u e,^{'} a^{'})_{0} & = 12 \\ (12, T r u e,^{'} a^{'})_{1} & = T r u e \\ (12, T r u e,^{'} a^{'})_{2} & =^{'} a^{'} \\ (12, T r u e,^{'} a^{'})_{3} & =⊥ \end{aligned}

Secuencias

Las secuencias son una colección de valores de un mismo tipo, que pueden estar repetidos o no, y que tienen un cierto orden. Se definen $s e q ⟨ T ⟩$ , donde $T$ es el tipo de los datos. El tamaño de las secuencias, a diferencia de las tuplas, puede variar, o incluso pueden estar vacías. A su vez, como $s e q ⟨ T ⟩$ es un tipo de dato en si mismo, podríamos definir una secuencia de secuencias de tipo $T$ , es decir $s e q ⟨ s e q ⟨ T ⟩ ⟩$ .

Por ejemplo, veamos una $s e q ⟨ T ⟩$ :

• $⟨ 1, 2, 3, 4, 5 ⟩$ es una secuencia de enteros

• $⟨ 5, 4, 3, 2, 1 ⟩$ es otra secuencia de enteros, ya que tiene otro orden

• $⟨ 1, 2, 3, 4, T r u e ⟩$ es una secuencia de enteros mal definida, ya que uno de sus elementos es de otro tipo

• $⟨ ⟩$ es una secuencia de enteros que está vacía

Tenemos un montón de funciones muy interesantes con las secuencias, vamos a verlas una a una. Para empezar, tenemos una operación que nos indica la longitud de la secuencia. Lo notamos $l e n g t h (a : s e q ⟨ T ⟩) : Z$ , donde a es la secuencia a evaluar. También podemos escribir $| a |$ , que es considerablemente mas corto. Unos ejemplos de esto:

\begin{array}{r} | ⟨ 1, 2, 3 ⟩ | = 3 \\ | ⟨^{'} E^{'},^{'} l^{'} ⟩ | = 2 \\ | ⟨ ⟩ | = 0 \end{array}

Por otro lado, tenemos la indexación, que dado un índice de la secuencia nos devuelve el valor en esa posición. Requerimos que el índice dado $i$ para la lista $l$ cumpla $0 \leq i < | l |$ , ya que en otros casos será indefinido. Es semejante a lo que hacíamos con los vectores, solo cambia la notación, pero es algo a tener en cuenta.

\begin{aligned} ⟨ 1, 2, 3 ⟩ [0] & = 1 \\ ⟨^{'} M^{'},^{'} a^{'},^{'} s^{'} ⟩ [1] & =^{'} a^{'} \\ ⟨ ⟩ [0] & =⊥ \end{aligned}

También podemos evaluar igualdad entre secuencias, la cual se cumple si y solo si tienen la misma cantidad de elementos, y para cualquier índice dado, el $i - e s i m o$ elemento en la primera lista es igual al de la segunda. Por ejemplo:

\begin{aligned} ⟨ 1, 2, 3 ⟩ & = ⟨ 1, 2, 3 ⟩ \\ ⟨ ⟩ & = ⟨ ⟩ \\ ⟨ 1, 2, 3 ⟩ & \neq ⟨ 1, 3, 2 ⟩ \\ ⟨ 2, 2, 2 ⟩ & = ⟨ 2, 2, 2 ⟩ \end{aligned}

Luego tenemos las operaciones de $h e a d$ (o cabeza) y $t a i l$ (o cola). La operación $h e a d$ , dada una lista $s$ nos devuelve el primer elemento de la misma, pero es requisito que la lista tenga por lo menos un elemento. Por otro lado, la función $t a i l$ , dada una lista $s$ nos devuelve la lista sin el primer elemento, es decir, habiéndole sacado la cabeza.

\begin{aligned} h e a d (⟨ 1, 2, 3 ⟩) & = 1 \\ h e a d (⟨ ⟩) & =⊥ \\ t a i l (⟨ 1, 3, 2 ⟩) & = ⟨ 3, 2 ⟩ \\ t a i l (⟨ 2 ⟩) & = ⟨ ⟩ \end{aligned}

Para agregar elementos a una lista tenemos la operación de $A d d F i r s t$ (o añadir al principio), que dado un elemento $t$ y una lista $l$ , crea una secuencia igual a $l$ pero ”moviendo” todos sus elementos una posición y dejando en la primera a $t$ .

\begin{aligned} a d d F i r s t (^{'} H^{'}, ⟨^{'} o^{'},^{'} l^{'},^{'} a^{'} ⟩) & = ⟨^{'} H^{'},^{'} o^{'},^{'} l^{'},^{'} a^{'} ⟩ \\ a d d F i r s t (1, ⟨ 2, 2, 2 ⟩) & = ⟨ 1, 2, 2, 2 ⟩ \\ a d d F i r s t (1, ⟨ ⟩) & = ⟨ 1 ⟩ \end{aligned}

Quizás queremos combinar dos secuencias en una sola, y para eso tenemos la operación de la concatenación. La notamos $c o n c a t (a; b)$ o $a + + b$ , donde $a$ y $b$ son dos secuencias cualesquiera. Lo que hace esta operación es devolvernos una lista con los elementos de $a$ , seguidos de los de $b$ . Las dos listas deben ser del mismo tipo.

\begin{aligned} ⟨^{'} H^{'} ⟩ + + ⟨^{'} o^{'},^{'} l^{'},^{'} a^{'} ⟩ & = ⟨^{'} H^{'},^{'} o^{'},^{'} l^{'},^{'} a^{'} ⟩ \\ ⟨ 1, 2, 3 i + + ⟨ 3, 4, 5 ⟩ & = ⟨ 1, 2, 3, 3, 4, 5 ⟩ \\ ⟨ ⟩ + + ⟨ ⟩ & = ⟨ ⟩ \\ ⟨ 1, 2 ⟩ + + ⟨ ⟩ & = ⟨ 1, 2 ⟩ \\ ⟨ ⟩ + + ⟨ 1, 2 ⟩ & = ⟨ 1, 2 ⟩ \end{aligned}

También podemos "cortar" secuencias, con la operación de $s u b s e q$ (o subsecuencia). Esta operación toma una lista $l$ , y dos números enteros $d$ y $h$ , donde se cumple que $0 \leq d \leq h < | l |$ , y cuando no se indefine. Esta operación devuelve una sublista de $l$ en las posiciones entre $d$ (inclusive) y $h$ (exclusive). Notemos que cuando $d = h$ , el resultado es la secuencia vacía.

\begin{aligned} s u b s e q (⟨^{'} o^{'},^{'} l^{'},^{'} a^{'} ⟩, 0, 1) & = ⟨^{'} o^{'} ⟩ \\ s u b s e q (⟨^{'} o^{'},^{'} l^{'},^{'} a^{'} ⟩, 0, 3) & = ⟨^{'} o^{'},^{'} l^{'},^{'} a^{'} ⟩ \\ s u b s e q (⟨^{'} o^{'},^{'} l^{'},^{'} a^{'} ⟩, 1, 1) & = ⟨ ⟩ \\ s u b s e q (⟨^{'} o^{'},^{'} l^{'},^{'} a^{'} ⟩, - 1, 3) & =⊥ \\ s u b s e q (⟨^{'} o^{'},^{'} l^{'},^{'} a^{'} ⟩, 0, 5) & =⊥ \end{aligned}

Para terminar tenemos la operación de reemplazar un valor en alguna posición de una secuencia. Es decir, la operación $s e t A t$ (o modifica en). Dada una lista $l$ , una posición $i$ , y un valor $n$ del tipo de los elementos de la secuencia, podemos construir la operación $s e t A t (l, i, n)$ , donde requerimos que $0 \leq i < | l |$ , ya que en caso contrario se indefiniría.

\begin{aligned} s e t A t (⟨^{'} o^{'},^{'} l^{'},^{'} a^{'} ⟩, 0,^{'} p^{'}) & = ⟨^{'} p^{'},^{'} l^{'},^{'} a^{'} ⟩ \\ s e t A t (⟨^{'} o^{'},^{'} l^{'},^{'} a^{'} ⟩, 0,^{'} O^{'}) & = ⟨^{'} O^{'},^{'} l^{'},^{'} a^{'} ⟩ \\ s e t A t (⟨^{'} o^{'},^{'} l^{'},^{'} a^{'} ⟩, 0, 3) & =⊥ \\ s e t A t (⟨ ⟩, 0, 5) & =⊥ \end{aligned}

Por ultimo, las matrices. Consisten en secuencias de secuencias, donde todas las secuencias internas tienen exactamente el mismo tamaño, y no deben ser vacías. Es decir, una matriz de números enteros se define como $s e q ⟨ s e q ⟨ Z ⟩ ⟩$ , aunque también aceptamos el reemplazo sintáctico de $M a t ⟨ T ⟩$ .

En si mismo, las matrices no tienen operaciones básicas, pero, al tratarse finalmente de secuencias, podemos construir las nuestras.

Conjuntos

Al igual que en las secuencias, es como $c o n j {T}$ es un tipo en si mismo, es posible crear conjuntos de conjuntos, o incluso conjuntos de secuencias, o secuencias de conjuntos. Algunos ejemplos para empezar pueden ser:

${1, 2, 3}$ es un conjunto de $Z$
${3, 2, 1}$ es un conjunto de $Z$ igual al anterior, porque no importa el orden o los repetidos
${}$ es un conjunto vacío de cualquier tipo.

Las operaciones sobre conjuntos son las mismas que las de los conjuntos matemáticos, es decir, pertenencia, tamaño, unión, intersección y resta.