-- I1M 2021-22: Rel_6_sol.hs
-- Definiciones por recursió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
-- recursión correspondientes al tema 6 cuyas transparencias se
-- encuentran en
-- http://www.cs.us.es/~jalonso/cursos/i1m/temas/tema-6.html
-- ---------------------------------------------------------------------
-- Importación de librerías auxiliares --
-- ---------------------------------------------------------------------
import Test.QuickCheck
import Data.Char
-- ---------------------------------------------------------------------
-- Ejercicio 1.1. Definir por recursión la función
-- potencia :: Integer -> Integer -> Integer
-- tal que (potencia x n) es x elevado al número natural n. Por ejemplo,
-- potencia 2 3 == 8
-- ---------------------------------------------------------------------
potencia :: Integer -> Integer -> Integer
potencia _ 0 = 1
potencia m n = m * potencia m (n-1)
-- ---------------------------------------------------------------------
-- Ejercicio 1.2. Comprobar con QuickCheck que la función potencia es
-- equivalente a la predefinida (^).
-- ---------------------------------------------------------------------
-- La propiedad es
prop_potencia :: Integer -> Integer -> Property
prop_potencia x n =
n >= 0 ==> potencia x n == x^n
-- La comprobación es
-- ghci> quickCheck prop_potencia
-- +++ OK, passed 100 tests.
-- ---------------------------------------------------------------------
-- Ejercicio 2.1. Dados dos números naturales, a y b, es posible
-- calcular su máximo común divisor mediante el Algoritmo de
-- Euclides. Este algoritmo se puede resumir en la siguiente fórmula:
-- mcd(a,b) = a, si b = 0
-- = mcd (b, a módulo b), si b > 0
--
-- Definir la función
-- mcd :: Integer -> Integer -> Integer
-- tal que (mcd a b) es el máximo común divisor de a y b calculado
-- mediante el algoritmo de Euclides. Por ejemplo,
-- mcd 30 45 == 15
-- ---------------------------------------------------------------------
mcd :: Integer -> Integer -> Integer
mcd a 0 = a
mcd a b = mcd b (a `mod` b)
-- ---------------------------------------------------------------------
-- Ejercicio 2.2. Definir y comprobar la propiedad prop_mcd según la
-- cual el máximo común divisor de dos números a y b (ambos mayores que
-- 0) es siempre mayor o igual que 1 y además es menor o igual que el
-- menor de los números a y b.
-- ---------------------------------------------------------------------
-- La propiedad es
prop_mcd :: Integer -> Integer -> Property
prop_mcd a b =
a > 0 && b > 0 ==> m >= 1 && m <= min a b
where m = mcd a b
-- La comprobación es
-- ghci> quickCheck prop_mcd
-- OK, passed 100 tests.
-- ---------------------------------------------------------------------
-- Ejercicio 2.3. Teniendo en cuenta que buscamos el máximo común
-- divisor de a y b, sería razonable pensar que el máximo común divisor
-- siempre sería igual o menor que la mitad del máximo de a y b. Definir
-- esta propiedad y comprobarla.
-- ---------------------------------------------------------------------
-- La propiedad es
prop_mcd_div :: Integer -> Integer -> Property
prop_mcd_div a b =
a > 0 && b > 0 ==> mcd a b <= max a b `div` 2
-- Al verificarla, se obtiene
-- ghci> quickCheck prop_mcd_div
-- Falsifiable, after 0 tests:
-- 3
-- 3
-- que la refuta. Pero si la modificamos ańadiendo la hipótesis que los números
-- son distintos,
prop_mcd_div' :: Integer -> Integer -> Property
prop_mcd_div' a b =
a > 0 && b > 0 && a /= b ==> mcd a b <= max a b `div` 2
-- entonces al comprobarla
-- ghci> quickCheck prop_mcd_div'
-- OK, passed 100 tests.
-- obtenemos que se verifica.
-- ---------------------------------------------------------------------
-- Ejercicio 3.1, Definir por recursión la función
-- pertenece :: Eq a => a -> [a] -> Bool
-- tal que (pertenece x xs) se verifica si x pertenece a la lista xs. Por
-- ejemplo,
-- pertenece 3 [2,3,5] == True
-- pertenece 4 [2,3,5] == False
-- ---------------------------------------------------------------------
pertenece :: Eq a => a -> [a] -> Bool
pertenece _ [] = False
pertenece x (y:ys) = x == y || pertenece x ys
-- ---------------------------------------------------------------------
-- Ejercicio 3.2. Comprobar con quickCheck que pertenece es equivalente
-- a elem.
-- ---------------------------------------------------------------------
-- La propiedad es
prop_pertenece :: Eq a => a -> [a] -> Bool
prop_pertenece x xs = pertenece x xs == elem x xs
-- La comprobación es
-- ghci> quickCheck prop_pertenece
-- +++ OK, passed 100 tests.
-- ---------------------------------------------------------------------
-- Ejercicio 4.1. Definir por recursión la función
-- concatenaListas :: [[a]] -> [a]
-- tal que (concatenaListas xss) es la lista obtenida concatenando las listas de
-- xss. Por ejemplo,
-- concatenaListas [[1..3],[5..7],[8..10]] == [1,2,3,5,6,7,8,9,10]
-- ---------------------------------------------------------------------
concatenaListas :: [[a]] -> [a]
concatenaListas [] = []
concatenaListas (xs:xss) = xs ++ concatenaListas xss
-- ---------------------------------------------------------------------
-- Ejercicio 4.2. Comprobar con QuickCheck que concatenaListas es
-- equivalente a concat.
-- ---------------------------------------------------------------------
-- La propiedad es
prop_concat :: Eq a => [[a]] -> Bool
prop_concat xss = concatenaListas xss == concat xss
-- La comprobación es
-- ghci> quickCheck prop_concat
-- +++ OK, passed 100 tests.
-- ---------------------------------------------------------------------
-- Ejercicio 5.1. Definir por recursión la función
-- coge :: Int -> [a] -> [a]
-- tal que (coge n xs) es la lista de los n primeros elementos de
-- xs. Por ejemplo,
-- coge 3 [4..12] => [4,5,6]
-- ---------------------------------------------------------------------
coge :: Int -> [a] -> [a]
coge n _ | n <= 0 = []
coge _ [] = []
coge n (x:xs) = x : coge (n-1) xs
-- ---------------------------------------------------------------------
-- Ejercicio 5.2. Comprobar con QuickCheck que coge es equivalente a
-- take.
-- ---------------------------------------------------------------------
-- La propiedad es
prop_coge :: Int -> [Int] -> Bool
prop_coge n xs =
coge n xs == take n xs
-- ---------------------------------------------------------------------
-- Ejercicio 6.1. Definir, por recursión, la función
-- sumaCuadradosR :: Integer -> Integer
-- tal que (sumaCuadradosR n) es la suma de los cuadrados de los números
-- de 1 a n. Por ejemplo,
-- sumaCuadradosR 4 == 30
-- ---------------------------------------------------------------------
sumaCuadradosR :: Integer -> Integer
sumaCuadradosR 0 = 0
sumaCuadradosR n = n^2 + sumaCuadradosR (n-1)
-- ---------------------------------------------------------------------
-- Ejercicio 6.2. Comprobar con QuickCheck si sumaCuadradosR n es igual a
-- n(n+1)(2n+1)/6.
-- ---------------------------------------------------------------------
-- La propiedad es
prop_SumaCuadrados :: Integer -> Property
prop_SumaCuadrados n =
n >= 0 ==>
sumaCuadradosR n == n * (n+1) * (2*n+1) `div` 6
-- La comprobación es
-- ghci> quickCheck prop_SumaCuadrados
-- OK, passed 100 tests.
-- ---------------------------------------------------------------------
-- Ejercicio 6.3. Definir, por comprensión, la función
-- sumaCuadradosC :: Integer --> Integer
-- tal que (sumaCuadradosC n) es la suma de los cuadrados de los números
-- de 1 a n. Por ejemplo,
-- sumaCuadradosC 4 == 30
-- ---------------------------------------------------------------------
sumaCuadradosC :: Integer -> Integer
sumaCuadradosC n = sum [x^2 | x <- [1..n]]
-- ---------------------------------------------------------------------
-- Ejercicio 6.4. Comprobar con QuickCheck que las funciones
-- sumaCuadradosR y sumaCuadradosC son equivalentes sobre los números
-- naturales.
-- ---------------------------------------------------------------------
-- La propiedad es
prop_sumaCuadradosR :: Integer -> Property
prop_sumaCuadradosR n =
n >= 0 ==> sumaCuadradosR n == sumaCuadradosC n
-- La comprobación es
-- ghci> quickCheck prop_sumaCuadrados
-- +++ OK, passed 100 tests.
-- ---------------------------------------------------------------------
-- Ejercicio 7.1. Definir, por recursión, la función
-- digitosR :: Integer -> [Integer]
-- tal que (digitosR n) es la lista de los dígitos del número n. Por
-- ejemplo,
-- digitosR 320274 == [3,2,0,2,7,4]
-- ---------------------------------------------------------------------
digitosR :: Integer -> [Integer]
digitosR n = reverse (digitosR' n)
digitosR' :: Integer -> [Integer]
digitosR' n
| n < 10 = [n]
| otherwise = (n `rem` 10) : digitosR' (n `div` 10)
-- ---------------------------------------------------------------------
-- Ejercicio 7.2. Definir, por comprensión, la función
-- digitosC :: Integer -> [Integer]
-- tal que (digitosC n) es la lista de los dígitos del número n. Por
-- ejemplo,
-- digitosC 320274 == [3,2,0,2,7,4]
-- Indicación: Usar las funciones show y read.
-- ---------------------------------------------------------------------
digitosC :: Integer -> [Integer]
digitosC n = [read [x] | x <- show n]
-- ---------------------------------------------------------------------
-- Ejercicio 7.3. Comprobar con QuickCheck que las funciones digitosR y
-- digitosC son equivalentes.
-- ---------------------------------------------------------------------
-- La propiedad es
prop_digitos :: Integer -> Property
prop_digitos n =
n >= 0 ==>
digitosR n == digitosC n
-- La comprobación es
-- ghci> quickCheck prop_digitos
-- +++ OK, passed 100 tests.
-- ---------------------------------------------------------------------
-- Ejercicio 8.1. Definir, por recursión, la función
-- sumaDigitosR :: Integer -> Integer
-- tal que (sumaDigitosR n) es la suma de los dígitos de n. Por ejemplo,
-- sumaDigitosR 3 == 3
-- sumaDigitosR 2454 == 15
-- sumaDigitosR 20045 == 11
-- ---------------------------------------------------------------------
sumaDigitosR :: Integer -> Integer
sumaDigitosR n
| n < 10 = n
| otherwise = n `rem` 10 + sumaDigitosR (n `div` 10)
-- ---------------------------------------------------------------------
-- Ejercicio 8.2. Definir, sin usar recursión, la función
-- sumaDigitosNR :: Integer -> Integer
-- tal que (sumaDigitosNR n) es la suma de los dígitos de n. Por ejemplo,
-- sumaDigitosNR 3 == 3
-- sumaDigitosNR 2454 == 15
-- sumaDigitosNR 20045 == 11
-- ---------------------------------------------------------------------
sumaDigitosNR :: Integer -> Integer
sumaDigitosNR n = sum (digitosC n)
-- ---------------------------------------------------------------------
-- Ejercicio 8.3. Comprobar con QuickCheck que las funciones sumaDigitosR
-- y sumaDigitosNR son equivalentes.
-- ---------------------------------------------------------------------
-- La propiedad es
prop_sumaDigitos :: Integer -> Property
prop_sumaDigitos n =
n >= 0 ==>
sumaDigitosR n == sumaDigitosNR n
-- La comprobación es
-- ghci> quickCheck prop_sumaDigitos
-- +++ OK, passed 100 tests.
-- ---------------------------------------------------------------------
-- Ejercicio 9.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
-- ---------------------------------------------------------------------
-- 1Ş solución
listaNumeroR :: [Integer] -> Integer
listaNumeroR xs = listaNumeroR' (reverse xs)
listaNumeroR' :: [Integer] -> Integer
listaNumeroR' [x] = x
listaNumeroR' (x:xs) = x + 10 * listaNumeroR' xs
listaNumeroR' [] = error "un numero sin digitos?"
-- 2Ş solución
listaNumeroR'' :: [Integer] -> Integer
listaNumeroR'' [] = error "un numero sin digitos?"
listaNumeroR'' [x] = x
listaNumeroR'' (x:xs) = x*10^n + listaNumeroR'' xs
where n = length xs
-- ---------------------------------------------------------------------
-- Ejercicio 9.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
-- ---------------------------------------------------------------------
-- 1Ş definición:
listaNumeroC1 :: [Integer] -> Integer
listaNumeroC1 xs = sum [y*10^n | (y,n) <- zip (reverse xs) [0..]]
-- 2Ş definición:
listaNumeroC2 :: [Integer] -> Integer
listaNumeroC2 xs = sum [y*10^n | (y,n) <- zip xs [n,n-1..0]]
where n = length xs -1
-- 3Ş definición:
listaNumeroC :: [Integer] -> Integer
listaNumeroC xs = read [x | x <- show xs, isDigit x]
-- ---------------------------------------------------------------------
-- Ejercicio 9.3. Comprobar con QuickCheck que las funciones
-- listaNumeroR y listaNumeroC son equivalentes.
-- ---------------------------------------------------------------------
-- La propiedad siguiente fallaría (żqué sucede con la lista vacía?)
prop_listaNumero' :: [Integer] -> Bool
prop_listaNumero' xs =
listaNumeroR xs == listaNumeroC xs
-- La propiedad siguiente también fallaría, pero no con lista vacía
-- (żqué sucede si quickcheck intenta comprobar la lista [-1,10]?)
prop_listaNumero'' :: [Integer] -> Property
prop_listaNumero'' xs = xs /= [] ==>
listaNumeroR xs == listaNumeroC xs
-- La propiedad siguiente sí funcionaría, pero imponte tantas
-- restricciones que al final se descartan la mayoría de los intentos
-- que hace quickcheck
prop_listaNumero''' :: [Integer] -> Property
prop_listaNumero''' xs = xs /= [] && sonTodosDigitos ==>
listaNumeroR xs == listaNumeroC xs
where sonTodosDigitos = and [ x >=0 && x <= 9 | x <- xs]
-- La propiedad siguiente funcionaría, porque aprovechamos el intento
-- en la mayoría de los casos (lo convertimos a lista de dígitos)
prop_listaNumero :: [Integer] -> Property
prop_listaNumero xs = xs /= [] ==>
listaNumeroR ys == listaNumeroC ys
where ys = [ rem (abs x) 10 | x <- xs]
-- La comprobación es
-- ghci> quickCheck prop_listaNumero
-- +++ OK, passed 100 tests; 15 discarded.
-- ---------------------------------------------------------------------
-- Ejercicio 10.1. Definir, por recursión, la función
-- mayorExponenteR :: Integer -> Integer -> Integer
-- tal que (mayorExponenteR a b) es el exponente de la mayor potencia de
-- a que divide b. Por ejemplo,
-- mayorExponenteR 2 8 == 3
-- mayorExponenteR 2 9 == 0
-- mayorExponenteR 5 100 == 2
-- mayorExponenteR 2 60 == 2
-- ---------------------------------------------------------------------
mayorExponenteR :: Integer -> Integer -> Integer
mayorExponenteR a b
| rem b a /= 0 = 0
| otherwise = 1 + mayorExponenteR a (b `div` a)
-- ---------------------------------------------------------------------
-- Ejercicio 10.2. Definir, por comprensión, la función
-- mayorExponenteC :: Integer -> Integer -> Integer
-- tal que (mayorExponenteC a b) es el exponente de la mayor potencia de
-- a que divide a b. Por ejemplo,
-- mayorExponenteC 2 8 == 3
-- mayorExponenteC 5 100 == 2
-- mayorExponenteC 5 101 == 0
-- ---------------------------------------------------------------------
mayorExponenteC :: Integer -> Integer -> Integer
mayorExponenteC a b = head [x-1 | x <- [0..], mod b (a^x) /= 0]
![Informática de 1º de Matemáticas [Curso 2021-22, Grupo 2]](/WIKIS/I1M2021G2/resources/assets/logoUS.png)