-- I1M 2021-22: Rel_7.hs
-- Definiciones por recursión y por comprensión
-- Departamento de Ciencias de la Computación e I.A.
-- Universidad de Sevilla
-- =====================================================================
-- ---------------------------------------------------------------------
-- Introducción --
-- ---------------------------------------------------------------------
-- Esta relación es de repaso y servirá para seguir practicando los
-- conceptos de recursión y comprensión
-- En esta relación se presentan ejercicios con dos definiciones (una
-- por recursión y otra por comprensión) y la comprobación de la
-- equivalencia de las dos definiciones con QuickCheck. Los ejercicios
-- corresponden a los temas 5 y 6
-- ---------------------------------------------------------------------
-- Importación de librerías auxiliares --
-- ---------------------------------------------------------------------
import Test.QuickCheck
import Data.List
-- ---------------------------------------------------------------------
-- En estas relación se definen operaciones conjuntistas sobre listas.
-- ---------------------------------------------------------------------
-- ---------------------------------------------------------------------
-- Ejercicio 1.1. Definir, por comprensión, la función
-- subconjunto :: Eq a => [a] -> [a] -> Bool
-- tal que (subconjunto xs ys) se verifica si xs es un subconjunto de
-- ys; es decir, si todos los elementos de xs pertenecen a ys. Por
-- ejemplo,
-- subconjunto [3,2,3] [2,5,3,5] == True
-- subconjunto [3,2,3] [2,5,6,5] == False
-- ---------------------------------------------------------------------
subconjunto :: Eq a => [a] -> [a] -> Bool
subconjunto = undefined
-- ---------------------------------------------------------------------
-- Ejercicio 1.2. Definir, por recursión, la función
-- subconjuntoR :: Eq a => [a] -> [a] -> Bool
-- tal que (subconjuntoR xs ys) se verifica si xs es un subconjunto de
-- ys; es decir, si todos los elementos de xs pertenecen a ys. Por
-- ejemplo,
-- subconjuntoR [3,2,3] [2,5,3,5] == True
-- subconjuntoR [3,2,3] [2,5,6,5] == False
-- ---------------------------------------------------------------------
subconjuntoR :: Eq a => [a] -> [a] -> Bool
subconjuntoR = undefined
-- ---------------------------------------------------------------------
-- Ejercicio 1.3. Comprobar con QuickCheck que las definiciones
-- subconjunto y subconjuntoR son equivalentes.
-- ---------------------------------------------------------------------
-- La propiedad es
prop_subconjuntoR :: [Int] -> [Int] -> Bool
prop_subconjuntoR = undefined
-- La comprobación es
-- ---------------------------------------------------------------------
-- Ejercicio 1.4. Definir, mediante all, la función
-- subconjuntoA :: Eq a => [a] -> [a] -> Bool
-- tal que (subconjuntoA xs ys) se verifica si xs es un subconjunto de
-- ys. Por ejemplo,
-- subconjuntoA [1,3,2,3] [1,2,3] == True
-- subconjuntoA [1,3,4,3] [1,2,3] == False
-- ---------------------------------------------------------------------
subconjuntoA :: Eq a => [a] -> [a] -> Bool
subconjuntoA = undefined
-- ---------------------------------------------------------------------
-- Ejercicio 1.5. Comprobar con QuickCheck que las funciones subconjunto
-- y subconjuntoA son equivalentes.
-- ---------------------------------------------------------------------
-- La propiedad es
prop_subconjuntoA :: [Int] -> [Int] -> Bool
prop_subconjuntoA = undefined
-- La comprobación es
-- ---------------------------------------------------------------------
-- Ejercicio 2. Definir la función
-- iguales :: Eq a => [a] -> [a] -> Bool
-- tal que (iguales xs ys) se verifica si xs e ys son iguales; es decir,
-- tienen los mismos elementos. Por ejemplo,
-- iguales [3,2,3] [2,3] == True
-- iguales [3,2,3] [2,3,2] == True
-- iguales [3,2,3] [2,3,4] == False
-- iguales [2,3] [4,5] == False
-- ---------------------------------------------------------------------
iguales :: Eq a => [a] -> [a] -> Bool
iguales = undefined
-- ---------------------------------------------------------------------
-- Ejercicio 3.1. Definir, por comprensión, la función
-- union :: Eq a => [a] -> [a] -> [a]
-- tal que (union xs ys) es la unión de los conjuntos xs e ys. Por
-- ejemplo,
-- union [3,2,5] [5,7,3,4] == [3,2,5,7,4]
-- ---------------------------------------------------------------------
union :: Eq a => [a] -> [a] -> [a]
union = undefined
-- ---------------------------------------------------------------------
-- Ejercicio 3.2. Definir, por comprensión, la función
-- unionR :: Eq a => [a] -> [a] -> [a]
-- tal que (unionR xs ys) es la unión de los conjuntos xs e ys. Por
-- ejemplo,
-- unionR [3,2,5] [5,7,3,4] == [2,5,7,3,4]
-- ---------------------------------------------------------------------
unionR :: Eq a => [a] -> [a] -> [a]
unionR = undefined
-- ---------------------------------------------------------------------
-- Ejercicio 3.3. Comprobar con QuickCheck que union y unionR son
-- equivalentes.
-- ---------------------------------------------------------------------
-- La propiedad es
prop_union :: [Int] -> [Int] -> Bool
prop_union = undefined
-- La comprobación es
-- ---------------------------------------------------------------------
-- Ejercicio 4. Comprobar con QuickCheck que la unión es conmutativa.
-- ---------------------------------------------------------------------
-- La propiedad es
prop_union_conmutativa :: [Int] -> [Int] -> Bool
prop_union_conmutativa = undefined
-- La comprobación es
-- ---------------------------------------------------------------------
-- Ejercicio 5.1. Definir, por comprensión, la función
-- interseccion :: Eq a => [a] -> [a] -> [a]
-- tal que (interseccion xs ys) es la intersección de xs e ys. Por
-- ejemplo,
-- interseccion [3,2,5] [5,7,3,4] == [3,5]
-- interseccion [3,2,5] [9,7,6,4] == []
-- ---------------------------------------------------------------------
interseccion :: Eq a => [a] -> [a] -> [a]
interseccion = undefined
-- ---------------------------------------------------------------------
-- Ejercicio 5.2. Definir, por recursión, la función
-- interseccionR :: Eq a => [a] -> [a] -> [a]
-- tal que (interseccionR xs ys) es la intersección de xs e ys. Por
-- ejemplo,
-- interseccionR [3,2,5] [5,7,3,4] == [3,5]
-- interseccionR [3,2,5] [9,7,6,4] == []
-- ---------------------------------------------------------------------
interseccionR :: Eq a => [a] -> [a] -> [a]
interseccionR = undefined
-- ---------------------------------------------------------------------
-- Ejercicio 5.3. Comprobar con QuickCheck que interseccion e
-- interseccionR son equivalentes.
-- ---------------------------------------------------------------------
-- La propiedad es
prop_interseccion :: [Int] -> [Int] -> Bool
prop_interseccion = undefined
-- La comprobación es
-- ---------------------------------------------------------------------
-- Ejercicio 6. Comprobar con QuickCheck si se cumple la siguiente
-- propiedad
-- A ∪ (B ∩ C) = (A ∪ B) ∩ C
-- donde se considera la igualdad como conjuntos. En el caso de que no
-- se cumpla verificar el contraejemplo calculado por QuickCheck.
-- ---------------------------------------------------------------------
prop_union_interseccion :: [Int] -> [Int] -> [Int] -> Bool
prop_union_interseccion = undefined
-- La comprobación es
-- ---------------------------------------------------------------------
-- Ejercicio 7.1. Definir, por comprensión, la función
-- diferencia :: Eq a => [a] -> [a] -> [a]
-- tal que (diferencia xs ys) es la diferencia entre los conjuntos xs e
-- ys; es decir, la lista de los elementos que sólo pertenecen a xs. Por
-- ejemplo,
-- diferencia [3,2,5,6] [5,7,3,4] == [2,6]
-- diferencia [3,2,5] [5,7,3,2] == []
-- ---------------------------------------------------------------------
diferencia :: Eq a => [a] -> [a] -> [a]
diferencia = undefined
-- ---------------------------------------------------------------------
-- Ejercicio 7.2. Definir, por recursión, la función
-- diferenciaR :: Eq a => [a] -> [a] -> [a]
-- tal que (diferenciaR xs ys) es la diferencia entre los conjuntos xs e
-- ys; es decir, la lista de los elementos que sólo pertenecen a xs. Por
-- ejemplo,
-- diferenciaR [3,2,5,6] [5,7,3,4] == [2,6]
-- diferenciaR [3,2,5] [5,7,3,2] == []
-- ---------------------------------------------------------------------
diferenciaR :: Eq a => [a] -> [a] -> [a]
diferenciaR = undefined
-- ---------------------------------------------------------------------
-- Ejercicio 7.3. Comprobar con QuickCheck que diferencia y diferenciaR
-- son equivalentes.
-- ---------------------------------------------------------------------
-- La propiedad es
prop_diferencia :: [Int] -> [Int] -> Bool
prop_diferencia = undefined
-- La comprobación es
-- ---------------------------------------------------------------------
-- Ejercicio 8. Comprobar con QuickCheck si la diferencia es
-- conmutativa.
-- ---------------------------------------------------------------------
prop_diferencia_conmutativa :: [Int] -> [Int] -> Bool
prop_diferencia_conmutativa = undefined
-- La comprobación es
-- ---------------------------------------------------------------------
-- Ejercicio 9. Comprobar con QuickCheck si se cumple la siguiente
-- propiedad: A \ B ⊂ A
-- ---------------------------------------------------------------------
-- La propiedad es
prop_diferencia_subconjunto :: [Int] -> [Int] -> Bool
prop_diferencia_subconjunto = undefined
-- La comprobación es
-- ---------------------------------------------------------------------
-- Ejercicio 10. Comprobar con QuickCheck si se cumple la siguiente
-- propiedad: (A \ B) ∩ B = ∅.
-- ---------------------------------------------------------------------
-- La propiedad es
prop_diferencia_interseccion :: [Int] -> [Int] -> Bool
prop_diferencia_interseccion = undefined
-- La comprobación es
-- ---------------------------------------------------------------------
-- Ejercicio 11.1. Definir, por comprensión, la función
-- producto :: Eq a => [a] -> [a] -> [(a,a)]
-- tal que (producto xs ys) es el producto cartesiano de xs e ys. Por
-- ejemplo,
-- producto [1,3] [2,4] == [(1,2),(1,4),(3,2),(3,4)]
-- ---------------------------------------------------------------------
producto :: Eq a => [a] -> [a] -> [(a,a)]
producto = undefined
-- ---------------------------------------------------------------------
-- Ejercicio 11.2. Definir, por recursión, la función
-- productoR :: Eq a => [a] -> [a] -> [(a,a)]
-- tal que (productoR xs ys) es el producto cartesiano de xs e ys. Por
-- ejemplo,
-- productoR [1,3] [2,4] == [(1,2),(1,4),(3,2),(3,4)]
-- ---------------------------------------------------------------------
productoR :: Eq a => [a] -> [a] -> [(a,a)]
productoR = undefined
-- ---------------------------------------------------------------------
-- Ejercicio 11.3. Comprobar con QuickCheck que producto y productoR
-- son equivalentes.
-- ---------------------------------------------------------------------
-- La propiedad es
prop_producto :: [Int] -> [Int] -> Bool
prop_producto = undefined
-- La comprobación es
-- ---------------------------------------------------------------------
-- Ejercicio 12. Comprobar con QuickCheck que el número de elementos
-- de (producto xs ys) es el producto del número de elementos de xs y de
-- ys.
-- ---------------------------------------------------------------------
-- La propiedad es
prop_elementos_producto :: [Int] -> [Int] -> Bool
prop_elementos_producto = undefined
-- La comprobación es
-- ---------------------------------------------------------------------
-- Ejercicio 13. Definir la función
-- subconjuntos :: [a] -> [[a]]
-- tal que (subconjuntos xs) es la lista de las subconjuntos de la lista
-- xs. Por ejemplo,
-- ghci> subconjuntos [2,3,4]
-- [[2,3,4],[2,3],[2,4],[2],[3,4],[3],[4],[]]
-- ghci> subconjuntos [1,2,3,4]
-- [[1,2,3,4],[1,2,3],[1,2,4],[1,2],[1,3,4],[1,3],[1,4],[1],
-- [2,3,4], [2,3], [2,4], [2], [3,4], [3], [4], []]
-- ---------------------------------------------------------------------
subconjuntos :: [a] -> [[a]]
subconjuntos = undefined
-- ---------------------------------------------------------------------
-- Ejercicio 14. Comprobar con QuickChek que el número de elementos de
-- (subconjuntos xs) es 2 elevado al número de elementos de xs.
--
-- Nota. Al hacer la comprobación limitar el tamaño de las pruebas como
-- se indica a continuación
-- quickCheckWith (stdArgs {maxSize=7}) prop_subconjuntos
-- ---------------------------------------------------------------------
-- La propiedad es
prop_subconjuntos :: [Int] -> Bool
prop_subconjuntos = undefined
-- La comprobación es
-- ---------------------------------------------------------------------
-- Ejercicios variados
-- ---------------------------------------------------------------------
-- ---------------------------------------------------------------------
-- Ejercicio 15.1 Se quiere formar una escalera con bloques cuadrados,
-- de forma que tenga un número determinado de escalones. Por ejemplo,
-- una escalera con tres escalones tendría la siguiente forma:
-- XX
-- XXXX
-- XXXXXX
-- Definir, por recursión, la función
-- numeroBloquesR :: Integer -> Integer
-- tal que (numeroBloquesR n) es el número de bloques necesarios para
-- construir una escalera con n escalones. Por ejemplo,
-- numeroBloquesR 1 == 2
-- numeroBloquesR 3 == 12
-- numeroBloquesR 10 == 110
-- ---------------------------------------------------------------------
numeroBloquesR :: Integer -> Integer
numeroBloquesR = undefined
-- ---------------------------------------------------------------------
-- Ejercicio 15.2. Definir, por comprensión, la función
-- numeroBloquesC :: Integer -> Integer
-- tal que (numeroBloquesC n) es el número de bloques necesarios para
-- construir una escalera con n escalones. Por ejemplo,
-- numeroBloquesC 1 == 2
-- numeroBloquesC 3 == 12
-- numeroBloquesC 10 == 110
-- ---------------------------------------------------------------------
numeroBloquesC :: Integer -> Integer
numeroBloquesC n = undefined
-- ---------------------------------------------------------------------
-- Ejercicio 15.3. Comprobar con QuickCheck que (numeroBloquesC n) es
-- igual a n+n^2.
-- ---------------------------------------------------------------------
-- La propiedad es
prop_numeroBloquesR n = undefined
-- La comprobación es
-- ---------------------------------------------------------------------
-- Ejercicio 16. Definir la función
-- esDigito :: Integer -> Integer -> Bool
-- tal que (esDigito x n) se verifica si x es un dígito de n. Por
-- ejemplo,
-- esDigito 4 1041 == True
-- esDigito 3 1041 == False
-- ---------------------------------------------------------------------
esDigito :: Integer -> Integer -> Bool
esDigito x n = undefined
-- ---------------------------------------------------------------------
-- Ejercicio 17. Definir la función
-- numeroDeDigitos :: Integer -> Integer
-- tal que (numeroDeDigitos x) es el número de dígitos de x. Por ejemplo,
-- numeroDeDigitos 34047 == 5
-- ---------------------------------------------------------------------
numeroDeDigitos :: Integer -> Int
numeroDeDigitos x = undefined
-- ---------------------------------------------------------------------
-- Ejercicio 18.1 Definir, por recursión, la función
-- listaNumeroR :: [Integer] -> Integer
-- tal que (listaNumeroR xs) es el número formado por los dígitos xs. Por
-- ejemplo,
-- listaNumeroR [5] == 5
-- listaNumeroR [1,3,4,7] == 1347
-- listaNumeroR [0,0,1] == 1
-- ---------------------------------------------------------------------
listaNumeroR :: [Integer] -> Integer
listaNumeroR = undefined
-- ---------------------------------------------------------------------
-- Ejercicio 18.2. Definir, por comprensión, la función
-- listaNumeroC :: [Integer] -> Integer
-- tal que (listaNumeroC xs) es el número formado por los dígitos xs. Por
-- ejemplo,
-- listaNumeroC [5] == 5
-- listaNumeroC [1,3,4,7] == 1347
-- listaNumeroC [0,0,1] == 1
-- ---------------------------------------------------------------------
listaNumeroC :: [Integer] -> Integer
listaNumeroC xs = undefined
-- ---------------------------------------------------------------------
-- Ejercicio 19.1. Definir, por recursión, la función
-- pegaNumerosR :: Integer -> Integer -> Integer
-- tal que (pegaNumerosR x y) es el número resultante de "pegar" los
-- números x e y. Por ejemplo,
-- pegaNumerosR 12 987 == 12987
-- pegaNumerosR 1204 7 == 12047
-- pegaNumerosR 100 100 == 100100
-- ---------------------------------------------------------------------
pegaNumerosR :: Integer -> Integer -> Integer
pegaNumerosR x y = undefined
-- ---------------------------------------------------------------------
-- Ejercicio 19.2. Definir, sin usar recursión, la función
-- pegaNumerosNR :: Integer -> Integer -> Integer
-- tal que (pegaNumerosNR x y) es el número resultante de "pegar" los
-- números x e y. Por ejemplo,
-- pegaNumerosNR 12 987 == 12987
-- pegaNumerosNR 1204 7 == 12047
-- pegaNumerosNR 100 100 == 100100
-- ---------------------------------------------------------------------
pegaNumerosNR :: Integer -> Integer -> Integer
pegaNumerosNR x y = undefined
-- ---------------------------------------------------------------------
-- Ejercicio 19.3. Comprobar con QuickCheck que las funciones
-- pegaNumerosR y pegaNumerosNR son equivalentes.
-- ---------------------------------------------------------------------
-- La propiedad es
prop_pegaNumeros x y = undefined
-- La comprobación es
-- ---------------------------------------------------------------------
-- Ejercicio 20.1. Definir, por recursión, la función
-- primerDigitoR :: Integer -> Integer
-- tal que (primerDigitoR n) es el primer dígito de n. Por ejemplo,
-- primerDigitoR 425 == 4
-- ---------------------------------------------------------------------
primerDigitoR :: Integer -> Integer
primerDigitoR n = undefined
-- ---------------------------------------------------------------------
-- Ejercicio 20.2. Definir, sin usar recursión, la función
-- primerDigitoNR :: Integer -> Integer
-- tal que (primerDigitoNR n) es la primera digito de n. Por ejemplo,
-- primerDigitoNR 425 == 4
-- ---------------------------------------------------------------------
primerDigitoNR :: Integer -> Integer
primerDigitoNR n = undefined
-- ---------------------------------------------------------------------
-- Ejercicio 20.3. Comprobar con QuickCheck que las funciones
-- primerDigitoR y primerDigitoNR son equivalentes.
-- ---------------------------------------------------------------------
-- La propiedad es
prop_primerDigito x = undefined
-- La comprobación es
-- ---------------------------------------------------------------------
-- Ejercicio 21.1. Definir la función
-- inverso :: Integer -> Integer
-- tal que (inverso n) es el número obtenido escribiendo los dígitos de n
-- en orden inverso. Por ejemplo,
-- inverso 42578 == 87524
-- inverso 203 == 302
-- ---------------------------------------------------------------------
inverso :: Integer -> Integer
inverso n = undefined
-- ---------------------------------------------------------------------
-- Ejercicio 22.2. Definir, usando show y read, la función
-- inverso' :: Integer -> Integer
-- tal que (inverso' n) es el número obtenido escribiendo los dígitos de n
-- en orden inverso'. Por ejemplo,
-- inverso' 42578 == 87524
-- inverso' 203 == 302
-- ---------------------------------------------------------------------
inverso' :: Integer -> Integer
inverso' n = undefined
-- ---------------------------------------------------------------------
-- Ejercicio 22.3. Comprobar con QuickCheck que las funciones
-- inverso e inverso' son equivalentes.
-- ---------------------------------------------------------------------
-- La propiedad es
prop_inverso n = undefined
-- La comprobación es
-- ---------------------------------------------------------------------
-- Ejercicio 23. Definir la función
-- capicua :: Integer -> Bool
-- tal que (capicua n) se verifica si si los dígitos que n son las mismas
-- de izquierda a derecha que de derecha a izquierda. Por ejemplo,
-- capicua 1234 = False
-- capicua 1221 = True
-- capicua 4 = True
-- ---------------------------------------------------------------------
capicua :: Integer -> Bool
capicua n = undefined
-- ---------------------------------------------------------------------
-- Ejercicio 24. (Problema 16 del proyecto Euler) El problema se
-- encuentra en http://goo.gl/4uWh y consiste en calcular la suma de los
-- dígitos de 2^1000. Lo resolveremos mediante los distintos apartados de
-- este ejercicio.
-- ---------------------------------------------------------------------
-- ---------------------------------------------------------------------
-- Ejercicio 24.1. Definir la función
-- euler16 :: Integer -> Integer
-- tal que (euler16 n) es la suma de los dígitos de 2^n. Por ejemplo,
-- euler16 4 == 7
-- ---------------------------------------------------------------------
euler16 :: Integer -> Integer
euler16 n = undefined
-- ---------------------------------------------------------------------
-- Ejercicio 24.2. Calcular la suma de los dígitos de 2^1000.
-- ---------------------------------------------------------------------
-- El cálculo es
-- *Main> euler16 1000
-- 1366
-- ---------------------------------------------------------------------
-- Ejercicio 25. En el enunciado de uno de los problemas de las
-- Olimpiadas matemáticas de Brasil se define el primitivo de un número
-- como sigue:
-- Dado un número natural N, multiplicamos todos sus dígitos,
-- repetimos este procedimiento hasta que quede un solo dígito al
-- cual llamamos primitivo de N. Por ejemplo para 327: 3x2x7 = 42 y
-- 4x2 = 8. Por lo tanto, el primitivo de 327 es 8.
--
-- Definir la función
-- primitivo :: Integer -> Integer
-- tal que (primitivo n) es el primitivo de n. Por ejemplo.
-- primitivo 327 == 8
-- ---------------------------------------------------------------------
primitivo :: Integer -> Integer
primitivo = undefined
-- ---------------------------------------------------------------------
-- Ejercicio 26. Dos números son equivalentes si la media de sus dígitos
-- son iguales. Por ejemplo, 3205 y 41 son equvalentes ya que
-- (3+2+0+5)/4 = (4+1)/2. Definir la función
-- equivalentes :: Integer -> Integer -> Bool
-- tal que (equivalentes x y) se verifica si los números x e y son
-- equivalentes. Por ejemplo,
-- equivalentes 3205 41 == True
-- equivalentes 3205 25 == False
-- ---------------------------------------------------------------------
equivalentes :: Integer -> Integer -> Bool
equivalentes x y = undefined
-- ---------------------------------------------------------------------
-- Ejercicio 27. Un número x es especial si el número de ocurrencia de
-- cada dígito d de x en x^2 es el doble del número de ocurrencias de d
-- en x. Por ejemplo, 72576 es especial porque tiene un 2, un 5, un 6 y
-- dos 7 y su cuadrado es 5267275776 que tiene exactamente dos 2, dos 5,
-- dos 6 y cuatro 7.
--
-- Definir la función
-- especial :: Integer -> Bool
-- tal que (especial x) se verifica si x es un número especial. Por
-- ejemplo,
-- especial 72576 == True
-- especial 12 == False
-- Calcular el menor número especial mayor que 72576.
-- ---------------------------------------------------------------------
especial :: Integer -> Bool
especial x = undefined
-- El cálculo es
![Informática de 1º de Matemáticas [Curso 2021-22, Grupo 2]](/WIKIS/I1M2021G2/resources/assets/logoUS.png)