-- 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]
-- ---------------------------------------------------------------------
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]
-- ---------------------------------------------------------------------
cuadradosR :: [Integer] -> [Integer]
cuadradosR [] = []
cuadradosR (x:xs) = x^2:cuadradosR xs
-- Por funciones de orden superior:
cuadradosO :: [Integer] -> [Integer]
cuadradosO xs = map (^2) xs
-- Por plegado:
cuadradosF :: [Integer] -> [Integer]
cuadradosF xs = foldr f [] xs
where f x y = x^2:y
cuadradosF' :: [Integer] -> [Integer]
cuadradosF' xs = foldr (\ x y -> x^2:y) [] xs
prop_cuadrados :: [Integer] -> Bool
prop_cuadrados xs = cuadradosC xs == cuadradosR xs &&
cuadradosC xs == cuadradosO xs &&
cuadradosC xs == cuadradosF xs &&
cuadradosC xs == cuadradosF' 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]
-- ---------------------------------------------------------------------
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]
-- ---------------------------------------------------------------------
imparesR :: [Integer] -> [Integer]
imparesR [] = []
imparesR (x:xs) | odd x = x:imparesR xs
| otherwise = imparesR xs
-- Por funciones de orden superior:
imparesO :: [Integer] -> [Integer]
imparesO xs = filter odd xs
-- Por plegado:
imparesF :: [Integer] -> [Integer]
imparesF xs = foldr (\ x y -> if odd x then x:y else y) [] xs
prop_impares :: [Integer] -> Bool
prop_impares xs = imparesC xs == imparesR xs &&
imparesC xs == imparesO xs &&
imparesC xs == imparesF 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]
-- ---------------------------------------------------------------------
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]
-- ---------------------------------------------------------------------
imparesCuadradosR :: [Integer] -> [Integer]
imparesCuadradosR [] = []
imparesCuadradosR (x:xs) | odd x = x^2:imparesCuadradosR xs
| otherwise = imparesCuadradosR xs
-- Por funciones de orden superior:
imparesCuadradosO :: [Integer] -> [Integer]
imparesCuadradosO xs = map (^2) (filter odd xs)
-- Por plegado:
imparesCuadradosF :: [Integer] -> [Integer]
imparesCuadradosF xs = foldr (\ x y -> if odd x then x^2:y else y) [] xs
prop_impares_cuadrados :: [Integer] -> Bool
prop_impares_cuadrados xs = imparesCuadradosC xs == imparesCuadradosR xs &&
imparesCuadradosC xs == imparesCuadradosO xs &&
imparesCuadradosC xs == imparesCuadradosF 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
-- ---------------------------------------------------------------------
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
-- ---------------------------------------------------------------------
sumaCuadradosImparesR :: [Integer] -> Integer
sumaCuadradosImparesR [] = 0
sumaCuadradosImparesR (x:xs) | odd x = x^2 + sumaCuadradosImparesR xs
| otherwise = sumaCuadradosImparesR xs
-- Por plegado:
sumaCuadradosImparesF :: [Integer] -> Integer
sumaCuadradosImparesF xs = foldr (\ x y -> (if odd x then x^2 else 0) + y ) 0 xs
prop_suma_cuadrados :: [Integer] -> Bool
prop_suma_cuadrados xs = sumaCuadradosImparesC xs == sumaCuadradosImparesR xs &&
sumaCuadradosImparesC xs == sumaCuadradosImparesF 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]
-- ---------------------------------------------------------------------
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]
-- ---------------------------------------------------------------------
entreR :: Integer -> Integer -> [Integer]
entreR m n | m > n = []
| otherwise = m:entreR (m+1) n
-- ---------------------------------------------------------------------
-- 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]
-- ---------------------------------------------------------------------
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]
-- ---------------------------------------------------------------------
mitadParesRec :: [Int] -> [Int]
mitadParesRec [] = []
mitadParesRec (x:xs) | even x = (div x 2):mitadParesRec xs
| otherwise = mitadParesRec xs
-- Por funciones de orden superior:
mitadParesO :: [Int] -> [Int]
mitadParesO xs = map (`div`2) (filter even xs)
-- Por plegado:
mitadParesF :: [Int] -> [Int]
mitadParesF xs = foldr (\ x y -> if even x then (div x 2):y else y) [] xs
-- ---------------------------------------------------------------------
-- Ejercicio 6.3. Comprobar con QuickCheck que ambas definiciones son
-- equivalentes.
-- ---------------------------------------------------------------------
-- La propiedad es
prop_mitadPares :: [Int] -> Bool
prop_mitadPares xs = mitadPares xs == mitadParesRec xs &&
mitadPares xs == mitadParesO xs &&
mitadPares xs == mitadParesF xs
-- ---------------------------------------------------------------------
-- 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]
-- ---------------------------------------------------------------------
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]
-- ---------------------------------------------------------------------
enRangoRec :: Int -> Int -> [Int] -> [Int]
enRangoRec a b [] = []
enRangoRec a b (x:xs) | x < a = enRangoRec a b xs
| x > b = enRangoRec a b xs
| otherwise = x:enRangoRec a b xs
-- Por funciones de orden superior:
enRangoO :: Int -> Int -> [Int] -> [Int]
enRangoO a b xs = filter (>=a) (filter (<=b) xs)
-- Por plegado:
enRangoF :: Int -> Int -> [Int] -> [Int]
enRangoF a b xs = foldr (\ x y -> if x >=a && x <= b then x:y else y) [] xs
-- ---------------------------------------------------------------------
-- Ejercicio 7.3. Comprobar con QuickCheck que ambas definiciones son
-- equivalentes.
-- ---------------------------------------------------------------------
-- La propiedad es
prop_enRango :: Int -> Int -> [Int] -> Bool
prop_enRango a b xs = enRango a b xs == enRangoRec a b xs &&
enRango a b xs == enRangoO a b xs &&
enRango a b xs == enRangoF a b xs
-- ---------------------------------------------------------------------
-- 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
-- ---------------------------------------------------------------------
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
-- ---------------------------------------------------------------------
sumaPositivosRec :: [Int] -> Int
sumaPositivosRec [] = 0
sumaPositivosRec (x:xs) | x > 0 = x + sumaPositivosRec xs
| otherwise = sumaPositivosRec xs
-- Por funciones de orden superior:
sumaPositivosO :: [Int] -> Int
sumaPositivosO xs = sum (filter (>0) xs)
-- Por plegado:
sumaPositivosF :: [Int] -> Int
sumaPositivosF xs = foldr (\ x y -> (if x > 0 then x else 0) + y) 0 xs
-- ---------------------------------------------------------------------
-- Ejercicio 8.3. Comprobar con QuickCheck que ambas definiciones son
-- equivalentes.
-- ---------------------------------------------------------------------
-- La propiedad es
prop_sumaPositivos :: [Int] -> Bool
prop_sumaPositivos xs = sumaPositivos xs == sumaPositivosRec xs &&
sumaPositivos xs == sumaPositivosO xs &&
sumaPositivos xs == sumaPositivosF xs
-- ---------------------------------------------------------------------
-- 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
-- ---------------------------------------------------------------------
dobleFactorial :: Integer -> Integer
dobleFactorial 0 = 1
dobleFactorial 1 = 1
dobleFactorial n = n * dobleFactorial (n - 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] == []
-- ---------------------------------------------------------------------
sumaConsecutivosC :: [Int] -> [Int]
sumaConsecutivosC xs = [x + y | (x,y) <- zip xs (tail xs)]
sumaConsecutivosR :: [Int] -> [Int]
sumaConsecutivosR [] = []
sumaConsecutivosR (x:[]) = []
sumaConsecutivosR (x:y:xs) = (x+y):sumaConsecutivosR (y:xs)
-- Por funciones de orden superior:
sumaConsecutivosO :: [Int] -> [Int]
sumaConsecutivosO xs = map (\ (x,y) -> x + y) (zip xs (tail xs))
-- Por plegado:
sumaConsecutivosF :: [Int] -> [Int]
sumaConsecutivosF xs = foldr (\ (x,y) z -> (x+y):z) [] (zip xs (tail xs))
prop_suma_consecutivos :: [Int] -> Bool
prop_suma_consecutivos xs = sumaConsecutivosC xs == sumaConsecutivosR xs &&
sumaConsecutivosC xs == sumaConsecutivosO xs &&
sumaConsecutivosC xs == sumaConsecutivosF 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
-- ---------------------------------------------------------------------
-- Por comprensión:
distancia :: Eq a => [a] -> [a] -> Int
distancia xs ys = sum [1 | (x,y) <- zip xs ys, x /= y]
-- Por recursión:
distancia' :: Eq a => [a] -> [a] -> Int
distancia' [] [] = 0
distancia' [] _ = 0
distancia' _ [] = 0
distancia' (x:xs) (y:ys) | x /= y = 1 + distancia' xs ys
| otherwise = distancia' xs ys
-- Por funciones de orden superior:
distanciaO :: Eq a => [a] -> [a] -> Int
distanciaO xs ys = length (filter (\ (x,y) -> x /= y) (zip xs ys))
-- Por plegado:
distanciaF :: Eq a => [a] -> [a] -> Int
distanciaF xs ys = foldr (\ (x,y) z -> (if x /= y then 1 else 0) + z) 0 (zip xs ys)
prop_distancia :: Eq a => [a] -> [a] -> Bool
prop_distancia xs ys = distancia xs ys == distancia' xs ys &&
distancia xs ys == distanciaO xs ys &&
distancia xs ys == distanciaF 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]
-- ---------------------------------------------------------------------
sustituyeImparC :: [Int] -> [Int]
sustituyeImparC xs = [if even x then x else x + 1 | x <- xs]
sustituyeImparR :: [Int] -> [Int]
sustituyeImparR [] = []
sustituyeImparR (x:xs) | even x = x:sustituyeImparR xs
| otherwise = (x+1):sustituyeImparR xs
sustituyeImparO :: [Int] -> [Int]
sustituyeImparO xs = map (\ x -> if even x then x else x+1) xs
sustituyeImparF :: [Int] -> [Int]
sustituyeImparF xs = foldr (\ x y -> (if even x then x else x+1):y) [] 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.
-- ---------------------------------------------------------------------
-- La propiedad es
prop_sustituyeImpar :: [Int] -> Bool
prop_sustituyeImpar xs = all even (sustituyeImparC xs)
prop_sustituyeImpar' xs = sustituyeImparC xs == sustituyeImparR xs &&
sustituyeImparC xs == sustituyeImparO xs &&
sustituyeImparC xs == sustituyeImparF xs
![Informática de 1º de Matemáticas [Curso 2021-22, Grupo 3]](/WIKIS/I1M2021G3/resources/assets/logoUS.png)