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, Irene Ortega, Ana Sánchez Martín
potencia :: Integer -> Integer -> Integer
potencia _ 0 = 1
potencia x n = x* potencia x (n-1)

-- Nicolás Rodríguez Ruiz, Elsa Domínguez, Adolfo Sagrera Vivancos, Ana Sosa Caballero
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, Irene Ortega, Elsa Domínguez, Adolfo Sagrera Vivancos, Ana Sánchez Martín, Ana Sosa Caballero
-- 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, Irene Ortega, Elsa Domínguez, Ana Sosa Caballero
mcd :: Integer -> Integer -> Integer
mcd a 0 = a
mcd a b = mcd b (mod a b)
-- Adolfo Sagrera Vivancos, Ana Sánchez Martín
mcd1 :: Integer -> Integer -> Integer
mcd1 a b | b==0 = a
        | b > 0 = 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, Irene Ortega, Elsa Domínguez, Adolfo Sagrera Vivancos, Ana Sánchez Martín, Ana Sosa Caballero
-- 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, Irene Ortega, Elsa Domínguez, Adolfo Sagrera Vivancos, Ana Sánchez Martín, Ana Sosa Caballero
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, Irene Ortega, Ana Sánchez Martín, Ana Sosa Caballero
pertenece :: Eq a => a -> [a] -> Bool
pertenece _ [] = False
pertenece n (x:xs) | n == x = True
                   |otherwise =  pertenece n xs
-- Nicolás Rodríguez Ruiz, Elsa Domínguez, Adolfo Sagrera Vivancos
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, Irene Ortega, Elsa Domínguez, Adolfo Sagrera Vivancos, Ana Sánchez Martín, Ana Sosa Caballero
-- 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, Elsa Domínguez, Adolfo Sagrera Vivancos, Ana Sánchez Martín, Ana Sosa Caballero
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, Elsa Domínguez, Adolfo Sagrera Vivancos, Ana Sánchez Martín, Ana Sosa Caballero
-- 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, Elsa Domínguez, Adolfo Sagrera Vivancos, Ana Sánchez Martín
coge :: Int -> [a] -> [a]
coge _ [] = []
coge n (x:xs) | n<=0 = []
              | otherwise = x : coge (n-1) XS

-- Ana Sosa Caballero
coge' :: Int -> [a] -> [a]
coge' n [] = []
coge' 0 xs = []
coge' n (x:xs) | n > 0 =  x : coge (n-1) xs
              | otherwise = []

-- ---------------------------------------------------------------------
-- Ejercicio 5.2. Comprobar con QuickCheck que coge es equivalente a
-- take. 
-- ---------------------------------------------------------------------
-- Lucía Hernández, Nicolás Rodríguez Ruiz, Elsa Domínguez, Adolfo Sagrera Vivancos, Ana Sánchez Martín, Ana Sosa Caballero
-- 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, Ana Sánchez Martín, Ana Sosa Caballero
sumaCuadradosR :: Integer -> Integer
sumaCuadradosR 0 = 0
sumaCuadradosR n = n^2 + sumaCuadradosR (n-1)
-- Elsa Domínguez, Adolfo Sagrera Vivancos
sumaCuadradosR :: Integer -> Integer
sumaCuadradosR 1 = 1
sumaCuadradosR n | n < 0      = error "n debe ser mayor que cero"
                 | otherwise  = 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, Elsa Domínguez, Adolfo Sagrera Vivancos, Ana Sánchez Martín, Ana Sosa Caballero
-- 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, Elsa Domínguez, Adolfo Sagrera Vivancos, Ana Sánchez Martín, Ana Sosa Caballero
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, Elsa Domínguez, Adolfo Sagrera Vivancos, Ana Sánchez Martín, Ana Sosa Caballero
-- 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, Elsa Domínguez, Adolfo Sagrera Vivancos, Ana Sánchez Martín
digitosR :: Integer -> [Integer]
digitosR n = if n<10 then [n]
          else   digitosR (div n 10) ++ [rem n 10]

-- Ana Sosa Caballero
digitosR' :: Integer -> [Integer]
digitosR' 0 = []
digitosR' n = 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, Elsa Domínguez, Adolfo Sagrera Vivancos, Ana Sánchez Martín, Ana Sosa Caballero
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, Elsa Domínguez, Adolfo Sagrera Vivancos, Ana Sánchez Martín, Ana Sosa Caballero
-- 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, Adolfo Sagrera Vivancos, Ana Sánchez Martín, Ana Sosa Caballero
sumaDigitosR :: Integer -> Integer
sumaDigitosR n = if n<10 then n
                else rem n 10 + sumaDigitosR (div n 10)
-- Elsa Domínguez
sumaDigitosR' :: Integer -> Integer
sumaDigitosR' 0 = 0 
sumaDigitosR' n | n < 0      = error "no es posible"
                | otherwise  = 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, Ana Sosa Caballero
sumaDigitosNR :: Integer -> Integer
sumaDigitosNR n = sum (digitosR n)
-- Elsa Domínguez, Adolfo Sagrera Vivancos, Ana Sánchez Martín
sumaDigitosNR :: Integer -> Integer
sumaDigitosNR n = sum (digitosC n)

-- ---------------------------------------------------------------------
-- Ejercicio 8.3. Comprobar con QuickCheck que las funciones sumaDigitosR
-- y sumaDigitosNR son equivalentes.
-- ---------------------------------------------------------------------
-- Lucía Hernández, Elsa Domínguez, Adolfo Sagrera Vivancos, Ana Sánchez Martín, Ana Sosa Caballero
-- 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, Ana Sánchez Martín, Ana Sosa Caballero
listaNumeroR :: [Integer] -> Integer
listaNumeroR [] = 0
listaNumeroR [x] = x
listaNumeroR (x:xs) = x*10^(length (xs)) + listaNumeroR xs
-- Elsa Domínguez, Adolfo Sagrera Vivancos
listaNumeroR' :: [Integer] -> Integer
listaNumeroR' [] = 0
listaNumeroR' [x] = x
listaNumeroR' xs = last xs + (listaNumeroR (init xs))*10

--José Manuel García
listaNumeroR :: [Integer] -> Integer
listaNumeroR (x:xs) = read ( (show x) ++ listaNumeroR' xs) :: Integer
listaNumeroR' :: [Integer] -> [Char]
listaNumeroR' [] = []
listaNumeroR' (x:xs) = show x ++ 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, Elsa Domínguez, Ana Sánchez Martín
listaNumeroC :: [Integer] -> Integer
listaNumeroC xs = sum [x*10^s | (x,s) <- zip(reverse xs) [0..length xs -1]]
-- Adolfo Sagrera Vivancos
listaNumeroC' :: [Integer] -> Integer
listaNumeroC' xs = sum [ x*(10^y)  | (x,y) <- agrupa1 xs]
agrupa1 xs = zip (reverse xs) [0..]

--José Manuel García
listaNumeroC :: [Integer] -> Integer
listaNumeroC xs = read [stringToChar t | t <- [show a | a <- xs]] :: Integer
stringToChar :: String -> Char
stringToChar x = head (x)

-- Ana Sosa Caballero
listaNumeroC'' :: [Integer] -> Integer
listaNumeroC'' [x] = x
listaNumeroC'' xs = sum [ x*10^(length xs) | x <- xs]
-- ---------------------------------------------------------------------
-- Ejercicio 9.3. Comprobar con QuickCheck que las funciones
-- listaNumeroR y listaNumeroC son equivalentes.
-- ---------------------------------------------------------------------
--Lucía Hernández, Elsa Domínguez, Ana Sánchez Martín, Ana Sosa Caballero
-- 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.
-- Adolfo Sagrera Vivancos
prop_listaNumero' xs = not(null xs) ==> listaNumeroR xs == listaNumeroC xs


-- ---------------------------------------------------------------------
-- 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, Elsa Domínguez, Adolfo Sagrera Vivancos, Ana Sánchez Martín, Ana Sosa Caballero
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, Adolfo Sagrera Vivancos, Ana Sánchez Martín
mayorExponenteC :: Integer -> Integer -> Integer
mayorExponenteC a b = last [s | s<- [0..b], mod b (a^s) == 0]
-- Elsa Domínguez 
mayorExponenteC' :: Integer -> Integer -> Integer
mayorExponenteC' a b | rem b a /= 0  = 0  -- mejora la eficiencia 
                     | otherwise     = last [x | x <- [0..32], rem b (a^x) == 0]