Relación 6

-- I1M 2021-22: Rel_6.hs (5 de noviembre de 2021)
-- 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

-- ---------------------------------------------------------------------
-- 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
-- ---------------------------------------------------------------------
-- Lucía Hernández
potencia :: Integer -> Integer -> Integer
potencia _ 0 = 1
potencia x n = x* potencia x (n-1)

-- Nicolás Rodríguez Ruiz
potencia :: Integer -> Integer -> Integer
potencia _ 0 = 1
potencia x n | n > 0 = x * potencia x (n-1)
             | n < 0 = error "n tiene que ser un natural (>=0)"

-- ---------------------------------------------------------------------
-- Ejercicio 1.2. Comprobar con QuickCheck que la función potencia es
-- equivalente a la predefinida (^).
-- ---------------------------------------------------------------------
-- Lucía Hernández
-- La propiedad es
prop_potencia :: Integer -> Integer -> Property
prop_potencia x n = n>=0 ==> x^n == potencia x n

-- La comprobación es 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
-- ---------------------------------------------------------------------
-- Lucía Hernández, Nicolás Rodríguez Ruiz
mcd :: Integer -> Integer -> Integer
mcd a 0 = a
mcd a b = mcd b (mod a 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. 
-- ---------------------------------------------------------------------
-- Lucía Hernández
-- La propiedad es
prop_mcd :: Integer -> Integer -> Property
prop_mcd a b = a>0 && b>0 ==> mcd a b >=1 && mcd a b <= min a b

-- Su comprobación es 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.  
-- ---------------------------------------------------------------------
--- Lucía Hernández
-- La propiedad es
prop_mcd_div :: Integer -> Integer -> Property
prop_mcd_div a b = a>0 && b>0 ==> (mcd a b) <= div (max a b)2

-- La comprobación es quickCheck prop_mcd_div
*** Failed! Falsifiable (after 1 test):
1
1
-- Nicolás Rodríguez Ruiz
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

-- La comprobación es
-- +++ OK, passed 100 tests; 407 discarded.
-- ---------------------------------------------------------------------
-- 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
-- ---------------------------------------------------------------------
-- Lucía Hernández
pertenece :: Eq a => a -> [a] -> Bool
pertenece _ [] = False
pertenece n (x:xs) | n == x = True
                   |otherwise =  pertenece n xs
-- Nicolás Rodríguez Ruiz
pertenece :: Eq a => a -> [a] -> Bool
pertenece _ [] = False
pertenece y (x:xs) = y==x || pertenece y xs
-- ---------------------------------------------------------------------
-- Ejercicio 3.2. Comprobar con quickCheck que pertenece es equivalente
-- a elem. 
-- ---------------------------------------------------------------------
-- Lucía Hernández
-- La propiedad es
prop_pertenece :: Int -> [Int] -> Bool
prop_pertenece x xs = pertenece x xs == elem x xs

-- La comprobación es 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]
-- ---------------------------------------------------------------------
-- Lucía Hernández , Nicolás Rodríguez Ruiz
concatenaListas :: [[a]] -> [a]
concatenaListas  []  = []
concatenaListas (xs:xss) = xs ++ concatenaListas xss
-- ---------------------------------------------------------------------
-- Ejercicio 4.2. Comprobar con QuickCheck que concatenaListas es
-- equivalente a concat. 
-- ---------------------------------------------------------------------

-- Nicolás Rodrígez Ruiz
-- La propiedad es
prop_concat :: [[Int]] -> Bool
prop_concat xss = concat xss == concatenaListas xss

-- La comprobación es
-- +++ 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 (-3) [4..12]  ==  []
-- ---------------------------------------------------------------------
-- Lucía Hernández, Nicolás Rodríguez Ruiz
coge :: Int -> [a] -> [a]
coge _ [] = []
coge n (x:xs) | n<=0 = []
              | otherwise = x : coge (n-1) xs

-- ---------------------------------------------------------------------
-- Ejercicio 5.2. Comprobar con QuickCheck que coge es equivalente a
-- take. 
-- ---------------------------------------------------------------------
-- Lucía Hernández, Nicolás Rodríguez Ruiz
-- La propiedad es
prop_coge :: Int -> [Int] -> Bool
prop_coge n xs = coge n xs == take n xs

-- La comprobación es quickCheck  prop_coge
+++ OK, passed 100 tests

-- ---------------------------------------------------------------------
-- 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 
-- ---------------------------------------------------------------------
-- Lucía Hernández, Nicolás Rodríguez Ruiz
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. 
-- ---------------------------------------------------------------------
-- Lucía Hernández
-- La propiedad es
prop_SumaCuadrados :: Integer -> Property
prop_SumaCuadrados n = n>=1 ==> sumaCuadradosR n == div (n*(n+1)*(2*n+1)) 6

-- La comprobación es  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 
-- ---------------------------------------------------------------------
-- Lucía Hernández
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. 
-- ---------------------------------------------------------------------
-- Lucía Hernández
-- La propiedad es
prop_sumaCuadradosR :: Integer -> Property
prop_sumaCuadradosR n = n>=1 ==> sumaCuadradosR n == sumaCuadradosC n

-- La comprobación es  quickCheck  prop_sumaCuadradosR
-- +++ 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]
-- ---------------------------------------------------------------------
-- Lucía Hernández
digitosR :: Integer -> [Integer]
digitosR n = if n<10 then [n]
          else   digitosR (div n 10) ++ [rem n 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.
-- ---------------------------------------------------------------------

-- Lucía Hernández
digitosC :: Integer -> [Integer]
digitosC n = [read [x] | x <- show n]
-- ---------------------------------------------------------------------
-- Ejercicio 7.3. Comprobar con QuickCheck que las funciones digitosR y
-- digitosC son equivalentes.
-- ---------------------------------------------------------------------
-- Lucía Hernández
-- La propiedad es
prop_digitos :: Integer -> Property
prop_digitos n = n>=0 ==> digitosR n == digitosC n
  
-- La comprobación es 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
-- ---------------------------------------------------------------------
-- Lucía Hernández
sumaDigitosR :: Integer -> Integer
sumaDigitosR n = if n<10 then n
                else rem n 10 + sumaDigitosR (div n 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
-- ---------------------------------------------------------------------
-- Lucía Hernández
sumaDigitosNR :: Integer -> Integer
sumaDigitosNR n = sum (digitosR n)

-- ---------------------------------------------------------------------
-- Ejercicio 8.3. Comprobar con QuickCheck que las funciones sumaDigitosR
-- y sumaDigitosNR son equivalentes.
-- ---------------------------------------------------------------------
-- Lucía Hernández
-- La propiedad es
prop_sumaDigitos :: Integer -> Property
prop_sumaDigitos n = n>= 0 ==> sumaDigitosR n  == sumaDigitosNR n


-- La comprobación es  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
-- ---------------------------------------------------------------------
-- Lucía Hernández
listaNumeroR :: [Integer] -> Integer
listaNumeroR [] = 0
listaNumeroR [x] = x
listaNumeroR (x:xs) = x*10^(length (xs)) + listaNumeroR 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
-- ---------------------------------------------------------------------
-- Lucía Hernández
listaNumeroC :: [Integer] -> Integer
listaNumeroC xs = sum [x*10^s | (x,s) <- zip(reverse xs) [0..length xs -1]]

-- ---------------------------------------------------------------------
-- Ejercicio 9.3. Comprobar con QuickCheck que las funciones
-- listaNumeroR y listaNumeroC son equivalentes.
-- ---------------------------------------------------------------------
--Lucía Hernández
-- La propiedad es
prop_listaNumero :: [Integer] -> Bool
prop_listaNumero xs = listaNumeroR xs == listaNumeroC xs

-- La comprobación es quickCheck prop_listaNumero
+++ OK, passed 100 tests.

-- ---------------------------------------------------------------------
-- 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
-- ---------------------------------------------------------------------
-- Lucía Hernández
mayorExponenteR :: Integer -> Integer -> Integer
mayorExponenteR  _ 0 = 0
mayorExponenteR a b | mod b (a) == 0 = 1 + mayorExponenteR a( div b a)
                    | otherwise = 0
  

-- ---------------------------------------------------------------------
-- 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
-- ---------------------------------------------------------------------
-- Lucía Hernández
mayorExponenteC :: Integer -> Integer -> Integer
mayorExponenteC a b = last [s | s<- [0..b], mod b (a^s) == 0]