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

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

longitud :: Lista a -> Int
longitud = undefined

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

cabeza :: Lista a -> a
cabeza = undefined

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

cola :: Lista a -> Lista a
cola = undefined

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

ultimo :: Lista a -> a
ultimo = undefined

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

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

elemPos :: Int -> Lista a -> a
elemPos = undefined

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

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

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

esVacia :: Lista a -> Bool
esVacia = undefined

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

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

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

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

concatena :: Lista a -> Lista a -> Lista a
concatena = undefined

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

invierte :: Lista a -> Lista a
invierte = undefined

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

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

suma :: Num a => Lista a -> a
suma = undefined

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

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

maximo :: Ord a => Lista a -> a
maximo = undefined

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

minimo :: Ord a => Lista a -> a
minimo = undefined

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

conjuncion :: Lista Bool -> Bool
conjuncion = undefined

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

disyuncion :: Lista Bool -> Bool
disyuncion = undefined

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

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