I1M2014: El tipo abstracto de datos de las colas de prioridad en Haskell

En la clase de hoy de Informática de 1º del Grado en Matemáticas se ha estudiado el tipo abstracto de las colas de prioridad, su implementación en Haskell mediante listas y motículos y la verificación con QuickCheck de sus propiedades características.

Las transparencias usadas en la clase son las del tema 16

El código de la implementación de las colas de prioridad mediante listas es el siguiente

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

-- Colas de prioridad mediante listas.
newtype CPrioridad a = CP [a]
    deriving (Eq, Show)

-- Ejemplo de cola de prioridad
--    ghci> cp1
--    CP [1,2,3,7,9]
cp1 :: CPrioridad Int
cp1 = foldr inserta vacia [3,1,7,2,9]

-- (valida c) se verifica si c es una cola de prioridad válida. Por
-- ejemplo, 
--    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 es la cola de prioridad vacía. Por ejemplo,
--    vacia  ==  CP []
vacia :: Ord a => CPrioridad a 
vacia = CP []

-- (inserta x c) es la cola obtenida añadiendo el elemento x a la cola
-- de prioridad c. Por ejemplo,  
--    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'

-- Nota. inserta usa O(n) pasos.

-- (primero c) es el primer elemento de la cola de prioridad c. Por
-- ejemplo, 
--    cp1          ==  CP [1,2,3,7,9]
--    primero cp1  ==  1
primero :: Ord a => CPrioridad a -> a
primero (CP(x:_)) = x
primero _         = error "primero: cola de prioridad vacia"

-- (resto c) es la cola de prioridad obtenida eliminando el primer
-- elemento de la cola de prioridad c. Por ejemplo,  
--    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 de prioridad vacia"

-- Nota. resto usa O(1) pasos.

-- (esVacia c) se verifica si la cola de prioridad c es vacía. Por
-- ejemplo,   
--    esVacia cp1    ==  False
--    esVacia vacia  ==  True
esVacia :: Ord a => CPrioridad a -> Bool 
esVacia (CP xs) = null xs

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

-- Colas de prioridad mediante listas.

newtype CPrioridad a = CP [a]

deriving (Eq, Show)

-- Ejemplo de cola de prioridad

-- ghci> cp1

-- CP [1,2,3,7,9]

cp1 :: CPrioridad Int

cp1 = foldr inserta vacia [3,1,7,2,9]

-- (valida c) se verifica si c es una cola de prioridad válida. Por

-- ejemplo,

-- 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 es la cola de prioridad vacía. Por ejemplo,

-- vacia == CP []

vacia :: Ord a => CPrioridad a

vacia = CP []

-- (inserta x c) es la cola obtenida añadiendo el elemento x a la cola

-- de prioridad c. Por ejemplo,

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

-- Nota. inserta usa O(n) pasos.

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

-- ejemplo,

-- cp1 == CP [1,2,3,7,9]

-- primero cp1 == 1

primero :: Ord a => CPrioridad a -> a

primero (CP(x:_)) = x

primero _ = error "primero: cola de prioridad vacia"

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

-- elemento de la cola de prioridad c. Por ejemplo,

-- 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 de prioridad vacia"

-- Nota. resto usa O(1) pasos.

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

-- ejemplo,

-- esVacia cp1 == False

-- esVacia vacia == True

esVacia :: Ord a => CPrioridad a -> Bool

esVacia (CP xs) = null xs

El código de la implementación de las colas de prioridad mediante listas es el siguiente

module ColaDePrioridadConMonticulos 
    (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

import qualified Monticulo as M

-- Colas de prioridad mediante montículos.
newtype CPrioridad a = CP (M.Monticulo a)
    deriving (Eq, Show)

-- Ejemplo de cola de prioridad
--    *Main> cp1
--    CP (M 1 2 
--          (M 2 2 
--             (M 9 1 VacioM VacioM) 
--             (M 7 1 VacioM VacioM)) 
--          (M 3 1 VacioM VacioM))
cp1 :: CPrioridad Int
cp1 = foldr inserta vacia [3,1,7,2,9]

-- vacia es la cola de prioridad vacía. Por ejemplo,
--    vacia  ==  CP Vacio
vacia :: Ord a => CPrioridad a 
vacia = CP M.vacio

-- (inserta x c) añade el elemento x a la cola de prioridad c. Por ejemplo, 
--    ghci> cp1
--    CP (M 1 2 
--          (M 2 2 
--             (M 9 1 VacioM VacioM) 
--             (M 7 1 VacioM VacioM)) 
--          (M 3 1 VacioM VacioM))
--    ghci> inserta 5 cp1
--    CP (M 1 2 
--          (M 2 2 
--             (M 9 1 VacioM VacioM) 
--             (M 7 1 VacioM VacioM)) 
--          (M 3 1 
--             (M 5 1 VacioM VacioM) VacioM))
inserta :: Ord a => a -> CPrioridad a -> CPrioridad a 
inserta v (CP c) = CP (M.inserta v c)

-- (primero c) es la cabeza de la cola de prioridad c. Por ejemplo,
--    primero cp1  ==  1
primero :: Ord a => CPrioridad a -> a
primero (CP c) = M.menor c

-- (resto c) elimina la cabeza de la cola de prioridad c. Por ejemplo, 
--    ghci> cp1
--    CP (M 1 2 
--          (M 2 2 
--             (M 9 1 VacioM VacioM) 
--             (M 7 1 VacioM VacioM)) 
--          (M 3 1 VacioM VacioM))
--    ghci> resto cp1
--    CP (M 2 2 
--          (M 9 1 VacioM VacioM) 
--          (M 3 1 
--             (M 7 1 VacioM VacioM) VacioM))
resto :: Ord a => CPrioridad a -> CPrioridad a
resto (CP c) = CP (M.resto c)

-- (esVacia c) se verifica si la cola de prioridad c es vacía. Por
-- ejemplo,   
--    esVacia cp1    ==  False
--    esVacia vacia  ==  True
esVacia :: Ord a => CPrioridad a -> Bool 
esVacia (CP c) = M.esVacio c

-- (valida c) se verifica si c es una cola de prioridad válida. En la
-- representación mediante montículo todas las colas de prioridad son
-- válidas. 
valida :: Ord a => CPrioridad a -> Bool
valida _ = True

module ColaDePrioridadConMonticulos

(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

import qualified Monticulo as M

-- Colas de prioridad mediante montículos.

newtype CPrioridad a = CP (M.Monticulo a)

deriving (Eq, Show)

-- Ejemplo de cola de prioridad

-- *Main> cp1

-- CP (M 1 2

-- (M 2 2

-- (M 9 1 VacioM VacioM)

-- (M 7 1 VacioM VacioM))

-- (M 3 1 VacioM VacioM))

cp1 :: CPrioridad Int

cp1 = foldr inserta vacia [3,1,7,2,9]

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

-- vacia == CP Vacio

vacia :: Ord a => CPrioridad a

vacia = CP M.vacio

-- (inserta x c) añade el elemento x a la cola de prioridad c. Por ejemplo,

-- ghci> cp1

-- CP (M 1 2

-- (M 2 2

-- (M 9 1 VacioM VacioM)

-- (M 7 1 VacioM VacioM))

-- (M 3 1 VacioM VacioM))

-- ghci> inserta 5 cp1

-- CP (M 1 2

-- (M 2 2

-- (M 9 1 VacioM VacioM)

-- (M 7 1 VacioM VacioM))

-- (M 3 1

-- (M 5 1 VacioM VacioM) VacioM))

inserta :: Ord a => a -> CPrioridad a -> CPrioridad a

inserta v (CP c) = CP (M.inserta v c)

-- (primero c) es la cabeza de la cola de prioridad c. Por ejemplo,

-- primero cp1 == 1

primero :: Ord a => CPrioridad a -> a

primero (CP c) = M.menor c

-- (resto c) elimina la cabeza de la cola de prioridad c. Por ejemplo,

-- ghci> cp1

-- CP (M 1 2

-- (M 2 2

-- (M 9 1 VacioM VacioM)

-- (M 7 1 VacioM VacioM))

-- (M 3 1 VacioM VacioM))

-- ghci> resto cp1

-- CP (M 2 2

-- (M 9 1 VacioM VacioM)

-- (M 3 1

-- (M 7 1 VacioM VacioM) VacioM))

resto :: Ord a => CPrioridad a -> CPrioridad a

resto (CP c) = CP (M.resto c)

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

-- ejemplo,

-- esVacia cp1 == False

-- esVacia vacia == True

esVacia :: Ord a => CPrioridad a -> Bool

esVacia (CP c) = M.esVacio c

-- (valida c) se verifica si c es una cola de prioridad válida. En la

-- representación mediante montículo todas las colas de prioridad son

-- válidas.

valida :: Ord a => CPrioridad a -> Bool

valida _ = True

Se puede imprimir o compartir con