Tema 15: El TAD de las colas

1 Especificación del TAD de las colas

1.1 Signatura del TAD de las colas

Descripción informal de las colas

Signatura del TAD colas

vacia   :: Cola a
inserta :: a -> Cola a -> Cola a
primero :: Cola a -> a
resto   :: Cola a -> Cola a
esVacia :: Cola a -> Bool
valida  :: Cola a -> Bool

1.2 Propiedades del TAD de las colas

Propiedades del TAD de las colas

2 Implementaciones del TAD de las colas

2.1 Implementación de las colas mediante listas

module ColaConListas 
    (Cola,
     vacia,   -- Cola a
     inserta, -- a -> Cola a -> Cola a
     primero, -- Cola a -> a
     resto,   -- Cola a -> Cola a
     esVacia, -- Cola a -> Bool
     valida   -- Cola a -> Bool
    ) where
newtype Cola a = C [a] deriving (Show, Eq)
ghci> c1
C [10,9,8,7,6,5,4,3,2,1]
c1 = foldr inserta vacia [1..10]
ghci> vacia
C []
vacia :: Cola a
vacia = C []
inserta 12 c1  ==  C [10,9,8,7,6,5,4,3,2,1,12]
inserta :: a -> Cola a -> Cola a
inserta x (C c) = C (c ++ [x])
primero c1  ==  10
primero :: Cola a -> a
primero (C (x:_)) = x
primero (C [])    = error "primero: cola vacia"
resto c1  ==  C [9,8,7,6,5,4,3,2,1]
resto :: Cola a -> Cola a
resto (C (_:xs)) = C xs
resto (C [])     = error "resto: cola vacia"
esVacia c1     ==  False
esVacia vacia  ==  True
esVacia :: Cola a -> Bool
esVacia (C xs)  = null xs
valida :: Cola a -> Bool
valida c = True

2.2 Implementación de las colas mediante pares de listas

Las colas como pares de listas

Implementación de las colas como pares de listas

module ColaConDosListas
    (Cola,
     vacia,   -- Cola a
     inserta, -- a -> Cola a -> Cola a
     primero, -- Cola a -> a
     resto,   -- Cola a -> Cola a
     esVacia, -- Cola a -> Bool
     valida   -- Cola a -> Bool
    ) where
newtype Cola a = C ([a],[a])
valida (C ([2],[5]))  ==  True
valida (C ([2],[]))   ==  True
valida (C ([],[5]))   ==  False
valida:: Cola a -> Bool
valida (C (xs,ys)) = not (null xs) || null ys
instance Show a => Show (Cola a) where
    showsPrec p (C (xs,ys)) cad
        = showString "C " (showList (xs ++ (reverse ys)) cad)
ghci> c1
C [10,9,8,7,6,5,4,3,2,1]
c1 :: Cola Int
c1 = foldr inserta vacia [1..10]
ghci> c1
C [10,9,8,7,6,5,4,3,2,1]
vacia :: Cola a
vacia  = C ([],[])
inserta 12 c1  ==  C [10,9,8,7,6,5,4,3,2,1,12]
inserta :: a -> Cola a -> Cola a
inserta y (C (xs,ys)) = C (normaliza (xs,y:ys))
normaliza ([],[2,5,3])   ==  ([3,5,2],[])
normaliza ([4],[2,5,3])  ==  ([4],[2,5,3])
normaliza :: ([a],[a]) -> ([a],[a])
normaliza ([], ys) = (reverse ys, [])
normaliza p        = p
primero c1  ==  10
primero  :: Cola a -> a
primero (C (x:xs,ys)) = x
primero _             = error "primero: cola vacia"
resto c1  ==  C [9,8,7,6,5,4,3,2,1]
resto  :: Cola a -> Cola a
resto (C (x:xs,ys)) = C (normaliza (xs,ys))
resto (C ([],[]))   = error "resto: cola vacia"
esVacia c1     ==  False
esVacia vacia  ==  True
esVacia :: Cola a -> Bool
esVacia (C (xs,_)) = null xs
elementos (C ([3,2],[5,4,7]))  ==  [3,2,7,4,5]
elementos:: Cola a -> [a]
elementos (C (xs,ys)) = xs ++ (reverse ys)
ghci> igualColas (C ([3,2],[5,4,7])) (C ([3],[5,4,7,2]))   
True
ghci> igualColas (C ([3,2],[5,4,7])) (C ([],[5,4,7,2,3]))  
False
igualColas c1 c2 = 
    valida c1 && valida c2 && 
    elementos c1 == elementos c2

3 Comprobación de las implementaciones con QuickCheck

3.1 Librerías auxiliares

Importación de librerías

import ColaConListas
-- import ColaConDosListas
import Data.List
import Test.QuickCheck
import Test.Framework
import Test.Framework.Providers.QuickCheck2

3.2 Generador de colas

ghci> sample genCola
C ([7,8,4,3,7],[5,3,3])
C ([1],[13])
...
genCola :: Gen (Cola Int)
genCola = frequency [(1, return vacia),
                     (30, do n <- choose (10,100)
                             xs <- vectorOf n arbitrary
                             return (creaCola xs))]
          where creaCola = foldr inserta vacia

instance Arbitrary (Cola Int) where
    arbitrary = genCola

Corrección del generador de colas

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

3.3 Especificación de las propiedades de las colas

prop_primero_inserta_vacia :: Int -> Bool
prop_primero_inserta_vacia x = 
    primero (inserta x vacia) == x
prop_primero_inserta_no_vacia :: Cola Int -> Int -> Int 
                                 -> Bool
prop_primero_inserta_no_vacia c x y =
    primero (inserta x c') == primero c'
    where c' = inserta y vacia
prop_resto_inserta_vacia :: Int -> Bool
prop_resto_inserta_vacia x = 
    resto (inserta x vacia) == vacia
prop_resto_inserta_en_no_vacia :: Cola Int -> Int -> Int 
                                  -> Bool
prop_resto_inserta_en_no_vacia c x y =
    resto (inserta x c') == inserta x (resto c')
    where c' = inserta y c
prop_vacia_es_vacia :: Bool
prop_vacia_es_vacia = 
    esVacia vacia
prop_inserta_no_es_vacia :: Int -> Cola Int -> Bool
prop_inserta_no_es_vacia x c = 
    not (esVacia (inserta x c))
prop_valida_vacia :: Bool
prop_valida_vacia = valida vacia
prop_valida_inserta :: Cola Int -> Int -> Property
prop_valida_inserta c x =
    valida c ==> valida (inserta x c)
prop_valida_resto :: Cola Int -> Property
prop_valida_resto c =
    valida c && not (esVacia c) ==> valida (resto c)

3.4 Comprobación de las propiedades

Definición del procedimiento de comprobación

compruebaPropiedades = 
    defaultMain 
        [testGroup "Propiedades del TAD cola"
        [testGroup "Propiedades del TAD cola"
          [testProperty "P1" prop_primero_inserta_vacia,
           testProperty "P2" prop_primero_inserta_no_vacia,
           testProperty "P3" prop_resto_inserta_vacia,
           testProperty "P4" prop_resto_inserta_en_no_vacia,
           testProperty "P5" prop_vacia_es_vacia,
           testProperty "P6" prop_inserta_no_es_vacia,
           testProperty "P7" prop_valida_vacia,
           testProperty "P8" prop_valida_inserta,
           testProperty "P9" prop_valida_resto]]

Comprobación de las propiedades de las colas

ghci> compruebaPropiedades
Propiedades del TAD cola
  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]
  P8: [OK, passed 100 tests]
  P9: [OK, passed 100 tests]

         Properties  Total      
 Passed  9           9          
 Failed  0           0          
 Total   9           9     

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