I1M2012: Ejercicios de definiciones por recursión y comprensión en Haskell (4)
En la clase de hoy de Informática de 1º del Grado en Matemáticas hemos comentado las soluciones de los ejercicios 4 y 5 de la 10ª relación y 1 a 5 de la 11ª relación en las que 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.
Los ejercicios, y sus soluciones, se muestran a continuación: Los de la relación 10 son
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
-- --------------------------------------------------------------------- -- Importación de librerías auxiliares -- -- --------------------------------------------------------------------- import Test.QuickCheck -- --------------------------------------------------------------------- -- 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 -- --------------------------------------------------------------------- -- 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 |
y los de la relación 11 son
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 |
-- --------------------------------------------------------------------- -- Importación de librerías auxiliares -- -- --------------------------------------------------------------------- import Test.QuickCheck -- --------------------------------------------------------------------- -- Ejercicio 1.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 = [x `div` 2 | x <- xs, even x] -- --------------------------------------------------------------------- -- Ejercicio 1.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 = x `div` 2 : mitadParesRec xs | otherwise = mitadParesRec xs -- --------------------------------------------------------------------- -- Ejercicio 1.3. Comprobar con QuickCheck que ambas definiciones son -- equivalentes. -- --------------------------------------------------------------------- -- La propiedad es prop_mitadPares :: [Int] -> Bool prop_mitadPares xs = mitadPares xs == mitadParesRec xs -- La comprobación es -- ghci> quickCheck prop_mitadPares -- +++ OK, passed 100 tests. -- --------------------------------------------------------------------- -- Ejercicio 2.1. Definir, por comprensión, la función -- enRangoC :: Int -> Int -> [Int] -> [Int] -- tal que (enRangoC a b xs) es la lista de los elementos de xs mayores o -- iguales que a y menores o iguales que b. Por ejemplo, -- enRangoC 5 10 [1..15] == [5,6,7,8,9,10] -- enRangoC 5 10 [7,2,9,3] == [7,9] -- enRangoC 10 5 [1..15] == [] -- enRangoC 5 5 [1..15] == [5] -- --------------------------------------------------------------------- enRangoC :: Int -> Int -> [Int] -> [Int] enRangoC a b xs = [x | x <- xs, a <= x, x <= b] -- --------------------------------------------------------------------- -- Ejercicio 2.2. Definir, por recursión, la función -- enRangoR :: Int -> Int -> [Int] -> [Int] -- tal que (enRangoR a b []) es la lista de los elementos de xs -- mayores o iguales que a y menores o iguales que b. Por ejemplo, -- enRangoR 5 10 [1..15] == [5,6,7,8,9,10] -- enRangoR 5 10 [7,2,9,3] == [7,9] -- enRangoR 10 5 [1..15] == [] -- enRangoR 5 5 [1..15] == [5] -- --------------------------------------------------------------------- enRangoR :: Int -> Int -> [Int] -> [Int] enRangoR a b [] = [] enRangoR a b (x:xs) | a <= x && x <= b = x : enRangoR a b xs | otherwise = enRangoR a b xs -- --------------------------------------------------------------------- -- Ejercicio 2.3. Comprobar con QuickCheck que ambas definiciones son -- equivalentes. -- --------------------------------------------------------------------- -- La propiedad es prop_enRangoC :: Int -> Int -> [Int] -> Bool prop_enRangoC a b xs = enRangoC a b xs == enRangoR a b xs -- La comprobación es -- ghci> quickCheck prop_enRango -- +++ OK, passed 100 tests. -- --------------------------------------------------------------------- -- Ejercicio 3.1. Definir, por comprensión, la función -- sumaPositivosC :: [Int] -> Int -- tal que (sumaPositivosC xs) es la suma de los números positivos de -- xs. Por ejemplo, -- sumaPositivosC [0,1,-3,-2,8,-1,6] == 15 -- --------------------------------------------------------------------- sumaPositivosC :: [Int] -> Int sumaPositivosC xs = sum [x | x <- xs, x > 0] -- --------------------------------------------------------------------- -- Ejercicio 3.2. Definir, por recursión, la función -- sumaPositivosR :: [Int] -> Int -- tal que (sumaPositivosR xs) es la suma de los números positivos de -- xs. Por ejemplo, -- sumaPositivosR [0,1,-3,-2,8,-1,6] == 15 -- --------------------------------------------------------------------- sumaPositivosR :: [Int] -> Int sumaPositivosR [] = 0 sumaPositivosR (x:xs) | x > 0 = x + sumaPositivosR xs | otherwise = sumaPositivosR xs -- --------------------------------------------------------------------- -- Ejercicio 3.3. Comprobar con QuickCheck que ambas definiciones son -- equivalentes. -- --------------------------------------------------------------------- -- La propiedad es prop_sumaPositivosC :: [Int] -> Bool prop_sumaPositivosC xs = sumaPositivosC xs == sumaPositivosR xs -- La comprobación es -- ghci> quickCheck prop_sumaPositivos -- +++ OK, passed 100 tests. -- --------------------------------------------------------------------- -- Ejercicio 4.1. La suma de la serie -- 1/1^2 + 1/2^2 + 1/3^2 + 1/4^2 + ... -- es pi^2/6. Por tanto, pi se puede aproximar mediante la raíz cuadrada -- de 6 por la suma de la serie. -- -- Definir, por comprensión, la función aproximaPiC tal que -- (aproximaPiC n) es la aproximación de pi obtenida mediante n -- términos de la serie. Por ejemplo, -- aproximaPiC 4 == sqrt(6*(1/1^2 + 1/2^2 + 1/3^2 + 1/4^2)) -- == 2.9226129861250305 -- aproximaPiC 1000 == 3.1406380562059946 -- --------------------------------------------------------------------- aproximaPiC n = sqrt(6*sum [1/x^2 | x <- [1..n]]) -- --------------------------------------------------------------------- -- Ejercicio 4.2. Definir, por recursión, la función aproximaPiR tal -- que (aproximaPiR n) es la aproximación de pi obtenida mediante n -- términos de la serie. Por ejemplo, -- aproximaPiR 4 == sqrt(6*(1/1^2 + 1/2^2 + 1/3^2 + 1/4^2)) -- == 2.9226129861250305 -- aproximaPiR 1000 == 3.1406380562059946 -- --------------------------------------------------------------------- aproximaPiR n = sqrt(6*aproximaPiR' n) aproximaPiR' 1 = 1 aproximaPiR' n = 1/n^2 + aproximaPiR' (n-1) -- --------------------------------------------------------------------- -- Ejercicio 5.1. 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] -- --------------------------------------------------------------------- sustituyeImpar :: [Int] -> [Int] sustituyeImpar [] = [] sustituyeImpar (x:xs) | odd x = (x+1): sustituyeImpar xs | otherwise = x:sustituyeImpar xs -- --------------------------------------------------------------------- -- Ejercicio 5.2. 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 = and [even x | x <- sustituyeImpar xs] -- La comprobación es -- ghci> quickCheck prop_sustituyeImpar -- +++ OK, passed 100 tests. |