El tipo abstracto de datos de las colas en Haskell

En este artículo continúo la serie dedicada a los tipos de datos abstractos (TAD) en Haskell presentando el TAD de las colas.

Al igual que hice en los anteriores TAD, usaré módulos, funciones de escritura y QuickCheck para conseguir la abstracción, independencia y certificación de los resultados de las implementaciones.

Una cola es una estructura de datos, caracterizada por ser una secuencia de elementos en la que la operación de inserción se realiza por un extremo (el posterior o final) y la operación de extracción por el otro (el anterior o frente). Las colas también se llaman estructuras FIFO (del inglés First In First Out), debido a que el primer elemento en entrar será también el primero en salir. Este comportamiento es análogo a las colas del cine.

El contenido del resto del artículo es el siguiente:

la signatura del TAD de las colas;
las propiedades del TAD de las colas;
la implementación, en Haskell, de las colas mediante listas;
la implementación, en Haskell, de las colas mediante pares de listas y
la comprobación con QuickCheck de sus propiedades.

La signatura del TAD de las colas

Las signatura de las operaciones del TAD de las colas son las siguientes:

colaVacia   :: Cola a
encolar     :: a -> Cola a -> Cola a
cabeza      :: Cola a -> a
desencolar  :: Cola a -> Cola a
esColaVacia :: Cola a -> Bool
valida      :: Cola a -> Bool

colaVacia :: Cola a

encolar :: a -> Cola a -> Cola a

cabeza :: Cola a -> a

desencolar :: Cola a -> Cola a

esColaVacia :: Cola a -> Bool

valida :: Cola a -> Bool

con el siguiente significado

colaVacia es la cola vacía.
(encolar x c) es la cola obtenida añadiendo el elemento x al final de la cola c.
(cabeza c) es la cabeza de la cola c.
(desencolar c) es la cola obtenida eliminando la cabeza de la cola c.
(esColaVacia c) se verifica si c es la cola vacía.
(valida c) se verifica si c representa una cola válida.

Propiedades del TAD de las colas

Las propiedades son las siguientes:

cabeza (encolar x colaVacia) == x
Si c es una cola no vacía, entonces cabeza (encolar x c) == cabeza c,
desencolar (encolar x colaVacia) == colaVacia
Si c es una cola no vacía, entonces desencolar (encolar x c) == encolar x (desencolar c)
esColaVacia colaVacia
not (esColaVacia (encolar x c))

ColaConListas.hs: 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

-- Colas como listas:
newtype Cola a = C [a]
    deriving (Show, Eq)

-- Ejemplo de cola
--    ghci> c1
--    C [10,9,8,7,6,5,4,3,2,1]
c1 = foldr inserta vacia [1..10]

-- vacia es la cola vacía. Por ejemplo,
--    ghci> vacia
--    C []
vacia :: Cola a
vacia = C []

-- (inserta x c) es la cola obtenida añadiendo x al final de la cola
-- c. Por ejemplo,
--    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])

-- Nota: La operación inserta usa O(n) pasos.

-- (primero c) es el primer elemento de la cola c. Por ejemplo,
--    primero c1  ==  10
primero :: Cola a -> a
primero (C (x:_)) = x
primero (C [])    = error "primero: cola vacia"

-- (resto c) es la cola obtenida eliminando el primer elemento de la
-- cola c. Por ejemplo,
--    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 c) se verifica si c es la cola vacía. Por ejemplo,
--    esVacia c1     ==  False
--    esVacia vacia  ==  True
esVacia :: Cola a -> Bool
esVacia (C xs)  = null xs

-- (valida c) se verifica si c representa una cola válida. Con esta
-- representación, todas las colas son válidas.
valida :: Cola a -> Bool
valida c = True

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

-- Colas como listas:

newtype Cola a = C [a]

deriving (Show, Eq)

-- Ejemplo de cola

-- ghci> c1

-- C [10,9,8,7,6,5,4,3,2,1]

c1 = foldr inserta vacia [1..10]

-- vacia es la cola vacía. Por ejemplo,

-- ghci> vacia

-- C []

vacia :: Cola a

vacia = C []

-- (inserta x c) es la cola obtenida añadiendo x al final de la cola

-- c. Por ejemplo,

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

-- Nota: La operación inserta usa O(n) pasos.

-- (primero c) es el primer elemento de la cola c. Por ejemplo,

-- primero c1 == 10

primero :: Cola a -> a

primero (C (x:_)) = x

primero (C []) = error "primero: cola vacia"

-- (resto c) es la cola obtenida eliminando el primer elemento de la

-- cola c. Por ejemplo,

-- 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 c) se verifica si c es la cola vacía. Por ejemplo,

-- esVacia c1 == False

-- esVacia vacia == True

esVacia :: Cola a -> Bool

esVacia (C xs) = null xs

-- (valida c) se verifica si c representa una cola válida. Con esta

-- representación, todas las colas son válidas.

valida :: Cola a -> Bool

valida c = True

ColaConDosListas.hs: Implementación de las colas mediante dos listas

En esta implementación, una cola c se representa mediante un par de listas (xs,ys) de modo que los elementos de c son, en ese orden, los elementos de la lista xs++(reverse ys).

Al dividir la lista en dos parte e invertir la segunda de ellas, esperamos hacer más eficiente las operaciones sobre las colas.

Impondremos también una restricción adicional sobre la representación: las colas serán representadas mediante pares (xs,ys) tales que si xs es vacía, entonces ys será también vacía. Esta restricción ha de mantenerse por los programas que crean colas.

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

-- Las colas como pares listas.
newtype Cola a = C ([a],[a])
    -- deriving Show

-- Procedimiento de escritura de colas como pares de listas.
instance (Show a) => Show (Cola a) where
    showsPrec p (C (xs,ys)) cad
        = showString "C " (showList (xs ++ ys) cad)

-- Ejemplo de cola: c1 es la cola obtenida añadiéndole a la cola 
-- vacía los números del 1 al 10. Por ejemplo,
--    ghci> c1
--    C [10,9,8,7,6,5,4,3,2,1]
c1 :: Cola Int
c1 = foldr inserta vacia [1..10]

-- vacia es la cola vacía. Por ejemplo,
--    ghci> vacia
--    C []
vacia :: Cola a
vacia  = C ([],[])

-- (inserta x c) es la cola obtenida añadiendo x al final de la cola
-- c. Por ejemplo,
--    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 p) es la cola obtenida al normalizar el par de listas
-- p. Por ejemplo,  
--    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 c) es el primer elemento de la cola c. Por ejemplo,
--    primero c1  ==  10
primero  :: Cola a -> a
primero (C (x:xs,ys)) = x
primero _             = error "primero: cola vacia"

-- (resto c) es la cola obtenida eliminando el primer elemento de la
-- cola c. Por ejemplo,
--    resto c1  ==  C [9,8,7,6,5,4,3,2,1]
resto  :: Cola a -> Cola a
resto (C ([],[]))   = error "resto: cola vacia"
resto (C (x:xs,ys)) = C (normaliza (xs,ys))

-- (esVacia c) se verifica si c es la cola vacía. Por ejemplo,
--    esVacia c1     ==  False
--    esVacia vacia  ==  True
esVacia :: Cola a -> Bool
esVacia (C (xs,_)) = null xs

-- (valida c) se verifica si la cola c es válida; es decir, si
-- su primer elemento es vacío entonces también lo es el segundo. Por
-- ejemplo, 
--    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

-- ---------------------------------------------------------------------
-- Igualdad de colas                                                  --
-- ---------------------------------------------------------------------

-- (elementos c) es la lista de los elementos de la cola c en el orden de
-- la cola. Por ejemplo, 
--    elementos (C ([3,2],[5,4,7]))  ==  [3,2,7,4,5]
elementos:: Cola a -> [a]
elementos (C (xs,ys)) = xs ++ (reverse ys)

-- (igualColas c1 c2) se verifica si las colas c1 y c2 son iguales. Por
-- ejemplo, 
--    igualColas (C ([3,2],[5,4,7])) (C ([3],[5,4,7,2]))   ==  True
--    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

instance (Eq a) => Eq (Cola a) where
    (==) = igualColas

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

-- Las colas como pares listas.

newtype Cola a = C ([a],[a])

-- deriving Show

-- Procedimiento de escritura de colas como pares de listas.

instance (Show a) => Show (Cola a) where

showsPrec p (C (xs,ys)) cad

= showString "C " (showList (xs ++ ys) cad)

-- Ejemplo de cola: c1 es la cola obtenida añadiéndole a la cola

-- vacía los números del 1 al 10. Por ejemplo,

-- ghci> c1

-- C [10,9,8,7,6,5,4,3,2,1]

c1 :: Cola Int

c1 = foldr inserta vacia [1..10]

-- vacia es la cola vacía. Por ejemplo,

-- ghci> vacia

-- C []

vacia :: Cola a

vacia = C ([],[])

-- (inserta x c) es la cola obtenida añadiendo x al final de la cola

-- c. Por ejemplo,

-- 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 p) es la cola obtenida al normalizar el par de listas

-- p. Por ejemplo,

-- 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 c) es el primer elemento de la cola c. Por ejemplo,

-- primero c1 == 10

primero :: Cola a -> a

primero (C (x:xs,ys)) = x

primero _ = error "primero: cola vacia"

-- (resto c) es la cola obtenida eliminando el primer elemento de la

-- cola c. Por ejemplo,

-- resto c1 == C [9,8,7,6,5,4,3,2,1]

resto :: Cola a -> Cola a

resto (C ([],[])) = error "resto: cola vacia"

resto (C (x:xs,ys)) = C (normaliza (xs,ys))

-- (esVacia c) se verifica si c es la cola vacía. Por ejemplo,

-- esVacia c1 == False

-- esVacia vacia == True

esVacia :: Cola a -> Bool

esVacia (C (xs,_)) = null xs

-- (valida c) se verifica si la cola c es válida; es decir, si

-- su primer elemento es vacío entonces también lo es el segundo. Por

-- ejemplo,

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

-- ---------------------------------------------------------------------

-- Igualdad de colas --

-- ---------------------------------------------------------------------

-- (elementos c) es la lista de los elementos de la cola c en el orden de

-- la cola. Por ejemplo,

-- elementos (C ([3,2],[5,4,7])) == [3,2,7,4,5]

elementos:: Cola a -> [a]

elementos (C (xs,ys)) = xs ++ (reverse ys)

-- (igualColas c1 c2) se verifica si las colas c1 y c2 son iguales. Por

-- ejemplo,

-- igualColas (C ([3,2],[5,4,7])) (C ([3],[5,4,7,2])) == True

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

instance (Eq a) => Eq (Cola a) where

(==) = igualColas

Propiedades de las colas

-- Nota: Necesita framework que está en http://goo.gl/8psHc

{-# LANGUAGE FlexibleInstances #-}

-- Hay que elegir una implementación del TAD colas:
import ColaConListas
-- import ColaConDosListas

import Data.List
import Test.Framework (defaultMain, testGroup)
import Test.Framework.Providers.QuickCheck2 (testProperty)
import Test.QuickCheck

-- ---------------------------------------------------------------------
-- Generador de colas                                          --
-- ---------------------------------------------------------------------

-- genCola es un generador de colas de enteros. Por ejemplo,
--    ghci> sample genCola
--    C ([],[])
--    C ([],[])
--    C ([],[])
--    C ([],[])
--    C ([7,8,4,3,7],[5,3,3])
--    C ([],[])
--    C ([1],[13])
--    C ([18,28],[12,21,28,28,3,18,14])
--    C ([47],[64,45,7])
--    C ([8],[])
--    C ([42,112,178,175,107],[])
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

-- El tipo pila es una instancia del arbitrario.
instance Arbitrary (Cola Int) where
    arbitrary = genCola

-- Propiedad. Todo los elementos generados por genCola son colas
-- válidas. 
prop_genCola_correcto :: Cola Int -> Bool
prop_genCola_correcto c = valida c

-- Comprobación.
--    ghci> quickCheck prop_genCola_correcto
--    +++ OK, passed 100 tests.

-- ---------------------------------------------------------------------
-- Propiedades
-- ---------------------------------------------------------------------

-- Propiedad. El primero de la cola obtenida añadiendo x a la cola vacía
-- es x. 
prop_primero_inserta_vacia :: Int -> Bool
prop_primero_inserta_vacia x = 
    primero (inserta x vacia) == x

-- Comprobación.
--    > quickCheck prop_primero_inserta_vacia
--    +++ OK, passed 100 tests.

-- Propiedad. Si una cola no está vacía, su primer elemento no varía al
-- añadirle un elemento. 
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

-- Comprobación.
--    > quickCheck prop_primero_inserta_no_vacia
--    +++ OK, passed 100 tests.

-- Propiedad. El resto de la cola obtenida insertando un elemento en la
-- cola vacía es la cola vacía.  
prop_resto_inserta_vacia :: Int -> Bool
prop_resto_inserta_vacia x = 
    resto (inserta x vacia) == vacia

-- Comprobación.
--    > quickCheck prop_resto_inserta_vacia
--    +++ OK, passed 100 tests.

-- Propiedad. Las operaciones de inserta y resto conmutan.
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

-- Comprobación.
--    > quickCheck prop_resto_inserta_en_no_vacia
--    +++ OK, passed 100 tests.

-- Propiedad. vacia es una cola vacía.
prop_vacia_es_vacia :: Bool
prop_vacia_es_vacia = 
    esVacia vacia

-- Comprobación.
--    > quickCheck prop_vacia_es_vacia
--    +++ OK, passed 100 tests.

-- Propiedad. La cola obtenida insertando un elemento no es vacía.
prop_inserta_no_es_vacia :: Int -> Cola Int -> Bool
prop_inserta_no_es_vacia x c = 
    not (esVacia (inserta x c))

-- Comprobación
--    > quickCheck prop_inserta_no_es_vacia
--    +++ OK, passed 100 tests.

-- ---------------------------------------------------------------------
-- Propiedades de la normalización                                    --
-- ---------------------------------------------------------------------

-- Propiedad. La cola vacía es válida.
prop_valida_vacia :: Bool
prop_valida_vacia = valida vacia

-- Comprobación
--    ghci> quickCheck prop_valida_vacia
--    +++ OK, passed 100 tests.

-- Propiedad. Al añadirle un elemento a una cola válida se obtiene otra
-- cola válida. 
prop_valida_inserta :: Cola Int -> Int -> Property
prop_valida_inserta c x =
    valida c ==> valida (inserta x c)

-- Comprobación.
--    ghci> quickCheck prop_valida_inserta
--    +++ OK, passed 100 tests.

-- Propiedad. El resto de una cola válida y no vacía es una cola válida. 
prop_valida_resto :: Cola Int -> Property
prop_valida_resto c =
    valida c && not (esVacia c) ==> valida (resto c)

-- Comprobación
--    *Main> quickCheck prop_valida_resto
--    +++ OK, passed 100 tests.

-- compruebaPropiedades comprueba todas las propiedades con la
-- plataforma de verificación. Por ejemplo,
--    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]
--    Propiedades de validez:
--      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     
compruebaPropiedades = 
    defaultMain 
        [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],
         testGroup "Propiedades de normalizacion" 
          [testProperty "P7" prop_valida_vacia,
           testProperty "P8" prop_valida_inserta,
           testProperty "P9" prop_valida_resto]]

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

-- Nota: Necesita framework que está en http://goo.gl/8psHc

{-# LANGUAGE FlexibleInstances #-}

-- Hay que elegir una implementación del TAD colas:

import ColaConListas

-- import ColaConDosListas

import Data.List

import Test.Framework (defaultMain, testGroup)

import Test.Framework.Providers.QuickCheck2 (testProperty)

import Test.QuickCheck

-- ---------------------------------------------------------------------

-- Generador de colas --

-- ---------------------------------------------------------------------

-- genCola es un generador de colas de enteros. Por ejemplo,

-- ghci> sample genCola

-- C ([],[])

-- C ([7,8,4,3,7],[5,3,3])

-- C ([],[])

-- C ([1],[13])

-- C ([18,28],[12,21,28,28,3,18,14])

-- C ([47],[64,45,7])

-- C ([8],[])

-- C ([42,112,178,175,107],[])

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

-- El tipo pila es una instancia del arbitrario.

instance Arbitrary (Cola Int) where

arbitrary = genCola

-- Propiedad. Todo los elementos generados por genCola son colas

-- válidas.

prop_genCola_correcto :: Cola Int -> Bool

prop_genCola_correcto c = valida c

-- Comprobación.

-- ghci> quickCheck prop_genCola_correcto

-- +++ OK, passed 100 tests.

-- ---------------------------------------------------------------------

-- Propiedades

-- ---------------------------------------------------------------------

-- Propiedad. El primero de la cola obtenida añadiendo x a la cola vacía

-- es x.

prop_primero_inserta_vacia :: Int -> Bool

prop_primero_inserta_vacia x =

primero (inserta x vacia) == x

-- Comprobación.

-- > quickCheck prop_primero_inserta_vacia

-- +++ OK, passed 100 tests.

-- Propiedad. Si una cola no está vacía, su primer elemento no varía al

-- añadirle un elemento.

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

-- Comprobación.

-- > quickCheck prop_primero_inserta_no_vacia

-- +++ OK, passed 100 tests.

-- Propiedad. El resto de la cola obtenida insertando un elemento en la

-- cola vacía es la cola vacía.

prop_resto_inserta_vacia :: Int -> Bool

prop_resto_inserta_vacia x =

resto (inserta x vacia) == vacia

-- Comprobación.

-- > quickCheck prop_resto_inserta_vacia

-- +++ OK, passed 100 tests.

-- Propiedad. Las operaciones de inserta y resto conmutan.

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

-- Comprobación.

-- > quickCheck prop_resto_inserta_en_no_vacia

-- +++ OK, passed 100 tests.

-- Propiedad. vacia es una cola vacía.

prop_vacia_es_vacia :: Bool

prop_vacia_es_vacia =

esVacia vacia

-- Comprobación.

-- > quickCheck prop_vacia_es_vacia

-- +++ OK, passed 100 tests.

-- Propiedad. La cola obtenida insertando un elemento no es vacía.

prop_inserta_no_es_vacia :: Int -> Cola Int -> Bool

prop_inserta_no_es_vacia x c =

not (esVacia (inserta x c))

-- Comprobación

-- > quickCheck prop_inserta_no_es_vacia

-- +++ OK, passed 100 tests.

-- ---------------------------------------------------------------------

-- Propiedades de la normalización --

-- ---------------------------------------------------------------------

-- Propiedad. La cola vacía es válida.

prop_valida_vacia :: Bool

prop_valida_vacia = valida vacia

-- Comprobación

-- ghci> quickCheck prop_valida_vacia

-- +++ OK, passed 100 tests.

-- Propiedad. Al añadirle un elemento a una cola válida se obtiene otra

-- cola válida.

prop_valida_inserta :: Cola Int -> Int -> Property

prop_valida_inserta c x =

valida c ==> valida (inserta x c)

-- Comprobación.

-- ghci> quickCheck prop_valida_inserta

-- +++ OK, passed 100 tests.

-- Propiedad. El resto de una cola válida y no vacía es una cola válida.

prop_valida_resto :: Cola Int -> Property

prop_valida_resto c =

valida c && not (esVacia c) ==> valida (resto c)

-- Comprobación

-- *Main> quickCheck prop_valida_resto

-- +++ OK, passed 100 tests.

-- compruebaPropiedades comprueba todas las propiedades con la

-- plataforma de verificación. Por ejemplo,

-- 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]

-- Propiedades de validez:

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

compruebaPropiedades =

defaultMain

[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],

testGroup "Propiedades de normalizacion"

[testProperty "P7" prop_valida_vacia,

testProperty "P8" prop_valida_inserta,

testProperty "P9" prop_valida_resto]]

El objetivo de la serie es la elaboración de los temas de TAD del curso de Informática del Grado en Matemáticas.

La signatura del TAD de las colas

Propiedades del TAD de las colas

ColaConListas.hs: Implementación de las colas mediante listas

ColaConDosListas.hs: Implementación de las colas mediante dos listas

Propiedades de las colas

Se puede imprimir o compartir con