Tipos abstractos de datos y programación modular 2ª Sesión Sesión Previa I



Descargar 11,94 Kb.
Fecha de conversión07.02.2017
Tamaño11,94 Kb.

TIPOS ABSTRACTOS DE DATOS Y PROGRAMACIÓN MODULAR 2ª Sesión

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.

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.

Módulos. Haskell I

  • module Cadenas (rellena, aMayusculas) where
  • --Añade espacios a la izquierda
  • rellena :: Int String  String
  • rellena ns = espacios (n – length s) ++ s
  • --Pasa a Mayúsculas
  • aMayusculas :: String String
  • aMayusculas = map toUpper
  • espacios :: Int String
  • espacios n = replicate n ‘ ‘
  • El nombre del módulo en mayúsculas.
  • Se guarda en fichero de texto con mismo nombre ‘Cadenas.hs’
  • Lista de exportaciones: entidades vistas desde modulo externo.
  • Si no aparecen  privadas (funciones internas)

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.

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.

TAD cola (no sobrecargado)

  • module Cola(
  • Cola,
  • colaVacia, --:: Cola a
  • meteEnCola, --:: Cola a  a  Cola a
  • sacaDeCola, --:: Cola a  Bool
  • estáVacíaCola --:: Cola a  Bool
  • ) where
  • type Cola a = [a]
  • -- Crea una nueva cola
  • colaVacia :: Cola a
  • colaVacia = []
  • -- Test para conocer si una cola está vacía
  • estáVacíaCola :: Cola a  Bool
  • estáVacíaCola [] = true
  • estáVacíaCola _ = false
  • -- Inserta un elemento en la cola
  • 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)

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).

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)
  • 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, -- -> TPila a
  • meteEnPila, -- a -> TPila a -> TPila a
  • sacaDePila, --TPila a -> TPila a
  • muestra -- (Show a) => TPila a -> String
  • ) where
  • -- 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
  • -- 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)
  • 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
  • -- 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.


La base de datos está protegida por derechos de autor ©absta.info 2016
enviar mensaje

    Página principal