Relación 11 Sol

-- I1M 2021-22: 
-- Tipos de datos algebraicos: Listas.
-- Departamento de Ciencias de la Computación e I.A.
-- Universidad de Sevilla
-- =====================================================================

import Test.QuickCheck

-- ---------------------------------------------------------------------
-- Introducción                                                       --
-- ---------------------------------------------------------------------
--
-- En esta relación se presenta ejercicios sobre el TAD Lista.
-- TAD = Tipo Abstracto de Datos
--
-- ---------------------------------------------------------------------
--
-- Nota. En los siguientes ejercicios se trabajará con el tipo recursivo
-- lista definido como sigue:
--
--     data Lista a = Vacia | Cons a (Lista a)
--
-- Donde el constructor "Vacia" crea una lista vacía y el constructor
-- "Cons a (Lista a)" construye una lista que tiene como cabeza el
-- primer argumento pasado y como cola la lista pasada como segundo
-- argumento.
--
-- Por ejemplo, la lista [2,4,7,9,11] se representa por
--    Cons 2 (Cons 4 (Cons 7 (Cons 9 (Cons 11 Vacia))))
--
-- ---------------------------------------------------------------------

-- Definición del tipo:
data Lista a = Vacia | Cons a (Lista a)
               deriving Eq

-- Definición de la función "show":
instance Show a => Show (Lista a) where
  show Vacia = "{}"
  show (Cons x Vacia) = "{" ++ show x ++ "}"
  show (Cons x lista) = "{" ++ show x ++ "," ++ tail (show lista)

-- Generador para quickCheck:
instance Arbitrary a => Arbitrary (Lista a) where
  arbitrary = sized generaLista
    where generaLista n = if n <= 0 
                          then return Vacia
                          else Cons <$> arbitrary <*> generaLista (n - 1)
  
-- Ejemplos usados para ilustrar los ejercicios:
lista1 :: Lista Int
lista1 = Cons 2 (Cons 4 (Cons 7 (Cons 9 (Cons 11 Vacia))))

lista2 :: Lista Int
lista2 = Cons 10 (Cons 3 (Cons 2 Vacia))

lista3 :: Lista Bool
lista3 = Cons True (Cons True (Cons True Vacia))

lista4 :: Lista Bool
lista4 = Cons False (Cons True (Cons False Vacia))

lista5 :: Lista Int
lista5 = Cons (-1) (Cons 5 (Cons 2 (Cons 3 (Cons 10 (Cons 4 Vacia)))))

lista6 :: Lista (Lista Int)
lista6 = Cons lista1 (Cons lista2 (Cons lista5 Vacia))

-- ---------------------------------------------------------------------
--
-- Ejercicio 1. Definir las siguientes funciones:
--
-- ---------------------------------------------------------------------

-- 1.1. Devuelve la longitud de una lista.
-- longitud lista1 == 5
-- longitud lista1 == 3

longitud :: Lista a -> Int
longitud Vacia = 0
longitud (Cons _ lista) = 1 + longitud lista

-- 1.2. Devuelve el primer elemento de la lista.
-- cabeza lista1 == 2
-- cabeza lista2 == 10

cabeza :: Lista a -> a
cabeza Vacia = error "La lista no tiene elementos"
cabeza (Cons x _) = x

-- 1.3. Devuelve la cola de la lista.
-- cola lista1 == {4,7,9,11}
-- cola (cola (cola lista2)) == {}

cola :: Lista a -> Lista a
cola Vacia = Vacia
cola (Cons _ lista) = lista

-- 1.4. Devuelve el último elemento de lista.
-- ultimo lista1 == 11
-- ultimo lista2 == 2

ultimo :: Lista a -> a
ultimo Vacia = error "La lista no tiene elementos"
ultimo (Cons x Vacia) = x
ultimo (Cons _ lista) = ultimo lista

-- 1.5. Devuelve la lista quitando el ultimo elemento.
-- eliminaUltimo lista1 = {2,4,7,9}
-- eliminaUltimo lista2 = {10,3}

eliminaUltimo :: Lista a -> Lista a
eliminaUltimo Vacia = Vacia
eliminaUltimo (Cons x Vacia) = Vacia
eliminaUltimo (Cons x lista) = Cons x (eliminaUltimo lista)

-- 1.6. Devuelve el elemento en la posición "pos".
-- elemPos 2 lista1 = 7
-- elemPos 1 lista2 = 3

elemPos :: Int -> Lista a -> a
elemPos _ Vacia = error "La lista no tiene elementos"
elemPos 0 (Cons x _) = x
elemPos n (Cons _ lista) | n < 0 = error "La posicion es negativa"
                         | otherwise = elemPos (n-1) lista

-- 1.7. Coge los n primeros elementos de la lista.
-- cogePrimeros 2 lista1 == {2,4}
-- cogePrimeros 4 lista2 == {10,3,2}

cogePrimeros :: Int -> Lista a -> Lista a
cogePrimeros n Vacia = Vacia
cogePrimeros n (Cons x lista) | n <= 0 = Vacia
                              | otherwise = Cons x (cogePrimeros (n-1) lista)

-- 1.8. Elimina los n primeros elementos de la lista.
-- eliminaPrimeros 2 lista1 == {7,9,11}
-- eliminaPrimeros 4 lista2 == {}

eliminaPrimeros :: Int -> Lista a -> Lista a
eliminaPrimeros n Vacia = Vacia
eliminaPrimeros n (Cons x lista) | n <= 0 = Cons x lista
                                 | otherwise = eliminaPrimeros (n-1) lista

-- 1.9. Comprueba si la lista está vacía.
-- esVacia Vacia == True
-- esVacia lista1 == False
-- esVacia lista2 == False

esVacia :: Lista a -> Bool
esVacia Vacia = True
esVacia (Cons _ _) = False

-- 1.10. Comprueba si un elemento está en la lista.
-- esta 10 lista1 = False
-- esta 10 lista2 = True

esta :: Eq a => a -> Lista a -> Bool
esta e Vacia = False
esta e (Cons x lista) = e == x || esta e lista

-- 1.11. Convierte nuestra lista a una lista de Haskell.
-- convierteAList lista1 = [2,4,7,9,11]
-- convierteAList lista2 = [10,3,2]

convierteAList :: Lista a -> [a]
convierteAList Vacia = []
convierteAList (Cons x lista) = x:convierteAList lista

-- 1.12. Convierte una lista de Haskell a nuestra lista.
-- (convierteALista [2,4,7,9,11] == lista1) == True
-- (convierteALista [10,3,2] == lista2) == True

convierteALista :: [a] -> Lista a
convierteALista [] = Vacia
convierteALista (x:xs) = Cons x (convierteALista xs)

-- 1.13. Concatena dos listas.
-- concatena lista1 lista2 == {2,4,7,9,11,10,3,2}

concatena :: Lista a -> Lista a -> Lista a
concatena Vacia lista2 = lista2
concatena (Cons x lista1) lista2 = Cons x (concatena lista1 lista2)

-- 1.14. Invierte una lista.
-- invierte lista1 == {11,9,7,4,2}

invierte :: Lista a -> Lista a
invierte lista = invierteAc lista Vacia

invierteAc :: Lista a -> Lista a -> Lista a
invierteAc Vacia ac = ac
invierteAc (Cons x lista1) ac = invierteAc lista1 (Cons x ac)

-- 1.15. Empareja los elementos de dos listas posición a posición hasta la
-- longitud de la más corta.
-- cremallera lista1 lista2 = [(2,10),(4,3),(7,2)]

cremallera :: Lista a -> Lista a -> [(a,a)]
cremallera _ Vacia = []
cremallera Vacia _ = []
cremallera (Cons x lista1) (Cons y lista2) = (x,y):cremallera lista1 lista2

-- 1.16. Suma los elementos de una lista.
-- suma lista1 = 33
-- suma lista2 = 15

suma :: Num a => Lista a -> a
suma Vacia = 0
suma (Cons x lista) = x + suma lista

-- 1.17. Calcula el producto de todos los elementos de una lista.
-- producto lista1 = 5544
-- producto lista2 = 60

producto :: Num a => Lista a -> a
producto Vacia = 1
producto (Cons x lista) = x * producto lista

-- 1.18. Calcula el máximo elemento de la lista.
-- maximo lista1 = 11
-- maximo lista2 = 10

maximo :: Ord a => Lista a -> a
maximo Vacia = error "La lista no tiene elementos"
maximo (Cons x Vacia) = x
maximo (Cons x lista) = max x (maximo lista)

-- 1.19. Calcula el máximo elemento de la lista.
-- minimo lista1 = 2
-- minimo lista2 = 2

minimo :: Ord a => Lista a -> a
minimo Vacia = error "La lista no tiene elementos"
minimo (Cons x Vacia) = x
minimo (Cons x lista) = min x (minimo lista)

-- 1.20. Calcula la "AND" de todos los elementos de la lista.
-- conjuncion lista3 == True
-- conjuncion lista4 == False

conjuncion :: Lista Bool -> Bool
conjuncion Vacia = True
conjuncion (Cons b lista) = b && conjuncion lista

-- 1.21. Calcula la "OR" de todos los elementos de la lista.
-- disyuncion lista3 == True
-- disyuncion lista4 == True

disyuncion :: Lista Bool -> Bool
disyuncion Vacia = False
disyuncion (Cons b lista) = b || disyuncion lista

-- 1.22. Aplana una lista de listas.
-- aplana lista6 = {2,4,7,9,11,10,3,2,-1,5,2,3,10,4}

aplana :: Lista (Lista a) -> Lista a
aplana Vacia = Vacia
aplana (Cons lista1 lista2) = concatena lista1 (aplana lista2)

-- ---------------------------------------------------------------------
--
-- Ejercicio 2. Comprobar que las funciones anteriores funcionan igual
-- que sus equivalentes en listas de Haskell. Por ejemplo, si queremos
-- comprobar que la función "invierte" funciona igual que "reverse"
-- habría que hacer:
--
-- prop_invierte :: Lista Int -> Bool
-- prop_invierte lista = convierteAList (invierte lista) ==
--                       reverse (convierteAList lista)
--
-- Otro ejemplo con la función longitud:
--
-- prop_longitud :: Lista Int -> Bool
-- prop_longitud lista = longitud lista ==
--                       length (convierteAList lista)
--
-- Nota: Probar con listas de Int o listas de Bool y usar el tipo
-- "Property" cuando sea necesario.
-- 
-- ---------------------------------------------------------------------

-- 1.1.

prop_longitud :: Lista Int -> Bool
prop_longitud lista = longitud lista == length (convierteAList lista)

-- 1.2. 

prop_cabeza :: Lista Int -> Property
prop_cabeza lista = not (esVacia lista) ==> cabeza lista == head (convierteAList lista)

-- 1.3. 

prop_cola :: Lista Int -> Property
prop_cola lista = not (esVacia lista) ==> convierteAList (cola lista) == tail (convierteAList lista)

-- 1.4. 

prop_ultimo :: Lista Int -> Property
prop_ultimo lista = not (esVacia lista) ==> ultimo lista == last (convierteAList lista)

-- 1.5. 

prop_eliminaUltimo :: Lista Int -> Property
prop_eliminaUltimo lista = not (esVacia lista) ==> convierteAList (eliminaUltimo lista) == init (convierteAList lista)

-- 1.6. 

prop_elemPos :: Int -> Lista Int -> Property
prop_elemPos pos lista = not (esVacia lista) && pos < longitud lista && pos >= 0 ==>
                         elemPos pos lista == convierteAList lista !! pos

-- 1.7.

prop_cogePrimeros :: Int -> Lista Int -> Bool
prop_cogePrimeros n lista = convierteAList (cogePrimeros n lista) == take n (convierteAList lista)

-- 1.8. 

prop_eliminaPrimeros :: Int -> Lista Int -> Bool
prop_eliminaPrimeros n lista = convierteAList (eliminaPrimeros n lista) == drop n (convierteAList lista)

-- 1.9.

prop_esVacia :: Lista Int -> Bool
prop_esVacia lista = esVacia lista == null (convierteAList lista)

-- 1.10. 

prop_esta :: Int -> Lista Int -> Bool
prop_esta e lista = esta e lista == elem e (convierteAList lista)

-- 1.11. 

prop_convierteAList :: Lista Int -> Bool
prop_convierteAList lista = convierteALista (convierteAList lista) == lista

-- 1.12. 

prop_convierteALista :: [Int] -> Bool
prop_convierteALista lista = convierteAList (convierteALista lista) == lista

-- 1.13.

prop_concatena :: Lista Int -> Lista Int -> Bool
prop_concatena lista1 lista2 = convierteAList (concatena lista1 lista2) == convierteAList lista1 ++ convierteAList lista2

-- 1.14.

prop_invierte :: Lista Int -> Bool
prop_invierte lista = convierteAList (invierte lista) == reverse (convierteAList lista)

-- 1.15.

prop_cremallera :: Lista Int -> Lista Int -> Bool
prop_cremallera lista1 lista2 = cremallera lista1 lista2 == zip (convierteAList lista1) (convierteAList lista2)

-- 1.16.

prop_suma :: Lista Int -> Bool
prop_suma lista = suma lista == sum (convierteAList lista)

-- 1.17.

prop_producto :: Lista Int -> Bool
prop_producto lista = producto lista == product (convierteAList lista)

-- 1.18.

prop_maximo :: Lista Int -> Property
prop_maximo lista = not (esVacia lista) ==> maximo lista == maximum (convierteAList lista)

-- 1.19.

prop_minimo :: Lista Int -> Property
prop_minimo lista = not (esVacia lista) ==> minimo lista == minimum (convierteAList lista)

-- 1.20.

prop_conjuncion :: Lista Bool -> Bool
prop_conjuncion lista = conjuncion lista == and (convierteAList lista)

-- 1.21.

prop_disyuncion :: Lista Bool -> Bool
prop_disyuncion lista = disyuncion lista == or (convierteAList lista)

-- 1.22.

prop_aplana :: Lista (Lista Int) -> Bool
prop_aplana lista = convierteAList (aplana lista) == concat (map convierteAList (convierteAList lista))