Tema 14: El TAD de las pilas

1 Tipos abstractos de datos

1.1 Abstracción y tipos abstractos de datos

Abstracción y tipos abstractos de datos

2 Especificación del TAD de las pilas

2.1 Signatura del TAD pilas

Descripción informal de las pilas

Signatura del TAD de las pilas

vacia    :: Pila a
apila    :: a -> Pila a -> Pila a
cima     :: Pila a -> a
desapila :: Pila a -> Pila a
esVacia  :: Pila a -> Bool

2.2 Propiedades del TAD de las pilas

Propiedades de las pilas

3 Implementaciones del TAD de las pilas

3.1 Las pilas como tipos de datos algebraicos

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
data Pila a = Vacia | P a (Pila a)
              deriving Eq
instance (Show a) => Show (Pila a) where
    showsPrec p Vacia cad   = showChar '-' cad
    showsPrec p (P x s) cad = 
       shows x (showChar '|' (shows s cad))
p1 :: Pila Int
p1 = apila 1 (apila 2 (apila 3 vacia))
ghci> p1
1|2|3|-
ghci> vacia
-
vacia :: Pila a
vacia = Vacia
apila 4 p1  =>  4|1|2|3|-
apila :: a -> Pila a -> Pila a
apila x p = P x p
cima p1  ==  1
cima :: Pila a -> a
cima Vacia   = error "cima: pila vacia"
cima (P x _) =  x
desapila p1  =>  2|3|-
desapila :: Pila a -> Pila a
desapila Vacia   = error "desapila: pila vacia"
desapila (P _ p) = p
esVacia p1     ==  False
esVacia vacia  ==  True
esVacia :: Pila a -> Bool
esVacia Vacia = True
esVacia _     = False

3.2 Las pilas como listas

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
newtype Pila a = P [a]
    deriving Eq
instance (Show a) => Show (Pila a) where
    showsPrec p (P [])     cad = showChar '-' cad
    showsPrec p (P (x:xs)) cad
        = shows x (showChar '|' (shows (P xs) cad))
ghci> p1
1|2|3|-
p1 = apila 1 (apila 2 (apila 3 vacia))    
ghci> vacia
-
vacia   :: Pila a
vacia = P []
apila 4 p1  =>  4|1|2|3|-|
apila :: a -> Pila a -> Pila a
apila x (P xs) = P (x:xs)
cima p1  ==  1
cima :: Pila a -> a
cima (P (x:_)) = x
cima (P [])    = error "cima de la pila vacia"
desapila p1  =>  2|3|-
desapila :: Pila a -> Pila a
desapila (P [])     = error "desapila la pila vacia"
desapila (P (_:xs)) = P  xs
esVacia p1     ==  False
esVacia vacia  ==  True
esVacia :: Pila a -> Bool
esVacia (P xs) = null xs

4 Comprobación de las implementaciones con QuickCheck

4.1 Librerías auxiliares

Importación de librerías

import PilaConTipoDeDatoAlgebraico
-- import PilaConListas
import Test.QuickCheck
import Test.Framework
import Test.Framework.Providers.QuickCheck2

4.2 Generador de pilas

ghci> sample genPila
0|0|-
-6|4|-3|3|0|-
-
9|5|-1|-3|0|-8|-5|-7|2|-
...
genPila :: (Num a, Arbitrary a) => Gen (Pila a)
genPila = do xs <- listOf arbitrary
             return (foldr apila vacia xs)

instance (Arbitrary a, Num a) => Arbitrary (Pila a) where
    arbitrary = genPila

4.3 Especificación de las propiedades de las pilas

prop_cima_apila :: Int -> Pila Int -> Bool
prop_cima_apila x p = 
    cima (apila x p) == x
prop_desapila_apila :: Int -> Pila Int -> Bool
prop_desapila_apila x p = 
    desapila (apila x p) == p
prop_vacia_esta_vacia :: Bool
prop_vacia_esta_vacia = 
    esVacia vacia
prop_apila_no_es_vacia :: Int -> Pila Int -> Bool
prop_apila_no_es_vacia x p = 
    not (esVacia (apila x p))

4.4 Comprobación de las propiedades

Definición del procedimiento de comprobación

compruebaPropiedades = 
    defaultMain 
        [testGroup "Propiedades del TAD pilas"
          [testProperty "P1" prop_cima_apila,
           testProperty "P2" prop_desapila_apila,
           testProperty "P3" prop_vacia_esta_vacia,
           testProperty "P4" prop_apila_no_es_vacia]]

Comprobación de las propiedades de las pilas

ghci> compruebaPropiedades
Propiedades del TAD pilas:
  P1: [OK, passed 100 tests]
  P2: [OK, passed 100 tests]
  P3: [OK, passed 100 tests]
  P4: [OK, passed 100 tests]

         Properties  Total      
 Passed  4           4          
 Failed  0           0          
 Total   4           4      

5 Referencias



Universidad de Sevilla

José A. Alonso Jiménez
Grupo de Lógica Computacional
Dpto. de Ciencias de la Computación e I.A.
Universidad de Sevilla