Relación 17

-- I1M 2021-22: Relación 17
-- El TAD de las colas.
-- Departamento de Ciencias de la Computación e I.A.
-- Universidad de Sevilla
-- =====================================================================

-- ---------------------------------------------------------------------
-- Importación de librerías                                           --
-- ---------------------------------------------------------------------

import Data.List
import Test.QuickCheck

-- Hay que elegir una implementación del TAD colas:
import ColaConListas
-- import ColaConDosListas
    
-- ---------------------------------------------------------------------
-- Nota. A lo largo de la relación de ejercicios usaremos los siguientes
-- ejemplos de colas:
c1, c2, c3, c4, c5, c6 :: Cola Int
c1 = foldr inserta vacia [1..20]
c2 = foldr inserta vacia [2,5..18]
c3 = foldr inserta vacia [3..10]
c4 = foldr inserta vacia [4,-1,7,3,8,10,0,3,3,4]
c5 = foldr inserta vacia [15..20]
c6 = foldr inserta vacia (reverse [1..20])
-- ---------------------------------------------------------------------

-- ---------------------------------------------------------------------
-- Ejercicio 1: Definir la función
--    ultimoCola :: Cola a -> a
-- tal que (ultimoCola c) es el último elemento de la cola c. Por
-- ejemplo:
--    ultimoCola c4 == 4
--    ultimoCola c5 == 15
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:

ultimoCola :: Cola a -> a
ultimoCola c | esVacia (resto c) = primero c
             | otherwise = ultimoCola (resto c) 

-- ---------------------------------------------------------------------
-- Ejercicio 2: Definir la función
--    longitudCola :: Cola a -> Int
-- tal que (longitudCola c) es el número de elementos de la cola c. Por
-- ejemplo, 
--     longitudCola c2 == 6
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:

longitudCola :: Cola a -> Int
longitudCola c | esVacia c = 0
               | otherwise = 1 + longitudCola (resto c)

-- ---------------------------------------------------------------------
-- Ejercicio 3: Definir la función 
--    todosVerifican :: (a -> Bool) -> Cola a -> Bool
-- tal que (todosVerifican p c) se verifica si todos los elementos de la
-- cola c cumplen la propiedad p. Por ejemplo,
--    todosVerifican (>0) c1 == True
--    todosVerifican (>0) c4 == False
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:

todosVerifican :: (a -> Bool) -> Cola a -> Bool
todosVerifican p c | esVacia c = error "Lista vacia"
                   | esVacia (resto c) = p (primero c)
                   | otherwise = p (primero c) && todosVerifican p (resto c)

-- ---------------------------------------------------------------------
-- Ejercicio 4: Definir la función
--    algunoVerifica :: (a -> Bool) -> Cola a -> Bool
-- tal que (algunoVerifica p c) se verifica si algún elemento de la cola
-- c cumple la propiedad p. Por ejemplo,
--   algunoVerifica (<0) c1 == False
--   algunoVerifica (<0) c4 == True
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:

algunoVerifica :: (a -> Bool) -> Cola a -> Bool
algunoVerifica p c | esVacia c = error "Lista vacia"
                   | esVacia (resto c) = p (primero c)
                   | otherwise = p (primero c) || algunoVerifica p (resto c)


-- ---------------------------------------------------------------------
-- Ejercicio 5: Definir la función
--    ponAlaCola :: Cola a -> Cola a -> Cola a
-- tal que (ponAlaCola c1 c2) es la cola que resulta de poner los
-- elementos de c2 a la cola de c1. Por ejemplo,
--    ponAlaCola c2 c3 == C [17,14,11,8,5,2,10,9,8,7,6,5,4,3]
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:

ponAlaCola :: Cola a -> Cola a -> Cola a
ponAlaCola c1 c2 | esVacia c2 = c1
                 | otherwise = ponAlaCola (inserta (primero c2) c1) (resto c2) 

-- ---------------------------------------------------------------------
-- Ejercicio 6: Definir la función
--    mezclaColas :: Cola a -> Cola a -> Cola a
-- tal que (mezclaColas c1 c2) es la cola formada por los elementos de
-- c1 y c2 colocados en una cola, de forma alternativa, empezando por
-- los elementos de c1. Por ejemplo,
--    mezclaColas c2 c4 == C [17,4,14,3,11,3,8,0,5,10,2,8,3,7,-1,4]
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:

mezclaColas :: Cola a -> Cola a -> Cola a
mezclaColas c1 c2 = mezclaColas' vacia c1 c2

mezclaColas' :: Cola a -> Cola a -> Cola a -> Cola a
mezclaColas' c c1 c2 | esVacia c1 = ponAlaCola c c2
                     | esVacia c2 = ponAlaCola c c1
                     | otherwise = mezclaColas' (inserta (primero c2) (inserta (primero c1) c)) (resto c1)(resto c2)

-- ---------------------------------------------------------------------
-- Ejercicio 7: Definir la función
--    agrupaColas :: [Cola a] -> Cola a
-- tal que (agrupaColas [c1,c2,c3,...,cn]) es la cola formada mezclando
-- las colas de la lista como sigue: mezcla c1 con c2, el resultado con
-- c3, el resultado con c4, y así sucesivamente. Por ejemplo,
--    ghci> agrupaColas [c3,c3,c4]
--    C [10,4,10,3,9,3,9,0,8,10,8,8,7,3,7,7,6,-1,6,4,5,5,4,4,3,3]
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:

agrupaColas :: [Cola a] -> Cola a
agrupaColas xs | length xs == 1 = head xs
               | otherwise = agrupaColas ((mezclaColas (head xs) (head (tail xs))):(drop 2 xs))

-- ---------------------------------------------------------------------
-- Ejercicio 8: Definir la función
--    perteneceCola :: Eq a => a -> Cola a -> Bool
-- tal que (perteneceCola x c) se verifica si x es un elemento de la
-- cola c. Por ejemplo, 
--    perteneceCola 7 c1  == True
--    perteneceCola 70 c1 == False
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:

perteneceCola :: Eq a => a -> Cola a -> Bool
perteneceCola x c | esVacia c = False
                  | x == primero c = True
                  | otherwise = perteneceCola x (resto c)

-- ---------------------------------------------------------------------
-- Ejercicio 9: Definir la función
--    contenidaCola :: Eq a => Cola a -> Cola a -> Bool
-- tal que (contenidaCola c1 c2) se verifica si todos los elementos de
-- c1 son elementos de c2. Por ejemplo, 
--    contenidaCola c2 c1 == True
--    contenidaCola c1 c2 == False
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:

contenidaCola :: Eq a => Cola a -> Cola a -> Bool
contenidaCola c1 c2 | esVacia c1 = True
                    | otherwise = (perteneceCola (primero c1) c2) && (contenidaCola (resto c1) c2)

-- ---------------------------------------------------------------------
-- Ejercicio 10: Definir la función
--    prefijoCola :: Eq a => Cola a -> Cola a -> Bool
-- tal que (prefijoCola c1 c2) se verifica si la cola c1 es un prefijo
-- de la cola c2. Por ejemplo, 
--    prefijoCola c3 c2 == False
--    prefijoCola c5 c1 == True
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:

prefijoCola :: Eq a => Cola a -> Cola a -> Bool
prefijoCola c1 c2 | esVacia c1 = True
                  | esVacia c2 = False 
                  | (primero c1) /= (primero c2) = False
                  | otherwise = prefijoCola (resto c1) (resto c2) 

-- ---------------------------------------------------------------------
-- Ejercicio 11: Definir la función
--    subCola :: Eq a => Cola a -> Cola a -> Bool
-- tal que (subCola c1 c2) se verifica si c1 es una subcola de c2. Por
-- ejemplo,  
--    subCola c2 c1 == False
--    subCola c3 c1 == True
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:

subCola :: Eq a => Cola a -> Cola a -> Bool
subCola c1 c2 | esVacia c2 = False
              | otherwise = prefijoCola c1 c2 || subCola c1 (resto c2) 

-- ---------------------------------------------------------------------
-- Ejercicio 12: Definir la función
--    ordenadaCola :: Ord a => Cola a -> Bool
-- tal que (ordenadaCola c) se verifica si los elementos de la cola c
-- están ordenados en orden creciente. Por ejemplo,
--    ordenadaCola c6 == True
--    ordenadaCola c4 == False
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:

ordenadaCola :: Ord a => Cola a -> Bool
ordenadaCola c | esVacia (resto c) = True
               | otherwise = (primero c) <= (primero (resto c)) && ordenadaCola (resto c) 

-- ---------------------------------------------------------------------
-- Ejercicio 13.1: Definir una función
--    lista2Cola :: [a] -> Cola a
-- tal que (lista2Cola xs) es una cola formada por los elementos de xs.
-- Por ejemplo,
--    lista2Cola [1..6] == C [1,2,3,4,5,6]
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:

lista2Cola :: [a] -> Cola a
lista2Cola xs = foldr inserta vacia (reverse xs)

-- ---------------------------------------------------------------------
-- Ejercicio 13.2: Definir una función
--    cola2Lista :: Cola a -> [a]
-- tal que (cola2Lista c) es la lista formada por los elementos de p.
-- Por ejemplo,
--    cola2Lista c2 == [17,14,11,8,5,2]
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:

cola2Lista :: Cola a -> [a]
cola2Lista c | esVacia c = []
             | otherwise = (primero c):(cola2Lista (resto c))

-- ---------------------------------------------------------------------
-- Ejercicio 13.3. Comprobar con QuickCheck que la función cola2Lista es
-- la inversa de  lista2Cola, y recíprocamente.
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:

prop_cola2Lista :: Cola Int -> Bool
prop_cola2Lista c = lista2Cola (cola2Lista c) == c

-- ghci> quickCheck prop_cola2Lista
-- +++ OK, passed 100 tests.

prop_lista2Cola :: [Int] -> Bool
prop_lista2Cola xs = cola2Lista (lista2Cola xs) == xs

-- ghci> quickCheck prop_lista2Cola
-- +++ OK, passed 100 tests.

-- ---------------------------------------------------------------------
-- Ejercicio 14: Definir la función 
--    maxCola :: Ord a => Cola a -> a
-- tal que (maxCola c) es el mayor de los elementos de la cola c. Por
-- ejemplo, 
--    maxCola c4 == 10
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:

maxCola :: Ord a => Cola a -> a
maxCola c | esVacia c = error "Lista vacia"
          | esVacia (resto c) = primero c
          | (primero c) <= (primero (resto c)) = maxCola (resto c)
          | otherwise = maxCola (inserta (primero c) (resto c))

-- ---------------------------------------------------------------------
-- 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 :: (Num a, Arbitrary a) => Gen (Cola a)
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 cola es una instancia del arbitrario.
instance (Arbitrary a, Num a) => Arbitrary (Cola a) where
    arbitrary = genCola