Tema 16: El TAD de las colas de prioridad

1 Especificación del TAD de las colas de prioridad

1.1 Signatura del TAD colas de prioridad

Descripción de las colas de prioridad

Signatura de las colas de prioridad

vacia,   :: Ord a => CPrioridad a 
inserta, :: Ord a => a -> CPrioridad a -> CPrioridad a 
primero, :: Ord a => CPrioridad a -> a
resto,   :: Ord a => CPrioridad a -> CPrioridad a
esVacia, :: Ord a => CPrioridad a -> Bool 
valida   :: Ord a => CPrioridad a -> Bool

1.2 Propiedades del TAD de las colas de prioridad

2 Implementaciones del TAD de las colas de prioridad

2.1 Las colas de prioridad como listas

module ColaDePrioridadConListas
    (CPrioridad,
     vacia,   -- Ord a => CPrioridad a 
     inserta, -- Ord a => a -> CPrioridad a -> CPrioridad a 
     primero, -- Ord a => CPrioridad a -> a
     resto,   -- Ord a => CPrioridad a -> CPrioridad a
     esVacia, -- Ord a => CPrioridad a -> Bool 
     valida   -- Ord a => CPrioridad a -> Bool
    ) where
newtype CPrioridad a = CP [a]
    deriving (Eq, Show)
cp1  == CP [1,2,3,7,9]
cp1 :: CPrioridad Int
cp1 = foldr inserta vacia [3,1,7,2,9]
valida (CP [1,3,5])  ==  True
valida (CP [1,5,3])  ==  False
valida :: Ord a => CPrioridad a -> Bool
valida (CP xs) = ordenada xs
    where ordenada (x:y:zs) = x <= y && ordenada (y:zs)
          ordenada _        = True
vacia  ==  CP []
vacia :: Ord a => CPrioridad a 
vacia = CP []
cp1            ==  CP [1,2,3,7,9]
inserta 5 cp1  ==  CP [1,2,3,5,7,9]
inserta :: Ord a => a -> CPrioridad a -> CPrioridad a 
inserta x (CP q) = CP (ins x q)
    where ins x []                   = [x]
          ins x r@(e:r') | x < e     = x:r
                         | otherwise = e:ins x r'
cp1          ==  CP [1,2,3,7,9]
primero cp1  ==  1
primero :: Ord a => CPrioridad a -> a
primero (CP(x:_)) = x
primero _         = error "primero: cola vacia"
cp1        ==  CP [1,2,3,7,9]
resto cp1  ==  CP [2,3,7,9]
resto :: Ord a => CPrioridad a -> CPrioridad a
resto (CP (_:xs)) = CP xs
resto _           = error "resto: cola vacia"
esVacia cp1    ==  False
esVacia vacia  ==  True
esVacia :: Ord a => CPrioridad a -> Bool 
esVacia (CP xs) = null xs

2.2 Las colas de prioridad como montículos

La implementación de las colas de prioridad como montículos (ColaDePrioridadConMonticulos.hs) se encuentra en en el tema 20 (El TAD de los montículos).

3 Comprobación de las implementaciones con QuickCheck

3.1 Librerías auxiliares

import ColaDePrioridadConListas
-- ColaDePrioridadConMonticulos.hs
import Test.QuickCheck
import Test.Framework
import Test.Framework.Providers.QuickCheck2

3.2 Generador de colas de prioridad

ghci> sample genCPrioridad
CP [-4]
CP [-2,-1,-1,2,5]
...
genCPrioridad :: (Arbitrary a, Num a, Ord a) 
                 =>  Gen (CPrioridad a)
genCPrioridad = do xs <- listOf arbitrary
                   return (foldr inserta vacia xs)

instance (Arbitrary a, Num a, Ord a) 
         => Arbitrary (CPrioridad a) where
    arbitrary = genCPrioridad

Corrección del generador de colas de prioridad

prop_genCPrioridad_correcto ::  CPrioridad Int -> Bool
prop_genCPrioridad_correcto c = valida c
ghci> quickCheck prop_genCPrioridad_correcto
+++ OK, passed 100 tests.

3.3 Especificación de las propiedades de las colas de prioridad

prop_inserta_conmuta :: Int -> Int -> CPrioridad Int 
                        -> Bool
prop_inserta_conmuta x y c =
    inserta x (inserta y c) == inserta y (inserta x c)
prop_primero_inserta_vacia :: Int -> CPrioridad Int -> Bool
prop_primero_inserta_vacia x c =
    primero (inserta x vacia) == x
prop_primero_inserta :: Int -> Int -> CPrioridad Int 
                        -> Property
prop_primero_inserta x y c =
    x <= y ==> 
    primero (inserta y c') == primero c'
    where c' = inserta x c
prop_resto_inserta_vacia :: Int -> Bool
prop_resto_inserta_vacia x =
    resto (inserta x vacia) == vacia
prop_resto_inserta :: Int -> Int -> CPrioridad Int 
                      -> Property
prop_resto_inserta x y c =
    x <= y ==> 
    resto (inserta y c') == inserta y (resto c')
    where c' = inserta x c
prop_vacia_es_vacia :: Bool
prop_vacia_es_vacia = esVacia (vacia :: CPrioridad Int)
prop_inserta_no_es_vacia :: Int -> CPrioridad Int 
                            -> Bool
prop_inserta_no_es_vacia x c =
    not (esVacia (inserta x c))

3.4 Comprobación de las propiedades

Definición del procedimiento de comprobación

compruebaPropiedades = 
    defaultMain 
        [testGroup "Corrección del generador" 
          [testProperty "P0" prop_genCPrioridad_correcto],
         testGroup "Propiedades de colas de prioridad:"
          [testProperty "P1" prop_inserta_conmuta,
           testProperty "P2" prop_primero_inserta_vacia,
           testProperty "P3" prop_primero_inserta,
           testProperty "P4" prop_resto_inserta_vacia,
           testProperty "P5" prop_resto_inserta,
           testProperty "P6" prop_vacia_es_vacia,
           testProperty "P7" prop_inserta_no_es_vacia]]

Comprobación de las propiedades de las colas de prioridad

ghci> compruebaPropiedades
Corrección del generador:
  P0: [OK, passed 100 tests]
Propiedades de colas de prioridad:
  P1: [OK, passed 100 tests]
  P2: [OK, passed 100 tests]
  P3: [OK, passed 100 tests]
  P4: [OK, passed 100 tests]
  P5: [OK, passed 100 tests]
  P6: [OK, passed 100 tests]
  P7: [OK, passed 100 tests]

         Properties  Total      
 Passed  8           8          
 Failed  0           0          
 Total   8           8  

4 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