Tema 15: El tipo abstracto de datos de las colas

Índice

1. Especificación del TAD de las colas
- 1.1. Signatura del TAD de las colas
- 1.2. Propiedades del TAD de las colas
2. Implementaciones del TAD de las colas
- 2.1. Implementación de las colas mediante listas
- 2.2. Implementación de las colas mediante pares de listas
3. Comprobación de las implementaciones con QuickCheck
4. Material complementario
5. Referencias

1. Especificación del TAD de las colas

1.1. Signatura del TAD de las colas

1.1.1. Descripción informal de las colas

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.
Analogía con las colas del cine.

1.1.2. Signatura del TAD colas

Signatura:

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

Descripción de las operaciones:
- vacia es la cola vacía.
- (inserta x c) es la cola obtenida añadiendo x al final de c.
- (primero c) es el primero de la cola c.
- (resto c) es la cola obtenida eliminando el primero de c.
- (esVacia c) se verifica si c es la cola vacía.
- (valida c) se verifica si c representa una cola válida.

1.2. Propiedades del TAD de las colas

primero (inserta x vacia) == x
Si c es una cola no vacía, entonces primero (inserta x c) == primero c,
resto (inserta x vacia) == vacia
Si c es una cola no vacía, entonces resto (inserta x c) == inserta x (resto c)
esVacia vacia
not (esVacia (inserta x c))

2. Implementaciones del TAD de las colas

2.1. Implementación de las colas mediante listas

Cabecera del módulo:

module Tema_15.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

Representación de las colas mediante listas:

newtype Cola a = C [a]
  deriving (Show, Eq)

Ejemplo de cola: La cola obtenida añadiéndole a la cola vacía los números del 1 al 10 es
```
λ> foldr inserta vacia [1..10]
C [10,9,8,7,6,5,4,3,2,1]
```

#+end_src

vacia es la cola vacía. Por ejemplo,

λ> vacia
C []

Su definición es

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 (foldr inserta vacia [1..10])
C [10,9,8,7,6,5,4,3,2,1,12]

Su definición es

inserta :: a -> Cola a -> Cola a
inserta x (C c) = C (c ++ [x])

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

primero (foldr inserta vacia [1..10])  ==  10

Su definición es

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 (foldr inserta vacia [1..10])
C [9,8,7,6,5,4,3,2,1]

Su definición es

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 (foldr inserta vacia [1..10])     ==  False
esVacia vacia  ==  True

Su definición es

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 _ = True
```

2.2. Implementación de las colas mediante pares de 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 las operaciones que crean colas.

Cabecera del módulo

module Tema_15.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
   escribeCola -- Show a => Cola a -> String
  ) where

Las colas como pares de listas
```
newtype Cola a = C ([a],[a])
```

(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

Su definición es

valida :: Cola a -> Bool
valida (C (xs,ys)) = not (null xs) || null ys

Procedimiento de escritura de colas como pares de listas.

-- (escribeCola p) es la cadena correspondiente a la cola p. Por
-- ejemplo,
--    λ> escribeCola (foldr inserta vacia [1..10])
--    "C [10,9,8,7,6,5,4,3,2,1]"
escribeCola :: Show a => Cola a -> String
escribeCola (C (xs,ys)) = "C " ++ show (xs ++ reverse ys)

-- Procedimiento de escritura de colas.
instance Show a => Show (Cola a) where
  show = escribeCola

Ejemplo de cola: La cola obtenida añadiéndole a la cola vacía los números del 1 al 10 es
```
λ> foldr inserta vacia [1..10]
C [10,9,8,7,6,5,4,3,2,1]
```

vacia es la cola vacía. Por ejemplo,

λ> (foldr inserta vacia [1..10])
C [10,9,8,7,6,5,4,3,2,1]

Su definición es

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 (foldr inserta vacia [1..10])  ==  C [10,9,8,7,6,5,4,3,2,1,12]

Su definición es

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

Su definición es

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 (foldr inserta vacia [1..10])  ==  10

Su definición es

primero  :: Cola a -> a
primero (C (x:_,_)) = x
primero _           = error "primero: cola vacia"

(resto c) es la cola obtenida eliminando el primer elemento de la cola c. Por ejemplo,

λ> resto (foldr inserta vacia [1..10])
C [9,8,7,6,5,4,3,2,1]

Su definición es

resto  :: Cola a -> Cola a
resto (C (_:xs,ys)) = C (normaliza (xs,ys))
resto (C ([],[]))   = error "resto: cola vacia"

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

esVacia (foldr inserta vacia [1..10]) ==  False
esVacia vacia  ==  True

Su definición es

esVacia :: Cola a -> Bool
esVacia (C (xs,_)) = null xs

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

Su definición es

elementos :: Cola a -> [a]
elementos (C (xs,ys)) = xs ++ reverse ys

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

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

Su definición es

igualColas :: Eq a => Cola a -> Cola a -> Bool
igualColas c1 c2 =
  valida c1 &&
  valida c2 &&
  elementos c1 == elementos c2

Extensión de la igualdad a las colas:

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

3. Comprobación de las implementaciones con QuickCheck

3.1. Pragma y librerías auxiliares

Al principio del fichero se añade

{-# LANGUAGE TemplateHaskell #-}
{-# LANGUAGE FlexibleInstances #-}
{-# OPTIONS_GHC -fno-warn-orphans #-}

Importación de la implementación de las colas que se desea comprobar.

import Tema-15.ColaConListas
-- import Tema-15.ColaConDosListas
-- import I1M.Cola

Importación de librerías auxiliares
```
import Test.QuickCheck
```

3.2. Generador de colas

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

λ> sample genCola
C ([7,8,4,3,7],[5,3,3])
C ([1],[13])
...

Su definición es

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

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.

λ> quickCheck prop_genCola_correcto
+++ OK, passed 100 tests.

3.3. Especificación de las propiedades de las colas

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

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 c

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

Las operaciones de encolar y desencolar 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

vacia es una cola vacía.

prop_vacia_es_vacia :: Bool
prop_vacia_es_vacia =
  esVacia vacia

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

La cola vacía es válida.

prop_valida_vacia :: Bool
prop_valida_vacia = valida vacia

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

prop_valida_inserta :: Cola Int -> Int -> Property
prop_valida_inserta c x =
  valida c ==> valida (inserta x c)

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)

3.4. Comprobación de las propiedades

Para verificar todas las propiedades se escribe
```
return []
verifica = $quickCheckAll
```

Comprobación de las propiedades de las pilas

λ> verifica
=== prop_genCola_correcto from ColaPropiedades.hs:46 ===
+++ OK, passed 100 tests.

=== prop_primero_inserta_vacia from ColaPropiedades.hs:59 ===
+++ OK, passed 100 tests.

=== prop_primero_inserta_no_vacia from ColaPropiedades.hs:69 ===
+++ OK, passed 100 tests.

=== prop_resto_inserta_vacia from ColaPropiedades.hs:80 ===
+++ OK, passed 100 tests.

=== prop_resto_inserta_en_no_vacia from ColaPropiedades.hs:89 ===
+++ OK, passed 100 tests.

=== prop_vacia_es_vacia from ColaPropiedades.hs:99 ===
+++ OK, passed 1 tests.

=== prop_inserta_no_es_vacia from ColaPropiedades.hs:108 ===
+++ OK, passed 100 tests.

=== prop_valida_vacia from ColaPropiedades.hs:121 ===
+++ OK, passed 1 tests.

=== prop_valida_inserta from ColaPropiedades.hs:130 ===
+++ OK, passed 100 tests.

=== prop_valida_resto from ColaPropiedades.hs:139 ===
+++ OK, passed 100 tests.

True

4. Material complementario

El código del tema se encuentra en este los siguientes enlaces

Este tema también se encuentra en los siguientes formatos:

Como transparencias en PDF.
Como libro interactivo en IHaskell sobre Jupyter.
Como vídeo de clase.

5. Referencias

F. Rabhi y G. Lapalme. Algorithms: A functional programming approach.
- Cap. 5.3. Queues.
WikiBooks. Data structures primer.