I1M2011: Ejercicios de definiciones por plegado
La clase de hoy de Informática de 1º del Grado en Matemáticas se han explicado las soluciones de los 3 primeros ejercicios de la es/0/0a/Rel_10.hs”>10ª relación que contiene ejercicios con definiciones mediante
plegado. En concreto, se estudian definiciones por plegado para
calcular
- el máximo elemento de una lista,
- el mínimo elemento de una lista y
- la inversa de una lista.
Los ejercicios, y sus soluciones, se muestran a continuación:
|
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 |
-- --------------------------------------------------------------------- -- Importación de librerías auxiliares -- -- --------------------------------------------------------------------- import Test.QuickCheck -- --------------------------------------------------------------------- -- Ejercicio 1.1. Definir, mediante recursión, la función -- maximumR :: Ord a => [a] -> a -- tal que (maximumR xs) es el máximo de la lista xs. Por ejemplo, -- maximumR [3,7,2,5] == 7 -- Nota: La función maximumR es equivalente a la predefinida maximum. -- --------------------------------------------------------------------- maximumR :: Ord a => [a] -> a maximumR [x] = x maximumR (x:y:ys) = max x (maximumR (y:ys)) -- --------------------------------------------------------------------- -- Ejercicio 1.2. La función de plegado foldr1 está definida por -- foldr1 :: (a -> a -> a) -> [a] -> a -- foldr1 _ [x] = x -- foldr1 f (x:xs) = f x (foldr1 f xs) -- -- Definir, mediante plegado con foldr1, la función -- maximumP :: Ord a => [a] -> a -- tal que (maximumR xs) es el máximo de la lista xs. Por ejemplo, -- maximumP [3,7,2,5] == 7 -- Nota: La función maximumP es equivalente a la predefinida maximum. -- --------------------------------------------------------------------- maximumP :: Ord a => [a] -> a maximumP = foldr1 max -- --------------------------------------------------------------------- -- Ejercicio 2. Definir, mediante plegado con foldr1, la función -- minimunP :: Ord a => [a] -> a -- tal que (minimunR xs) es el máximo de la lista xs. Por ejemplo, -- minimunP [3,7,2,5] == 7 -- Nota: La función minimunP es equivalente a la predefinida minimun. -- --------------------------------------------------------------------- minimumP :: Ord a => [a] -> a minimumP = foldr1 min -- --------------------------------------------------------------------- -- Ejercicio 3.1. Definir, mediante recursión, la función -- inversaR :: [a] -> [a] -- tal que (inversaR xs) es la inversa de la lista xs. Por ejemplo, -- inversaR [3,5,2,4,7] == [7,4,2,5,3] -- --------------------------------------------------------------------- inversaR :: [a] -> [a] inversaR [] = [] inversaR (x:xs) = (inversaR xs) ++ [x] -- --------------------------------------------------------------------- -- Ejercicio 3.2. Definir, mediante plegado, la función -- inversaP :: [a] -> [a] -- tal que (inversaP xs) es la inversa de la lista xs. Por ejemplo, -- inversaP [3,5,2,4,7] == [7,4,2,5,3] -- --------------------------------------------------------------------- inversaP :: [a] -> [a] inversaP = foldr f [] where f x y = y ++ [x] -- La definición anterior puede simplificarse a inversaP_2 :: [a] -> [a] inversaP_2 = foldr f [] where f x = (++ [x]) -- --------------------------------------------------------------------- -- Ejercicio 3.3. Definir, por recursión con acumulador, la función -- inversaR' :: [a] -> [a] -- tal que (inversaR' xs) es la inversa de la lista xs. Por ejemplo, -- inversaR' [3,5,2,4,7] == [7,4,2,5,3] -- --------------------------------------------------------------------- inversaR' :: [a] -> [a] inversaR' xs = inversaAux [] xs where inversaAux ys [] = ys inversaAux ys (x:xs) = inversaAux (x:ys) xs -- --------------------------------------------------------------------- -- Ejercicio 3.4. La función de plegado foldl está definida por -- foldl :: (a -> b -> a) -> a -> [b] -> a -- foldl f ys xs = aux ys xs -- where aux ys [] = ys -- aux ys (x:xs) = aux (f ys x) xs -- Definir, mediante plegado con foldl, la función -- inversaP' :: [a] -> [a] -- tal que (inversaP' xs) es la inversa de la lista xs. Por ejemplo, -- inversaP' [3,5,2,4,7] == [7,4,2,5,3] -- --------------------------------------------------------------------- inversaP' :: [a] -> [a] inversaP' = foldl f [] where f ys x = x:ys -- La definición anterior puede simplificarse lambda: inversaP'_2 :: [a] -> [a] inversaP'_2= foldl (\ys x -> x:ys) [] -- La definición puede simplificarse usando flip: inversaP'_3 :: [a] -> [a] inversaP'_3 = foldl (flip(:)) [] -- --------------------------------------------------------------------- -- Ejercicio 3.5. Comprobar con QuickCheck que las funciones reverse, -- inversaP e inversaP' son equivalentes. -- --------------------------------------------------------------------- -- La propiedad es prop_inversa :: Eq a => [a] -> Bool prop_inversa xs = inversaP xs == ys && inversaP' xs == ys where ys = reverse xs -- La comprobación es -- ghci> quickCheck prop_inversa -- +++ OK, passed 100 tests. -- --------------------------------------------------------------------- -- Ejercicio 3.6. Comparar la eficiencia de inversaP e inversaP' -- calculando el tiempo y el espacio que usado en evaluar las siguientes -- expresiones: -- head (inversaP [1..100000]) -- head (inversaP' [1..100000]) -- --------------------------------------------------------------------- -- La sesión es -- ghci> :set +s -- ghci> head (inversaP [1..100000]) -- 100000 -- (0.41 secs, 20882460 bytes) -- ghci> head (inversaP' [1..100000]) -- 1 -- (0.00 secs, 525148 bytes) -- ghci> :unset +s |