Relación 4 extra 1

-- Definiciones por recursión y por comprensión. Temas 5 y 6.
-- Departamento de Ciencias de la Computación e I.A.
-- Universidad de Sevilla
-- =====================================================================

-- ---------------------------------------------------------------------
-- Introducció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. 

-- ---------------------------------------------------------------------
-- Importación de librerías auxiliares                                --
-- ---------------------------------------------------------------------

import Test.QuickCheck

-- ---------------------------------------------------------------------
-- Ejercicio 1.1. Definir, por comprensión, la función
--    cuadradosC :: [Integer] -> [Integer]
-- tal que (cuadradosC xs) es la lista de los cuadrados de xs. Por
-- ejemplo, 
--    cuadradosC [1,2,3]  ==  [1,4,9]
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
cuadradosC :: [Integer] -> [Integer]
cuadradosC xs = [x^2 | x <- xs]

-- ---------------------------------------------------------------------
-- Ejercicio 1.2. Definir, por recursión, la función
--    cuadradosR :: [Integer] -> [Integer]
-- tal que (cuadradosR xs) es la lista de los cuadrados de xs. Por
-- ejemplo, 
--    cuadradosR [1,2,3]  ==  [1,4,9]
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
cuadradosR :: [Integer] -> [Integer]
cuadradosR [] = []
cuadradosR (x:xs) = [x^2] ++ cuadradosR xs 

-- ---------------------------------------------------------------------
-- Ejercicio 2.1. Definir, por comprensión, la función
--    imparesC :: [Integer] -> [Integer]
-- tal que (imparesC xs) es la lista de los números impares de xs. Por
-- ejemplo, 
--    imparesC [1,2,3]  ==  [1,3]
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
imparesC :: [Integer] -> [Integer]
imparesC xs = [x | x <- xs, odd x]

-- ---------------------------------------------------------------------
-- Ejercicio 2.2. Definir, por recursión, la función
--    imparesR :: [Integer] -> [Integer]
-- tal que (imparesR xs) es la lista de los números impares de xs. Por
-- ejemplo, 
--    imparesR [1,2,3]  ==  [1,3]
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
imparesR :: [Integer] -> [Integer]
imparesR [] = []
imparesR (x:xs) = if odd x then [x] ++ imparesR xs else imparesR xs

-- ---------------------------------------------------------------------
-- Ejercicio 3.1. Definir, por comprensión, la función
--    imparesCuadradosC :: [Integer] -> [Integer]
-- tal que (imparesCuadradosC xs) es la lista de los cuadrados de los
-- números impares de xs. Por ejemplo, 
--    imparesCuadradosC [1,2,3]  ==  [1,9]
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
imparesCuadradosC :: [Integer] -> [Integer]
imparesCuadradosC xs = [x^2 | x <- xs, odd x]

-- ---------------------------------------------------------------------
-- Ejercicio 3.2. Definir, por recursión, la función
--    imparesCuadradosR :: [Integer] -> [Integer]
-- tal que (imparesCuadradosR xs) es la lista de los cuadrados de los
-- números impares de xs. Por ejemplo, 
--    imparesCuadradosR [1,2,3]  ==  [1,9]
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
imparesCuadradosR :: [Integer] -> [Integer]
imparesCuadradosR [] = []
imparesCuadradosR (x:xs) = if odd x then [x^2] ++ imparesCuadradosR xs else imparesCuadradosR xs

-- ---------------------------------------------------------------------
-- Ejercicio 4.1. Definir, por comprensión, la función
--    sumaCuadradosImparesC :: [Integer] -> Integer
-- tal que (sumaCuadradosImparesC xs) es la suma de los cuadrados de los
-- números impares de la lista xs. Por ejemplo,
--    sumaCuadradosImparesC [1,2,3]  ==  10
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
sumaCuadradosImparesC :: [Integer] -> Integer
sumaCuadradosImparesC xs = sum [x^2 | x <- xs, odd x]

-- ---------------------------------------------------------------------
-- Ejercicio 4.2. Definir, por recursión, la función
--    sumaCuadradosImparesR :: [Integer] -> Integer
-- tal que (sumaCuadradosImparesR xs) es la suma de los cuadrados de los
-- números impares de la lista xs. Por ejemplo,
--    sumaCuadradosImparesR [1,2,3]  ==  10
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
sumaCuadradosImparesR :: [Integer] -> Integer
sumaCuadradosImparesR [] = 0
sumaCuadradosImparesR (x:xs) = if odd x then (x^2) + sumaCuadradosImparesR xs else sumaCuadradosImparesR xs

-- ---------------------------------------------------------------------
-- Ejercicio 5.1. Definir, usando funciones predefinidas, la función
--    entreL :: Integer -> Integer -> [Integer]
-- tal que (entreL m n) es la lista de los números entre m y n. Por
-- ejemplo, 
--    entreL 2 5  ==  [2,3,4,5]
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
entreL :: Integer -> Integer -> [Integer]
entreL m n = [m..n]

-- ---------------------------------------------------------------------
-- Ejercicio 5.2. Definir, por recursión, la función
--    entreR :: Integer -> Integer -> [Integer]
-- tal que (entreR m n) es la lista de los números entre m y n. Por
-- ejemplo, 
--    entreR 2 5  ==  [2,3,4,5]
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
entreR :: Integer -> Integer -> [Integer]
entreR m n = if m<=n then [m] ++ entreR (m+1) n else []

-- ---------------------------------------------------------------------
-- Ejercicio 6.1. Definir, por comprensión, la función
--    mitadPares :: [Int] -> [Int]
-- tal que (mitadPares xs) es la lista de las mitades de los elementos
-- de xs que son pares. Por ejemplo,
--    mitadPares [0,2,1,7,8,56,17,18]  ==  [0,1,4,28,9]
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
mitadPares :: [Int] -> [Int]
mitadPares xs = [div x 2 | x <- xs, even x]

-- ---------------------------------------------------------------------
-- Ejercicio 6.2. Definir, por recursión, la función
--    mitadParesRec :: [Int] -> [Int]
-- tal que (mitadParesRec []) es la lista de las mitades de los elementos
-- de xs que son pares. Por ejemplo,
--    mitadParesRec [0,2,1,7,8,56,17,18]  ==  [0,1,4,28,9]
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
mitadParesRec :: [Int] -> [Int]
mitadParesRec [] = []
mitadParesRec (x:xs) = if even x then [(div x 2)] ++ mitadParesRec xs else mitadParesRec xs

-- ---------------------------------------------------------------------
-- Ejercicio 6.3. Comprobar con QuickCheck que ambas definiciones son
-- equivalentes. 
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
-- La propiedad es
prop_mitadPares :: [Int] -> Bool
prop_mitadPares xs = mitadPares xs == mitadParesRec xs 

-- La comprobación es

-- *Main> quickCheck prop_mitadPares
-- +++ OK, passed 100 tests.

-- ---------------------------------------------------------------------
-- Ejercicio 7.1. Definir, por comprensión, la función
--    enRango :: Int -> Int -> [Int] -> [Int]
-- tal que (enRango a b xs) es la lista de los elementos de xs mayores o
-- iguales que a y menores o iguales que b. Por ejemplo,
--    enRango  5 10 [1..15]   ==  [5,6,7,8,9,10]
--    enRango 10  5 [1..15]   ==  []
--    enRango  5  5 [1..15]   ==  [5]
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
enRango :: Int -> Int -> [Int] -> [Int]
enRango a b xs = [x | x <- xs, x >= a && x<= b]

-- ---------------------------------------------------------------------
-- Ejercicio 7.2. Definir, por recursión, la función
--    enRangoRec :: Int -> Int -> [Int] -> [Int]
-- tal que (enRangoRec a b []) es la lista de los elementos de xs
-- mayores o iguales que a y menores o iguales que b. Por ejemplo,
--    enRangoRec  5 10 [1..15]  ==  [5,6,7,8,9,10]
--    enRangoRec 10 5 [1..15]   ==  []
--    enRangoRec  5 5 [1..15]   ==  [5]
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
enRangoRec :: Int -> Int -> [Int] -> [Int]
enRangoRec _ _ [] = []
enRangoRec a b (x:xs) = if x >= a && x<= b then [x] ++ enRango a b xs else enRango a b xs

-- ---------------------------------------------------------------------
-- Ejercicio 7.3. Comprobar con QuickCheck que ambas definiciones son
-- equivalentes. 
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
-- La propiedad es
prop_enRango :: Int -> Int -> [Int] -> Bool
prop_enRango a b xs = enRango a b xs == enRangoRec a b xs 

-- La comprobación es

-- *Main> quickCheck prop_enRango
-- +++ OK, passed 100 tests.

-- ---------------------------------------------------------------------
-- Ejercicio 8.1. Definir, por comprensión, la función
--    sumaPositivos :: [Int] -> Int
-- tal que (sumaPositivos xs) es la suma de los números positivos de
-- xs. Por ejemplo, 
--    sumaPositivos [0,1,-3,-2,8,-1,6]  ==  15
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
sumaPositivos :: [Int] -> Int
sumaPositivos xs = sum [x | x <- xs, x>0 ]

-- ---------------------------------------------------------------------
-- Ejercicio 8.2. Definir, por recursión, la función
--    sumaPositivosRec :: [Int] -> Int
-- tal que (sumaPositivosRec xs) es la suma de los números positivos de
-- xs. Por ejemplo, 
--    sumaPositivosRec [0,1,-3,-2,8,-1,6]  ==  15
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
sumaPositivosRec :: [Int] -> Int
sumaPositivosRec [] = 0
sumaPositivosRec (x:xs) = if x > 0 then x + sumaPositivosRec xs else sumaPositivosRec xs 

-- ---------------------------------------------------------------------
-- Ejercicio 8.3. Comprobar con QuickCheck que ambas definiciones son
-- equivalentes. 
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
-- La propiedad es
prop_sumaPositivos :: [Int] -> Bool
prop_sumaPositivos xs = sumaPositivos xs == sumaPositivosRec xs 

-- La comprobación es

-- *Main> quickCheck prop_sumaPositivos 
-- +++ OK, passed 100 tests.

-- ---------------------------------------------------------------------
-- Ejercicio 9. El doble factorial de un número n se define por 
--    n!! = n*(n-2)* ... * 3 * 1, si n es impar
--    n!! = n*(n-2)* ... * 4 * 2, si n es par
--    1!! = 1
--    0!! = 1    
-- Por ejemplo,
--    8!! = 8*6*4*2   = 384
--    9!! = 9*7*5*3*1 = 945
-- Definir, por recursión, la función
--    dobleFactorial :: Integer -> Integer
-- tal que (dobleFactorial n) es el doble factorial de n. Por ejemplo,
--    dobleFactorial 8  ==  384
--    dobleFactorial 9  ==  945
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
dobleFactorial :: Integer -> Integer
dobleFactorial 0 = 1
dobleFactorial 1 = 1
dobleFactorial x = x * dobleFactorial (x-2)

-- ---------------------------------------------------------------------
-- Ejercicio 10. Definir, por recursión y 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]        ==  []
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
sumaConsecutivosR :: [Int] -> [Int]
sumaConsecutivosR [] = []
sumaConsecutivosR [_] = []
sumaConsecutivosR (x:xs) = [x + (head xs)] ++ sumaConsecutivosR xs 

sumaConsecutivosC :: [Int] -> [Int]
sumaConsecutivosC xs = [x+y | (x,y) <- zip xs (tail xs)]

-- ---------------------------------------------------------------------
-- Ejercicio 11. La distancia de Hamming entre dos listas es el
-- número de posiciones en que los correspondientes elementos son
-- distintos. Por ejemplo, la distancia de Hamming entre "roma" y "loba"
-- es 2 (porque hay 2 posiciones en las que los elementos
-- correspondientes son distintos: la 1ª y la 3ª).
--    
-- Definir la función
--    distancia :: Eq a => [a] -> [a] -> Int
-- tal que (distancia xs ys) es la distancia de Hamming entre xs e
-- ys. Por ejemplo,
--    distancia "romano" "comino"  ==  2
--    distancia "romano" "camino"  ==  3
--    distancia "roma"   "comino"  ==  2
--    distancia "roma"   "camino"  ==  3
--    distancia "romano" "ron"     ==  1
--    distancia "romano" "cama"    ==  2
--    distancia "romano" "rama"    ==  1
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
-- Por comprensión:
distancia :: Eq a => [a] -> [a] -> Int
distancia xs ys = sum [1 | (a,b) <- zip xs ys, a /= b]

-- Por recursión:
distancia' :: Eq a => [a] -> [a] -> Int
distancia' [] _ = 0
distancia' _ [] = 0 
distancia' (x:xs) (y:ys) = if x/=y then 1 + distancia' xs ys else distancia' xs ys 

-- ---------------------------------------------------------------------
-- Ejercicio 12. Definir por recursión la función 
--    sustituyeImpar :: [Int] -> [Int]
-- tal que (sustituyeImpar xs) es la lista obtenida sustituyendo cada
-- número impar de xs por el siguiente número par. Por ejemplo,
--    sustituyeImpar [2,5,7,4]  ==  [2,6,8,4]
-- --------------------------------------------------------------------- 

-- Álvaro Galisteo:
sustituyeImpar :: [Int] -> [Int]
sustituyeImpar [] = []
sustituyeImpar (x:xs) = if odd x then [x+1] ++ sustituyeImpar xs else [x] ++ sustituyeImpar xs

-- ---------------------------------------------------------------------
-- Ejercicio 13. Comprobar con QuickChek la siguiente propiedad: para
-- cualquier lista de números enteros xs, todos los elementos de la
-- lista (sustituyeImpar xs) son números pares. 
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
-- La propiedad es
prop_sustituyeImpar :: [Int] -> Bool
prop_sustituyeImpar xs = all even (sustituyeImpar xs)

-- La comprobación es

-- *Main> quickCheck prop_sustituyeImpar 
-- +++ OK, passed 100 tests.