I1M2014: El TAD (tipo abstracto de datos) de las tablas en Haskell
En la primera parte de la clase de hoy del curso de Informática de 1º del Grado en Matemáticas se ha estudiado cómo trabajar con tablas en Haskell usando el módulo Data.Array y en la segunda parte se ha estudiado el TAD (tipo abstracto de datos) de las tablas y tres implementaciones en Haskell: como funciones, como listas de asociación y como matrices.
Una tabla (array en inglés) es una colección de elementos (valores) a los que se accede mediante sus índices<.
El contenido la segunda parte ha sido el siguiente:
- la signatura del TAD de las tablas;
- las propiedades del TAD de las tablas;
- las implementaciones, en Haskell, de las tablas mediante funciones, listas de asociación y matrices y
- la comprobación con QuickCheck de sus propiedades.
La signatura del TAD de las tablas
Las signatura de las operaciones del TAD de las tablas son las siguientes:
con el siguiente significado
- (tabla ivs) es la tabla correspondiente a la lista de asociación ivs (que es una lista de pares formados por los índices y los valores).
- (valor t i) es el valor del índice i en la tabla t.
- (modifica (i,v) t) es la tabla obtenida modificando en la tabla t el valor de i por v.
Propiedades del TAD de las tablas
Las propiedades son las siguientes:
- modifica (i,v') (modifica (i,v) t) = modifica (i,v') t
- Si i /= i', entonces modifica (i',v') (modifica (i,v) t) = modifica (i,v) (modifica (i',v') t)
- valor (modifica (i,v) t) i = v
- Si i /= i', entonces valor (modifica (i,v) (modifica (k',v') t)) i' = valor (modifica (k',v') t) i'
Implementación de las tablas mediante funciones
Implementación de las tablas mediante listas de asociación
Implementación de las tablas mediante matrices
Propiedades de las tablas
Las transparencias usadas en la clase son las del tema 18.