I1M2015: El tipo abstracto de datos de las colas de prioridad en Haskell
En la primera parte de 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.
Se ha seguido el mismo patrón que en los anteriores tipos de datos:
- elección de las operaciones básicas,
- especificación de sus propiedades,
- implementación en Haskell mediante listas,
- análisis de la complejidad de las definiciones de las operaciones básicas y
- 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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
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" -- (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 |