José A. Alonso
Departamento de Ciencias de la Computación e I.A.
Universidad de Sevilla
Sevilla, 10 de agosto de 2019
Notas:
:opt no-lint
Abstracción y tipos abstractos de datos
La abstracción es un mecanismo para comprender problemas que involucran una gran cantidad de detalles.
Aspectos de la abstracción:
Un tipo abstracto de datos (TAD) es una colección de valores y operaciones* que se definen mediante una especificación que es independiente de cualquier representación.
Un TAD es una abstracción:
Analogía con las estructuras algebraicas.
Descripción informal de las pilas
Una pila es una estructura de datos, caracterizada por ser una secuencia de elementos en la que las operaciones de inserción y extracción se realizan por el mismo extremo.
La pilas también se llaman estructuras LIFO (del inglés Last In First Out), debido a que el último elemento en entrar será el primero en salir.
Analogía con las pilas de platos.
Signatura del TAD de las pilas
sesion
vacia :: Pila a
apila :: a -> Pila a -> Pila a
cima :: Pila a -> a
desapila :: Pila a -> Pila a
esVacia :: Pila a -> Bool
vacia
es la pila vacía.(apila x p)
es la pila obtenida añadiendo x
al principio de p
.(cima p)
es la cima de la pila p
.(desapila p)
es la pila obtenida suprimiendo la cima de p
.(esVacia p)
se verifica si p
es la pila vacía.Propiedades de las pilas
cima (apila x p) == x
desapila (apila x p) == p
esVacia vacia
not (esVacia (apila x p))
Está en el fichero PilaConTipoDeDatoAlgebraico.hs.
module PilaConTipoDeDatoAlgebraico
(Pila,
vacia, -- Pila a
apila, -- a -> Pila a -> Pila a
cima, -- Pila a -> a
desapila, -- Pila a -> Pila a
esVacia -- Pila a -> Bool
) where
-- Tipo de dato algebraico de las pilas:
data Pila a = Vacia
| P a (Pila a)
deriving Eq
-- Procedimiento de escritura de pilas.
instance (Show a) => Show (Pila a) where
showsPrec _ Vacia cad = showChar '-' cad
showsPrec _ (P x s) cad = shows x (showChar '|' (shows s cad))
-- Ejemplo de pila:
-- ghci> p1
-- 1|2|3|-
p1 :: Pila Int
p1 = apila 1 (apila 2 (apila 3 vacia))
-- vacia es la pila vacía. Por ejemplo,
-- ghci> vacia
-- -
vacia :: Pila a
vacia = Vacia
-- (apila x p) es la pila obtenida añadiendo x encima de la pila p. Por
-- ejemplo,
-- apila 4 p1 => 4|1|2|3|-
apila :: a -> Pila a -> Pila a
apila x p = P x p
-- (cima p) es la cima de la pila p. Por ejemplo,
-- cima p1 == 1
cima :: Pila a -> a
cima Vacia = error "la pila vacia no tiene cima"
cima (P x _) = x
-- (desapila p) es la pila obtenida suprimiendo la cima de la pila
-- p. Por ejemplo,
-- desapila p1 => 2|3|-
desapila :: Pila a -> Pila a
desapila Vacia = error "no se puede desapila la pila vacia"
desapila (P _ p) = p
-- (esVacia p) se verifica si p es la pila vacía. Por ejemplo,
-- esVacia p1 == False
-- esVacia vacia == True
esVacia :: Pila a -> Bool
esVacia Vacia = True
esVacia _ = False
p1 = apila 1 (apila 2 (apila 3 vacia))
p1
1|2|3|-
vacia
-
apila 4 p1
4|1|2|3|-
cima p1
1
desapila p1
2|3|-
esVacia p1
False
esVacia vacia
True
:m - PilaConTipoDeDatoAlgebraico
Está en el fichero PilaConListas.hs.
module PilaConListas
(Pila,
vacia, -- Pila a
apila, -- a -> Pila a -> Pila a
cima, -- Pila a -> a
desapila, -- Pila a -> Pila a
esVacia -- Pila a -> Bool
) where
-- Representación de las pilas mediante listas.
newtype Pila a = P [a]
deriving Eq
-- Procedimiento de escritura de pilas.
instance (Show a) => Show (Pila a) where
showsPrec _ (P []) cad = showChar '-' cad
showsPrec _ (P (x:xs)) cad =
shows x (showChar '|' (shows (P xs) cad))
-- Ejemplo de pila:
-- > p1
-- 1|2|3|-
p1 :: Pila Integer
p1 = apila 1 (apila 2 (apila 3 vacia))
-- vacia es la pila vacía. Por ejemplo,
-- > vacia
-- -
vacia :: Pila a
vacia = P []
-- (apila x p) es la pila obtenida añadiendo x encima de la pila p. Por
-- ejemplo,
-- apila 4 p1 => 4|1|2|3|-
apila :: a -> Pila a -> Pila a
apila x (P xs) = P (x:xs)
-- (cima p) es la cima de la pila p. Por ejemplo,
-- cima p1 == 1
cima :: Pila a -> a
cima (P []) = error "cima de la pila vacia"
cima (P (x:_)) = x
-- (desapila p) es la pila obtenida suprimiendo la cima de la pila
-- p. Por ejemplo,
-- desapila p1 => 2|3|-
desapila :: Pila a -> Pila a
desapila (P []) = error "desapila la pila vacia"
desapila (P (_:xs)) = P xs
-- (esVacia p) se verifica si p es la pila vacía. Por ejemplo,
-- esVacia p1 == False
-- esVacia vacia == True
esVacia :: Pila a -> Bool
esVacia (P xs) = null xs
p1 = apila 1 (apila 2 (apila 3 vacia))
p1
1|2|3|-
vacia
-
apila 4 p1
4|1|2|3|-
cima p1
1
desapila p1
2|3|-
esVacia p1
False
esVacia vacia
True
:m - PilaConListas
En el fichero PilaPropiedades.hs.
module PilaPropiedades where
-- Hay que elegir una implementación del TAD pilas.
import PilaConTipoDeDatoAlgebraico
-- import PilaConListas
import Test.QuickCheck
-- ---------------------------------------------------------------------
-- Generador de pilas --
-- ---------------------------------------------------------------------
-- genPila es un generador de pilas. Por ejemplo,
-- ghci> sample genPila
-- -
-- 0|0|-
-- -
-- -6|4|-3|3|0|-
-- -
-- 9|5|-1|-3|0|-8|-5|-7|2|-
-- -3|-10|-3|-12|11|6|1|-2|0|-12|-6|-
-- 2|-14|-5|2|-
-- 5|9|-
-- -1|-14|5|-
-- 6|13|0|17|-12|-7|-8|-19|-14|-5|10|14|3|-18|2|-14|-11|-6|-
genPila :: (Arbitrary a, Num a) => Gen (Pila a)
genPila = do
xs <- listOf arbitrary
return (foldr apila vacia xs)
-- El tipo pila es una instancia del arbitrario.
instance (Arbitrary a, Num a) => Arbitrary (Pila a) where
arbitrary = genPila
-- ---------------------------------------------------------------------
-- Propiedades
-- ---------------------------------------------------------------------
-- Propiedad. La cima de la pila que resulta de apilar x en una pila p
-- es x.
prop_cima_apila :: Int -> Pila Int -> Bool
prop_cima_apila x p =
cima (apila x p) == x
-- Comprobación.
-- > quickCheck prop_cima_apila
-- +++ OK, passed 100 tests.
-- Propiedad. La pila que resulta de desapilar después de apilar
-- cualquier elemento es la pila inicial.
prop_desapila_apila :: Int -> Pila Int -> Bool
prop_desapila_apila x p =
desapila (apila x p) == p
-- Comprobación.
-- > quickCheck prop_desapila_apila
-- +++ OK, passed 100 tests.
-- Propiedad. La pila vacía está vacía.
prop_vacia_esta_vacia :: Bool
prop_vacia_esta_vacia = esVacia vacia
-- Comprobación.
-- > quickCheck prop_vacia_esta_vacia
-- +++ OK, passed 100 tests.
-- Propiedad. La pila que resulta de apilar un elemento en un pila
-- cualquiera no es vacía.
prop_apila_no_es_vacia :: Int -> Pila Int -> Bool
prop_apila_no_es_vacia x p = not (esVacia (apila x p))
-- Comprobación.
-- > quickCheck prop_apila_no_es_vacia
-- +++ OK, passed 100 tests.
import Test.QuickCheck
quickCheck prop_cima_apila
quickCheck prop_desapila_apila
quickCheck prop_vacia_esta_vacia
quickCheck prop_apila_no_es_vacia
+++ OK, passed 100 tests.
+++ OK, passed 100 tests.
+++ OK, passed 1 test.
+++ OK, passed 100 tests.
Nota Se borran los ficheros de los módulos usados
:! rm -f *.hs *.hi *.o *.dyn_*