Relación 11

-- 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 presentan 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:
--
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:

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

longitud :: Lista a -> Int
longitud Vacia = 0
longitud (Cons x l) = 1 + longitud l

-- Álvaro Galisteo:

-- 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 l) = x 

-- Álvaro Galisteo:

-- 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 a l) = l

-- Álvaro Galisteo:

-- 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 a Vacia) = a
ultimo (Cons a l) = ultimo l 

-- Álvaro Galisteo:

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

eliminaUltimo :: Lista a -> Lista a
eliminaUltimo Vacia = error "La lista no tiene elementos"
eliminaUltimo (Cons a Vacia) = Vacia 
eliminaUltimo (Cons a l) = Cons a (eliminaUltimo l) 

-- Álvaro Galisteo:

-- 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 n (Cons a l) | n == 0 = a
                     | n < 0 = error "La posición es negativa"
                     | otherwise = elemPos (n-1) l

-- Álvaro Galisteo:

-- 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 0 _ = Vacia
cogePrimeros _ Vacia = Vacia
cogePrimeros n (Cons a l) = Cons a (cogePrimeros (n-1) l)

-- Álvaro Galisteo:

-- 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 _ Vacia = Vacia
eliminaPrimeros 0 l = l
eliminaPrimeros n (Cons a l) = eliminaPrimeros (n-1) l

-- Álvaro Galisteo:

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

-- Álvaro Galisteo:

-- 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 n Vacia = False 
esta n (Cons a l) = if n == a  then True
                       else esta n l 

-- Álvaro Galisteo:

-- 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 a l) = [a] ++ convierteAList l 

-- Álvaro Galisteo:

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

-- Álvaro Galisteo:

-- 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 l = l
concatena (Cons a1 l1) l2 = Cons a1 (concatena l1 l2)

-- Álvaro Galisteo:

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

invierte :: Lista a -> Lista a
invierte (Cons a Vacia) = (Cons a (Vacia))
invierte (Cons a l) = (Cons (ultimo l) (invierte (eliminaUltimo (Cons a l))))

-- Álvaro Galisteo:

-- 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 a1 l1) (Cons a2 l2) = [(a1,a2)] ++ cremallera l1 l2 

-- Álvaro Galisteo:

-- 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 a l) = a + (suma l) 

-- Álvaro Galisteo:

-- 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 a l) = a * (producto l) 

-- Álvaro Galisteo:

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

maximo :: Ord a => Lista a -> a
maximo (Cons a l) = auxMaximo a l

auxMaximo :: Ord a => a -> Lista a -> a
auxMaximo x Vacia = x
auxMaximo x (Cons a l) = auxMaximo (max x a) l 

-- Álvaro Galisteo:

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

minimo :: Ord a => Lista a -> a
minimo (Cons a l) = auxMinimo a l

auxMinimo :: Ord a => a -> Lista a -> a
auxMinimo x Vacia = x
auxMinimo x (Cons a l) = auxMinimo (min x a) l 

-- Álvaro Galisteo:

-- 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 a l) = a && conjuncion l

-- Álvaro Galisteo:

-- 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 a l) = a || disyuncion l 

-- Álvaro Galisteo:

-- 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 l1 l2) = concatena l1 (aplana l2)  

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

-- Álvaro Galisteo:

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

-- *Main> quickCheck prop_longitud
-- +++ OK, passed 100 tests.


prop_cabeza :: Lista Int -> Property
prop_cabeza l = l /= Vacia ==> cabeza l == head (convierteAList l)

-- *Main> quickCheck prop_cabeza
-- .+++ OK, passed 100 tests; 10 discarded.


prop_cola :: Lista Int -> Property
prop_cola l = l /= Vacia ==> convierteAList (cola l) == tail (convierteAList l)

-- *Main> quickCheck prop_cola
-- +++ OK, passed 100 tests; 10 discarded.


prop_ultimo :: Lista Int -> Property
prop_ultimo l = l /= Vacia ==> ultimo l == last (convierteAList l)

-- *Main> quickCheck prop_ultimo
-- +++ OK, passed 100 tests; 10 discarded.

prop_eliminaUltimo :: Lista Int -> Property
prop_eliminaUltimo l = l /= Vacia ==> convierteAList (eliminaUltimo l) == init (convierteAList l)

-- *Main> quickCheck prop_eliminaUltimo
-- +++ OK, passed 100 tests; 10 discarded.


prop_elemPos :: Int -> Lista Int -> Property 
prop_elemPos n l = n >= 0 && n<longitud l && l /= Vacia ==> elemPos n l == (convierteAList l) !! n 

-- *Main> quickCheck prop_elemPos
-- +++ OK, passed 100 tests; 106 discarded.


prop_cogePrimeros :: Int -> Lista Int -> Property
prop_cogePrimeros n l =  n >= 0 && n<longitud l && l /= Vacia ==> convierteAList (cogePrimeros n l) == take n (convierteAList l)

-- *Main> quickCheck prop_cogePrimeros
-- +++ OK, passed 100 tests; 112 discarded.


prop_eliminaPrimeros :: Int -> Lista Int -> Property
prop_eliminaPrimeros n l =  n >= 0 && n<longitud l && l /= Vacia ==> convierteAList (eliminaPrimeros n l) == drop n (convierteAList l)

-- *Main> quickCheck prop_eliminaPrimeros
-- +++ OK, passed 100 tests; 93 discarded.


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

-- *Main> quickCheck prop_esVacia
-- +++ OK, passed 100 tests.


prop_esta :: Eq a => a -> Lista a -> Bool
prop_esta n l = esta n l == elem n (convierteAList l)

-- *Main> quickCheck prop_esta
-- +++ OK, passed 100 tests.


prop_concatena :: Eq a => Lista a -> Lista a -> Bool 
prop_concatena l1 l2 = convierteAList (concatena l1 l2) == convierteAList l1 ++ convierteAList l2

-- *Main> quickCheck prop_concatena
-- +++ OK, passed 100 tests.


prop_invierte :: Lista Int -> Property
prop_invierte lista = lista /= Vacia ==> convierteAList (invierte lista) == reverse (convierteAList lista)

-- *Main> quickCheck prop_invierte
-- +++ OK, passed 100 tests; 10 discarded.


prop_cremallera :: Eq a => Lista a -> Lista a -> Bool
prop_cremallera l1 l2 = cremallera l1 l2 == zip (convierteAList l1) (convierteAList l2) 

-- *Main> quickCheck prop_cremallera
-- +++ OK, passed 100 tests.


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

-- *Main> quickCheck prop_suma
-- +++ OK, passed 100 tests.

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

-- *Main> quickCheck prop_producto
-- +++ OK, passed 100 tests.

prop_maximo :: Lista Int-> Property
prop_maximo l = l /= Vacia ==> maximo l == maximum (convierteAList l)

-- *Main> quickCheck prop_maximo
-- +++ OK, passed 100 tests; 10 discarded.

prop_minimo :: Lista Int -> Property 
prop_minimo l = l /= Vacia ==> minimo l == minimum (convierteAList l)

-- *Main> quickCheck prop_minimo
-- +++ OK, passed 100 tests; 10 discarded.

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

-- *Main> quickCheck prop_conjuncion
-- +++ OK, passed 100 tests.


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

-- *Main> quickCheck prop_disyuncion
-- +++ OK, passed 100 tests.


prop_aplana :: Lista (Lista Int) -> Bool
prop_aplana l = convierteAList (aplana l) == concat (convierteAlistas l)

convierteAlistas :: Lista (Lista Int) -> [[Int]]
convierteAlistas Vacia = [[]]
convierteAlistas (Cons l1 l2) = [convierteAList l1] ++ convierteAlistas l2

-- *Main> quickCheck prop_aplana
-- +++ OK, passed 100 tests.