-- I1M 2021-22: Rel_3_sol.hs
-- Definiciones por comprensión
-- Departamento de Ciencias de la Computación e I.A.
-- Universidad de Sevilla
-- =====================================================================
-- ---------------------------------------------------------------------
-- Introducción --
-- ---------------------------------------------------------------------
-- En esta relación se presentan ejercicios con definiciones por
-- comprensión correspondientes al tema 5 que se encuentra
-- http://www.cs.us.es/~jalonso/cursos/i1m/temas/tema-5.html
-- ---------------------------------------------------------------------
-- Ejercicio 1. Definir, por comprensión, la función
-- sumaDeCuadrados :: Integer -> Integer
-- tal que (sumaDeCuadrados n) es la suma de los cuadrados de los
-- primeros n números; es decir, 1^2 + 2^2 + ... + n^2. Por ejemplo,
-- sumaDeCuadrados 3 == 14
-- sumaDeCuadrados 100 == 338350
-- ---------------------------------------------------------------------
sumaDeCuadrados :: Integer -> Integer
sumaDeCuadrados n = sum [x^2 | x <- [1..n]]
-- ---------------------------------------------------------------------
-- Ejercicio 2. Definir por comprensión la función
-- replica :: Int -> a -> [a]
-- tal que (replica n x) es la lista formada por n copias del elemento
-- x. Por ejemplo,
-- replica 4 7 == [7,7,7,7]
-- replica 3 True == [True, True, True]
-- Nota: La función replica es equivalente a la predefinida replicate.
-- ---------------------------------------------------------------------
replica :: Int -> a -> [a]
replica n x = [x | _ <- [1..n]]
-- ---------------------------------------------------------------------
-- Ejercicio 3.1. Definir la función
-- suma :: Integer -> Integer
-- tal (suma n) es la suma de los n primeros números. Por ejemplo,
-- suma 3 == 6
-- ---------------------------------------------------------------------
suma :: Integer -> Integer
suma n = sum [1..n]
-- Otra definición más eficiente es
suma2 :: Integer -> Integer
suma2 n = (1+n)*n `div` 2
-- ---------------------------------------------------------------------
-- Ejercicio 3.2. Los triángulos aritméticos se forman como sigue
-- 1
-- 2 3
-- 4 5 6
-- 7 8 9 10
-- 11 12 13 14 15
-- 16 17 18 19 20 21
-- Definir la función
-- linea :: Integer -> [Integer]
-- tal que (linea n) es la línea n-ésima de los triángulos
-- aritméticos. Por ejemplo,
-- linea 4 == [7,8,9,10]
-- linea 5 == [11,12,13,14,15]
-- ---------------------------------------------------------------------
linea :: Integer -> [Integer]
linea n = [suma (n-1)+1..suma n]
-- La definición puede mejorarse
linea2 :: Integer -> [Integer]
linea2 n = [s+1..s+n]
where s = suma (n-1)
-- Una variante más eficiente es
linea3 :: Integer -> [Integer]
linea3 n = [s+1..s+n]
where s = suma2 (n-1)
-- La mejora de la eficiencia se puede observar como sigue:
-- ghci> :set +s
-- ghci> head (linea 1000000)
-- 499999500001
-- (17.94 secs, 309207420 bytes)
-- ghci> head (linea3 1000000)
-- 499999500001
-- (0.01 secs, 525496 bytes)
-- ---------------------------------------------------------------------
-- Ejercicio 3.3. Definir la función
-- triangulo :: Integer -> [[Integer]]
-- tal que (triangulo n) es el triángulo aritmético de altura n. Por
-- ejemplo,
-- triangulo 3 == [[1],[2,3],[4,5,6]]
-- triangulo 4 == [[1],[2,3],[4,5,6],[7,8,9,10]]
-- ---------------------------------------------------------------------
triangulo :: Integer -> [[Integer]]
triangulo n = [linea m | m <- [1..n]]
-- ---------------------------------------------------------------------
-- Ejercicio 4. Un entero positivo es perfecto si es igual a la suma de
-- sus factores, excluyendo el propio número.
--
-- Definir por comprensión la función
-- perfectos :: Int -> [Int]
-- tal que (perfectos n) es la lista de todos los números perfectos
-- menores que n. Por ejemplo,
-- perfectos 500 == [6,28,496]
-- Indicación: Usar la función factores del tema 5.
-- ---------------------------------------------------------------------
-- La función factores del tema es
factores :: Int -> [Int]
factores n = [x | x <- [1..n-1], n `mod` x == 0]
-- La definición es
perfectos :: Int -> [Int]
perfectos n = [x | x <- [1..n], sum (init (factores x)) == x]
-- ---------------------------------------------------------------------
-- Ejercicio 5.1. Un número natural n se denomina abundante si es menor
-- que la suma de sus divisores propios. Por ejemplo, 12 y 30 son
-- abundantes pero 5 y 28 no lo son.
--
-- Definir la función
-- numeroAbundante :: Int -> Bool
-- tal que (numeroAbundante n) se verifica si n es un número
-- abundante. Por ejemplo,
-- numeroAbundante 5 == False
-- numeroAbundante 12 == True
-- numeroAbundante 28 == False
-- numeroAbundante 30 == True
-- ---------------------------------------------------------------------
divisores :: Int -> [Int]
divisores n = [m | m <- [1..n-1], n `mod` m == 0]
numeroAbundante :: Int -> Bool
numeroAbundante n = n < sum (divisores n)
-- ---------------------------------------------------------------------
-- Ejercicio 5.2. Definir la función
-- numerosAbundantesMenores :: Int -> [Int]
-- tal que (numerosAbundantesMenores n) es la lista de números
-- abundantes menores o iguales que n. Por ejemplo,
-- numerosAbundantesMenores 50 == [12,18,20,24,30,36,40,42,48]
-- numerosAbundantesMenores 48 == [12,18,20,24,30,36,40,42,48]
-- ---------------------------------------------------------------------
numerosAbundantesMenores :: Int -> [Int]
numerosAbundantesMenores n = [x | x <- [1..n], numeroAbundante x]
-- ---------------------------------------------------------------------
-- Ejercicio 5.3. Definir la función
-- todosPares :: Int -> Bool
-- tal que (todosPares n) se verifica si todos los números abundantes
-- menores o iguales que n son pares. Por ejemplo,
-- todosPares 10 == True
-- todosPares 100 == True
-- todosPares 1000 == False
-- ---------------------------------------------------------------------
todosPares :: Int -> Bool
todosPares n = and [even x | x <- numerosAbundantesMenores n]
-- ---------------------------------------------------------------------
-- Ejercicio 5.4. Definir la constante
-- primerAbundanteImpar :: Int
-- que calcule el primer número natural abundante impar. Determinar el
-- valor de dicho número.
-- ---------------------------------------------------------------------
primerAbundanteImpar :: Int
primerAbundanteImpar = head [x | x <- [1,3..], numeroAbundante x]
-- Su cálculo es
-- ghci> primerAbundanteImpar
-- 945
-- ---------------------------------------------------------------------
-- Ejercicio 6 (Problema 1 del proyecto Euler) Definir la función
-- euler1 :: Int -> Int
-- tal que (euler1 n) es la suma de todos los múltiplos de 3 ó 5 menores
-- que n. Por ejemplo,
-- euler1 10 == 23
--
-- Calcular la suma de todos los múltiplos de 3 ó 5 menores que 1000.
-- ---------------------------------------------------------------------
euler1 :: Int -> Int
euler1 n = sum [x | x <- [1..n-1], multiplo x 3 || multiplo x 5]
where multiplo x y = mod x y == 0
-- Cálculo:
-- ghci> euler1 1000
-- 233168
-- ---------------------------------------------------------------------
-- Ejercicio 7. Definir la función
-- circulo :: Int -> Int
-- tal que (circulo n) es el la cantidad de pares de números naturales
-- (x,y) que se encuentran dentro del círculo de radio n. Por ejemplo,
-- circulo 3 == 9
-- circulo 4 == 15
-- circulo 5 == 22
-- circulo 100 == 7949
-- ---------------------------------------------------------------------
circulo :: Int -> Int
circulo n = length [(x,y) | x <- [0..n], y <- [0..n], x*x+y*y < n*n]
-- La eficiencia puede mejorarse con
circulo2 :: Int -> Int
circulo2 n = length [(x,y) | x <- [0..n-1]
, y <- [0..raizCuadradaEntera (n*n - x*x)]
, x*x+y*y < n*n]
-- (raizCuadradaEntera n) es la parte entera de la raíz cuadrada de
-- n. Por ejemplo,
-- raizCuadradaEntera 17 == 4
raizCuadradaEntera :: Int -> Int
raizCuadradaEntera n = truncate (sqrt (fromIntegral n))
-- Comparación de eficiencia
-- λ> circulo (10^4)
-- 78549754
-- (73.44 secs, 44,350,688,480 bytes)
-- λ> circulo2 (10^4)
-- 78549754
-- (59.71 secs, 36,457,043,240 bytes)
-- ---------------------------------------------------------------------
-- Ejercicio 8.1. Definir la función
-- aproxE :: Double -> [Double]
-- tal que (aproXE n) es la lista cuyos elementos son los términos de la
-- sucesión (1+1/m)**m desde 1 hasta n. Por ejemplo,
-- aproxE 1 == [2.0]
-- aproxE 4 == [2.0,2.25,2.37037037037037,2.44140625]
-- ---------------------------------------------------------------------
aproxE :: Double -> [Double]
aproxE n = [(1+1/m)**m | m <- [1..n]]
-- ---------------------------------------------------------------------
-- Ejercicio 8.2. ¿Cuál es el límite de la sucesión (1+1/m)**m ?
-- ---------------------------------------------------------------------
-- El límite de la sucesión es el número e.
-- ---------------------------------------------------------------------
-- Ejercicio 8.3. Definir la función
-- errorAproxE :: Double -> Double
-- tal que (errorE x) es el menor número de términos de la sucesión
-- (1+1/m)**m necesarios para obtener su límite con un error menor que
-- x. Por ejemplo,
-- errorAproxE 0.1 == 13.0
-- errorAproxE 0.01 == 135.0
-- errorAproxE 0.001 == 1359.0
-- Indicación: En Haskell, e se calcula como (exp 1).
-- ---------------------------------------------------------------------
errorAproxE :: Double -> Double
errorAproxE x = head [m | m <- [1..], abs(exp 1 - (1+1/m)**m) < x]
-- ---------------------------------------------------------------------
-- Ejercicio 9.1. Definir la función
-- aproxLimSeno :: Double -> [Double]
-- tal que (aproxLimSeno n) es la lista cuyos elementos son los términos
-- de la sucesión
-- sen(1/m)
-- --------
-- 1/m
-- desde 1 hasta n. Por ejemplo,
-- aproxLimSeno 1 == [0.8414709848078965]
-- aproxLimSeno 2 == [0.8414709848078965,0.958851077208406]
-- ---------------------------------------------------------------------
aproxLimSeno :: Double -> [Double]
aproxLimSeno n = [sin(1/m)/(1/m) | m <- [1..n]]
-- ---------------------------------------------------------------------
-- Ejercicio 9.2. ¿Cuál es el límite de la sucesión sen(1/m)/(1/m) ?
-- ---------------------------------------------------------------------
-- El límite es 1.
-- ---------------------------------------------------------------------
-- Ejercicio 9.3. Definir la función
-- errorLimSeno :: Double -> Double
-- tal que (errorLimSeno x) es el menor número de términos de la sucesión
-- sen(1/m)/(1/m) necesarios para obtener su límite con un error menor
-- que x. Por ejemplo,
-- errorLimSeno 0.1 == 2.0
-- errorLimSeno 0.01 == 5.0
-- errorLimSeno 0.001 == 13.0
-- errorLimSeno 0.0001 == 41.0
-- ---------------------------------------------------------------------
errorLimSeno :: Double -> Double
errorLimSeno x = head [m | m <- [1..], abs(1 - sin(1/m)/(1/m)) < x]
-- ---------------------------------------------------------------------
-- Ejercicio 10.1. Definir la función
-- calculaPi :: Double -> Double
-- tal que (calculaPi n) es la aproximación del número pi calculada
-- mediante la expresión
-- 4*(1 - 1/3 + 1/5 - 1/7 + ...+ (-1)**n/(2*n+1))
-- Por ejemplo,
-- calculaPi 3 == 2.8952380952380956
-- calculaPi 300 == 3.1449149035588526
-- ---------------------------------------------------------------------
calculaPi :: Double -> Double
calculaPi n = 4 * sum [(-1)**x/(2*x+1) | x <- [0..n]]
-- ---------------------------------------------------------------------
-- Ejercicio 10.2. Definir la función
-- errorPi :: Double -> Double
-- tal que (errorPi x) es el menor número de términos de la serie
-- 4*(1 - 1/3 + 1/5 - 1/7 + ...+ (-1)**n/(2*n+1))
-- necesarios para obtener pi con un error menor que x. Por ejemplo,
-- errorPi 0.1 == 9.0
-- errorPi 0.01 == 99.0
-- errorPi 0.001 == 999.0
-- ---------------------------------------------------------------------
errorPi :: Double -> Double
errorPi x = head [n | n <- [1..]
, abs (pi - calculaPi n) < x]
-- ---------------------------------------------------------------------
-- Ejercicio 11.1. Una terna (x,y,z) de enteros positivos es pitagórica
-- si x^2 + y^2 = z^2.
--
-- Definir, por comprensión, la función
-- pitagoricas :: Int -> [(Int,Int,Int)]
-- tal que (pitagoricas n) es la lista de todas las ternas pitagóricas
-- cuyas componentes están entre 1 y n. Por ejemplo,
-- pitagoricas 10 == [(3,4,5),(4,3,5),(6,8,10),(8,6,10)]
-- ---------------------------------------------------------------------
pitagoricas :: Int -> [(Int,Int,Int)]
pitagoricas n = [(x,y,z) | x <- [1..n]
, y <- [1..n]
, z <- [1..n]
, x^2 + y^2 == z^2]
-- ---------------------------------------------------------------------
-- Ejercicio 11.2. Definir la función
-- numeroDePares :: (Int,Int,Int) -> Int
-- tal que (numeroDePares t) es el número de elementos pares de la terna
-- t. Por ejemplo,
-- numeroDePares (3,5,7) == 0
-- numeroDePares (3,6,7) == 1
-- numeroDePares (3,6,4) == 2
-- numeroDePares (4,6,4) == 3
-- ---------------------------------------------------------------------
numeroDePares :: (Int,Int,Int) -> Int
numeroDePares (x,y,z) = length [1 | n <- [x,y,z], even n]
-- ---------------------------------------------------------------------
-- Ejercicio 11.3. Definir la función
-- conjetura :: Int -> Bool
-- tal que (conjetura n) se verifica si todas las ternas pitagóricas
-- cuyas componentes están entre 1 y n tiene un número impar de números
-- pares. Por ejemplo,
-- conjetura 10 == True
-- ---------------------------------------------------------------------
conjetura :: Int -> Bool
conjetura n = and [odd (numeroDePares t) | t <- pitagoricas n]
-- ---------------------------------------------------------------------
-- Ejercicio 11.4. Demostrar la conjetura para todas las ternas
-- pitagóricas.
-- ---------------------------------------------------------------------
-- Sea (x,y,z) una terna pitagórica. Entonces x^2+y^2=z^2. Pueden darse
-- 4 casos:
--
-- Caso 1: x e y son pares. Entonces, x^2, y^2 y z^2 también lo
-- son. Luego el número de componentes pares es 3 que es impar.
--
-- Caso 2: x es par e y es impar. Entonces, x^2 es par, y^2 es impar y
-- z^2 es impar. Luego el número de componentes pares es 1 que es impar.
--
-- Caso 3: x es impar e y es par. Análogo al caso 2.
--
-- Caso 4: x e y son impares. Entonces, x^2 e y^2 también son impares y
-- z^2 es par. Luego el número de componentes pares es 1 que es impar.
-- ---------------------------------------------------------------------
-- Ejercicio 12.1. (Problema 9 del Proyecto Euler). Una terna pitagórica
-- es una terna de números naturales (a,b,c) tal que a<b<c y
-- a^2+b^2=c^2. Por ejemplo (3,4,5) es una terna pitagórica.
--
-- Definir la función
-- ternasPitagoricas :: Integer -> [[Integer]]
-- tal que (ternasPitagoricas x) es la lista de las ternas pitagóricas
-- cuya suma es x. Por ejemplo,
-- ternasPitagoricas 12 == [(3,4,5)]
-- ternasPitagoricas 60 == [(10,24,26),(15,20,25)]
-- ---------------------------------------------------------------------
ternasPitagoricas :: Integer -> [(Integer,Integer,Integer)]
ternasPitagoricas x = [(a,b,c) | a <- [1..x],
b <- [a+1..x],
c <- [x-a-b],
a^2 + b^2 == c^2]
-- ---------------------------------------------------------------------
-- Ejercicio 12.2. Definir la constante
-- euler9 :: Integer
-- tal que euler9 es producto abc donde (a,b,c) es la única terna
-- pitagórica tal que a+b+c=1000.
--
-- Calcular el valor de euler9.
-- ---------------------------------------------------------------------
euler9 :: Integer
euler9 = a*b*c
where (a,b,c) = head (ternasPitagoricas 1000)
-- El cálculo del valor de euler9 es
-- ghci> euler9
-- 31875000
-- ---------------------------------------------------------------------
-- Ejercicio 13. El producto escalar de dos listas de enteros xs y ys de
-- longitud n viene dado por la suma de los productos de los elementos
-- correspondientes.
--
-- Definir por comprensión la función
-- productoEscalar :: [Int] -> [Int] -> Int
-- tal que (productoEscalar xs ys) es el producto escalar de las listas
-- xs e ys. Por ejemplo,
-- productoEscalar [1,2,3] [4,5,6] == 32
-- ---------------------------------------------------------------------
productoEscalar :: [Int] -> [Int] -> Int
productoEscalar xs ys = sum [x*y | (x,y) <- zip xs ys]
-- ---------------------------------------------------------------------
-- Ejercicio 14. Definir, por comprensión, la función
-- sumaConsecutivos :: [Int] -> [Int]
-- tal que (sumaConsecutivos xs) es la suma de los pares de elementos
-- consecutivos de la lista xs. Por ejemplo,
-- sumaConsecutivos [3,1,5,2] == [4,6,7]
-- sumaConsecutivos [3] == []
-- ---------------------------------------------------------------------
sumaConsecutivos :: [Int] -> [Int]
sumaConsecutivos xs = [x+y | (x,y) <- zip xs (tail xs)]
-- ---------------------------------------------------------------------
-- Ejercicio 15. Los polinomios pueden representarse de forma dispersa o
-- densa. Por ejemplo, el polinomio 6x^4-5x^2+4x-7 se puede representar
-- de forma dispersa por [6,0,-5,4,-7] y de forma densa por
-- [(4,6),(2,-5),(1,4),(0,-7)].
--
-- Definir la función
-- densa :: [Int] -> [(Int,Int)]
-- tal que (densa xs) es la representación densa del polinomio cuya
-- representación dispersa es xs. Por ejemplo,
-- densa [6,0,-5,4,-7] == [(4,6),(2,-5),(1,4),(0,-7)]
-- densa [6,0,0,3,0,4] == [(5,6),(2,3),(0,4)]
-- ---------------------------------------------------------------------
densa :: [Int] -> [(Int,Int)]
densa xs = [(x,y) | (x,y) <- zip [n-1,n-2..0] xs, y /= 0]
where n = length xs
-- ---------------------------------------------------------------------
-- Ejercicio 16. La bases de datos sobre actividades de personas pueden
-- representarse mediante listas de elementos de la forma (a,b,c,d),
-- donde a es el nombre de la persona, b su actividad, c su fecha de
-- nacimiento y d la de su fallecimiento. Un ejemplo es la siguiente que
-- usaremos a lo largo de este ejercicio,
-- ---------------------------------------------------------------------
personas :: [(String,String,Int,Int)]
personas = [("Cervantes","Literatura",1547,1616),
("Velazquez","Pintura",1599,1660),
("Picasso","Pintura",1881,1973),
("Beethoven","Musica",1770,1823),
("Poincare","Ciencia",1854,1912),
("Quevedo","Literatura",1580,1654),
("Goya","Pintura",1746,1828),
("Einstein","Ciencia",1879,1955),
("Mozart","Musica",1756,1791),
("Botticelli","Pintura",1445,1510),
("Borromini","Arquitectura",1599,1667),
("Bach","Musica",1685,1750)]
-- ---------------------------------------------------------------------
-- Ejercicio 16.1. Definir la función
-- nombres :: [(String,String,Int,Int)] -> [String]
-- tal que (nombres bd) es la lista de los nombres de las personas de la
-- base de datos bd. Por ejemplo,
-- ghci> nombres personas
-- ["Cervantes","Velazquez","Picasso","Beethoven","Poincare",
-- "Quevedo","Goya","Einstein","Mozart","Botticelli","Borromini","Bach"]
-- ---------------------------------------------------------------------
nombres :: [(String,String,Int,Int)] -> [String]
nombres bd = [x | (x,_,_,_) <- bd]
-- ---------------------------------------------------------------------
-- Ejercicio 16.2. Definir la función
-- musicos :: [(String,String,Int,Int)] -> [String]
-- tal que (musicos bd) es la lista de los nombres de los músicos de la
-- base de datos bd. Por ejemplo,
-- musicos personas == ["Beethoven","Mozart","Bach"]
-- ---------------------------------------------------------------------
musicos :: [(String,String,Int,Int)] -> [String]
musicos bd = [x | (x,"Musica",_,_) <- bd]
-- ---------------------------------------------------------------------
-- Ejercicio 16.3. Definir la función
-- seleccion :: [(String,String,Int,Int)] -> String -> [String]
-- tal que (seleccion bd m) es la lista de los nombres de las personas
-- de la base de datos bd cuya actividad es m. Por ejemplo,
-- ghci> seleccion personas "Pintura"
-- ["Velazquez","Picasso","Goya","Botticelli"]
-- ghci> seleccion personas "Musica"
-- ["Beethoven","Mozart","Bach"]
-- ---------------------------------------------------------------------
seleccion :: [(String,String,Int,Int)] -> String -> [String]
seleccion bd m = [ x | (x,m',_,_) <- bd, m == m' ]
-- ---------------------------------------------------------------------
-- Ejercicio 16.4. Definir, usando el apartado anterior, la función
-- musicos' :: [(String,String,Int,Int)] -> [String]
-- tal que (musicos' bd) es la lista de los nombres de los músicos de la
-- base de datos bd. Por ejemplo,
-- ghci> musicos' personas
-- ["Beethoven","Mozart","Bach"]
-- ---------------------------------------------------------------------
musicos' :: [(String,String,Int,Int)] -> [String]
musicos' bd = seleccion bd "Musica"
-- ---------------------------------------------------------------------
-- Ejercicio 16.5. Definir la función
-- vivas :: [(String,String,Int,Int)] -> Int -> [String]
-- tal que (vivas bd a) es la lista de los nombres de las personas de la
-- base de datos bd que estaban vivas en el año a. Por ejemplo,
-- ghci> vivas personas 1600
-- ["Cervantes","Velazquez","Quevedo","Borromini"]
-- ---------------------------------------------------------------------
vivas :: [(String,String,Int,Int)] -> Int -> [String]
vivas ps a = [x | (x,_,a1,a2) <- ps, a1 <= a, a <= a2]
![Informática de 1º de Matemáticas [Curso 2021-22, Grupo 2]](/WIKIS/I1M2021G2/resources/assets/logoUS.png)