TIPOS ABSTRACTOS DE DATOS
Y
PROGRAMACIÓN MODULAR
2ª Sesión
Programación Declarativa Avanzada
E.T.S.Ingeniería Informática
Departamento de Lenguajes y Ciencias de la Computación
Universidad de Málaga
Sesión Previa I
 Tipos de datos
conjunto de valores que sirve de dominio de ciertas operaciones
clasificar los objetos de los programas y determinar que valores pueden
tomar y que operaciones pueden realizar
 Para restringir su ámbito de aplicación surgen los TADs.
 Un TAD considera a un tipo de datos como…
Valores que lo Caracteriza + Operaciones
 Diseño Modular: Dividir el problema original en Subproblemas más pequeños.
 Ventajas:
1. Abstracción.
2. Corrección.
3. Legibilidad.
4. Mantenimiento.
5. Seguridad.
Jesús M. Doña Fernández
Programación Declarativa Avanzada
Sesión Previa II
 Pero ¿para qué nos sirven los TADs?
 Diseño de nuevos tipos de datos  diseño modular de las
aplicaciones.
 ¿Qué es el Diseño Modular?
 Dividir el problema original en Subproblemas más pequeños.
 Ventajas:
1. Abstracción.
2. Corrección.
3. Legibilidad.
4. Mantenimiento.
5. Seguridad.
Jesús M. Doña Fernández
Programación Declarativa Avanzada
Módulos. Haskell I
 Funciones principales:
 Controlar el espacio de nombres
 Crear tipos abstractos de datos
 Sintaxis
module Cadenas (rellena, aMayusculas) where
--Añade espacios a la izquierda
El nombre del módulo en
rellena
:: Int String  String
mayúsculas.
rellena ns = espacios (n – length s) ++ s
Se guarda en fichero de
--Pasa a Mayúsculas
texto con mismo nombre
aMayusculas :: String String
aMayusculas = map toUpper
‘Cadenas.hs’
espacios :: Int String
espacios n = replicate n ‘ ‘ Lista de exportaciones: entidades vistas desde
modulo externo.
Si no aparecen  privadas (funciones internas)
Jesús M. Doña Fernández
Programación Declarativa Avanzada
TAD’s. Funciones I
 Por último en el módulo solo queda la implementación de
las funciones del TAD
 Tenemos dos opciones disponibles
 Interfaz no sobrecargado.
 Interfaz sobrecargado.
Jesús M. Doña Fernández
Programación Declarativa Avanzada
Módulos: Implementación.
Interfaz no sobrecargado.
 Mediante un interfaz no sobrecargado dos implementaciones
diferentes de un mismo tipo NO pueden ser importadas desde un
mismo módulo.
 Soluciones:
 Llamar a las funciones para las diferentes implementaciones con
nombres diferentes.
 Usar importaciones cualificadas.
 Usar interfaces sobrecargados.
Jesús M. Doña Fernández
Programación Declarativa Avanzada
TAD cola (no sobrecargado)
module Cola(
Cola,
colaVacia,
meteEnCola,
sacaDeCola,
estáVacíaCola
) where
-- Inserta un elemento en la cola
--::
--::
--::
--::
Cola a
Cola a  a  Cola a
Cola a  Bool
Cola a  Bool
type Cola a = [a]
-- Crea una nueva cola
colaVacia :: Cola a
colaVacia = []
meteEnCola :: Cola a  a  Cola a
meteEnCola q x = q ++ [x]
-- Extrae el primer elemento de una cola
-- Error si no existe
sacaDeCola :: Cola a  (a, Cola a)
sacaDeCola []
= error “sacaDeCola: cola
vacía”
sacaDeCola (x:q) = (x,q)
-- Test para conocer si una cola está vacía
estáVacíaCola :: Cola a  Bool
estáVacíaCola [] = true
estáVacíaCola _ = false
Buena Costumbre
Jesús M. Doña Fernández
Programación Declarativa Avanzada
TAD’s. Estructuras de Datos II
Interfaz sobrecargado.
 Consiste en definir una clase que contenga el interfaz de las
declaraciones para el interfaz del tipo. Permite hacer distintas
implementaciones mediante instancias concretas de esa clase.
 En estas implementaciones debemos representar a los datos
mediante constructores (data).
Jesús M. Doña Fernández
Programación Declarativa Avanzada
TAD Cola (sobrecargado)
module Cola(Cola(..)) where
class Cola q where
colaVacía :: q a
estáVacíaCola :: q a  Bool
meteEnCola :: q a  a  q a
sacaDeCola :: q a  (a, q a)
module TCola(TCola) where
import Cola
data TCola a = TC[a] deriving Eq
instance Cola Tcola where
colaVacía
= TC []
estáVacíaCola (TC []) = True
estáVacíaCola (TC _) = False
meteEnCola (TC q) x = TC (q ++ [x])
sacaDeCola (TC [])
= error“Cola vacía”
sacaDeCola (TC (x:xs)) = (x, TC xs)
Jesús M. Doña Fernández
Programación Declarativa Avanzada
module BCola(BCola(..)) where
import Cola
data Bcola a = BC [a] [a]
instance Cola Bcola where
colaVacía
= BC []
estáVacíaCola (BC [] r) = True
estáVacíaCola (BC _ r) = False
meteEnCola (BC f r) x = check f (x:r)
sacaDeCola (BC [] _)
= error“Cola vacía”
sacaDeCola (BC (x:f) r) = (x, check f r)
- - No permite que la 1º lista esté vacía a menos
- - que la 2ª tabién lo esté
check :: [a]  [a]  Cola a
check [] r = BC (reverse r) []
check f r = BC f r
- - Coloca todos los elementos en la primera
- - lista
flush :: [a]  [a]  Cola a
flush f r = BC (f ++ (reverse r)) []
TAD’s. Ejemplos I
module Pila(
TPila,
vacia,
meteEnPila,
sacaDePila,
muestra
) where
-- -> TPila a
-- a -> TPila a -> TPila a
--TPila a -> TPila a
-- (Show a) => TPila a -> String
-- Definición del tipo Pila con dos constructores
data TPila a = PilaVacia | Apila a (TPila a)
-- Devuelve una pila vacía
vacia
:: TPila a
vacia
= PilaVacia
Jesús M. Doña Fernández
Programación Declarativa Avanzada
-- Inserta un elemento en la pila
meteEnPila
:: a -> TPila a -> TPila a
meteEnPila x p
= Apila x p
-- Elimina el primer elemento de la pila
sacaDePila
:: TPila a -> TPila a
sacaDePila (Apila _ p) = p
sacaDePila PilaVacia = error "no puedes sacar nada
de una pila vacia"
-- Imprime el contenido de la pila
muestra :: (Show a) => TPila a -> String
muestra PilaVacia
= " []"
muestra (Apila x p)
= " " ++ show x ++
muestra p
TAD’s. Ejemplos II
module Conjunto(
Conjunto,
conjuntoVacio,
-- :: Conjunto a
estaVacioConjunto, -- :: Conjunto a -> Bool
añadeAConjunto,
-- :: Eq a => a -> Conjunto a -> Conjunto a
eliminaDeConjunto,
-- :: Eq a => a -> Conjunto a -> Conjunto a
estaElemConjunto,
-- :: Eq a => a -> Conjunto a -> Bool
(\/),
-- :: Eq a => Conjunto a -> Conjunto a ->
Conjunto a
(/\),
-- :: Eq a => Conjunto a -> Conjunto a ->
Conjunto a
conjuntoALista
-- :: Conjunto a -> [a]
) where import List(delete)
Jesús M. Doña Fernández
Programación Declarativa Avanzada
data Conjunto a = Conjunto [a]
-- Crea un conjunto vacío
conjuntoVacio :: Conjunto a
conjuntoVacio = Conjunto []
-- Comprueba si un conjunto está vacío
estaVacioConjunto :: Conjunto a -> Bool
estaVacioConjunto (Conjunto xs) = null xs
-- Comprueba si un elemento está en un
conjunto
estaElemConjunto :: Eq a => a -> Conjunto a ->
Bool
estaElemConjunto x (Conjunto xs)
= elem x xs
-- Inserta un elemento en un conjunto
añadeAConjunto :: Eq a => a -> Conjunto a ->
Conjunto a
añadeAConjunto x (Conjunto xs)
| elem x xs = Conjunto xs
| otherwise = Conjunto (x:xs)
TAD’s. Ejemplos III
-- Borra un elemento de un conjunto
eliminaDeConjunto :: Eq a => a -> Conjunto a ->
Conjunto a
eliminaDeConjunto x (Conjunto xs)
| estaElemConjunto x (Conjunto xs) =
Conjunto (delete x xs)
| otherwise = error "eliminaDeConjunto : no
está"
-- Union de conjuntos
infixl 6 \/
(\/) :: Eq a => Conjunto a -> Conjunto a ->
Conjunto a
cs \/ (Conjunto ys) = foldr añadeAConjunto cs ys
Jesús M. Doña Fernández
Programación Declarativa Avanzada
-- Intersección de conjunto
infixl 7 /\
(/\) :: Eq a => Conjunto a -> Conjunto a ->
Conjunto a
cs /\ (Conjunto ys) = Conjunto [x|x <- ys,
estaElemConjunto x cs]
-- Convierte un conjunto en una lista
conjuntoALista :: Conjunto a -> [a]
conjuntoALista (Conjunto xs) = xs
instance Show a => Show (Conjunto a) where
show (Conjunto xs) = "{" ++ show2 xs where
show2 [] = "}"
show2 [x] = show x ++ show2 []
show2 (x:xs) = show x ++ "," ++ show2
xs
Bibliografía
 “Razonando con Haskell. Una introducción a la Programación Funcional”. Blas
C. Ruiz Jiménez, Francisco Gutiérrez López, Pablo Guerrero García, José E. Gallardo Ruiz
 Apuntes de Tipos Abstractos de Datos (2º Curso Ing. En Informática).




polaris.lcc.uma.es/~blas/apuntes/PDAv/
haskell.org
www.info-ab.uclm.es/asignaturas/42630/BuzAPD/Trabajos/ClasesyModulosenHaskell.ppt
www.dsic.upv.es/users/elp/ slucas/MexicoWeb/TyposYEDsEnLFs.pdf
Este Trabajo estará disponible para su descarga en Internet en la dirección:
http://perso.wanadoo.es/e/intersoft/TADs
Junto con el trabajo se incluirán los enlaces a la bibliografía, a los documentos pdf y ppt
usados, así como a la exposición preparada para su presentación en clase.
Jesús M. Doña Fernández
Programación Declarativa Avanzada
Descargar

Tipos Abstractos de Datos en Haskell