I1M2018: Ejercicios de funciones de orden superior
En la segunda parte de la clase de hoy de Informática de 1º del Grado en Matemáticas hemos comentado las soluciones de los primeros ejercicios de la relación 7 sobre funciones de orden superior.
Los ejercicios y su solución 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 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 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 |
-- --------------------------------------------------------------------- -- Introducción -- -- --------------------------------------------------------------------- -- Esta relación tiene contiene ejercicios con funciones de orden -- superior y definiciones por plegado correspondientes al tema 7 -- http://www.cs.us.es/~jalonso/cursos/i1m-18/temas/tema-7.html -- --------------------------------------------------------------------- -- Importación de librerías auxiliares -- -- --------------------------------------------------------------------- import Test.QuickCheck -- --------------------------------------------------------------------- -- Ejercicio 1. Definir la función -- segmentos :: (a -> Bool) -> [a] -> [a] -- tal que (segmentos p xs) es la lista de los segmentos de xs cuyos -- elementos verifican la propiedad p. Por ejemplo, -- segmentos even [1,2,0,4,9,6,4,5,7,2] == [[2,0,4],[6,4],[2]] -- segmentos odd [1,2,0,4,9,6,4,5,7,2] == [[1],[9],[5,7]] -- --------------------------------------------------------------------- segmentos :: (a -> Bool) -> [a] -> [[a]] segmentos _ [] = [] segmentos p (x:xs) | p x = takeWhile p (x:xs) : segmentos p (dropWhile p xs) | otherwise = segmentos p xs -- --------------------------------------------------------------------- -- Ejercicio 2.1. Definir, por comprensión, la función -- relacionadosC :: (a -> a -> Bool) -> [a] -> Bool -- tal que (relacionadosC r xs) se verifica si para todo par (x,y) de -- elementos consecutivos de xs se cumple la relación r. Por ejemplo, -- relacionadosC (<) [2,3,7,9] == True -- relacionadosC (<) [2,3,1,9] == False -- --------------------------------------------------------------------- relacionadosC :: (a -> a -> Bool) -> [a] -> Bool relacionadosC r xs = and [r x y | (x,y) <- zip xs (tail xs)] -- --------------------------------------------------------------------- -- Ejercicio 2.2. Definir, por recursión, la función -- relacionadosR :: (a -> a -> Bool) -> [a] -> Bool -- tal que (relacionadosR r xs) se verifica si para todo par (x,y) de -- elementos consecutivos de xs se cumple la relación r. Por ejemplo, -- relacionadosR (<) [2,3,7,9] == True -- relacionadosR (<) [2,3,1,9] == False -- --------------------------------------------------------------------- relacionadosR :: (a -> a -> Bool) -> [a] -> Bool relacionadosR r (x:y:zs) = r x y && relacionadosR r (y:zs) relacionadosR _ _ = True -- --------------------------------------------------------------------- -- Ejercicio 3.1. Definir la función -- agrupa :: Eq a => [[a]] -> [[a]] -- tal que (agrupa xss) es la lista de las listas obtenidas agrupando -- los primeros elementos, los segundos, ... Por ejemplo, -- agrupa [[1..6],[7..9],[10..20]] == [[1,7,10],[2,8,11],[3,9,12]] -- agrupa [] == [] -- --------------------------------------------------------------------- agrupa :: Eq a => [[a]] -> [[a]] agrupa [] = [] agrupa xss | [] `elem` xss = [] | otherwise = primeros xss : agrupa (restos xss) where primeros = map head restos = map tail -- --------------------------------------------------------------------- -- Ejercicio 3.2. Comprobar con QuickChek que la longitud de todos los -- elementos de (agrupa xs) es igual a la longitud de xs. -- --------------------------------------------------------------------- -- La propiedad es prop_agrupa :: [[Int]] -> Bool prop_agrupa xss = and [length xs == n | xs <- agrupa xss] where n = length xss -- La comprobación es -- ghci> quickCheck prop_agrupa -- +++ OK, passed 100 tests. comprueba_agrupa :: IO () comprueba_agrupa = quickCheck prop_agrupa -- --------------------------------------------------------------------- -- Ejercicio 4.1. Definir, por recursión, la función -- concatR :: [[a]] -> [a] -- tal que (concatR xss) es la concatenación de las listas de xss. Por -- ejemplo, -- concatR [[1,3],[2,4,6],[1,9]] == [1,3,2,4,6,1,9] -- --------------------------------------------------------------------- concatR :: [[a]] -> [a] concatR [] = [] concatR (xs:xss) = xs ++ concatR xss -- --------------------------------------------------------------------- -- Ejercicio 4.2. Definir, usando foldr, la función -- concatP :: [[a]] -> [a] -- tal que (concatP xss) es la concatenación de las listas de xss. Por -- ejemplo, -- concatP [[1,3],[2,4,6],[1,9]] == [1,3,2,4,6,1,9] -- --------------------------------------------------------------------- concatP :: [[a]] -> [a] concatP = foldr (++) [] -- --------------------------------------------------------------------- -- Ejercicio 4.3. Comprobar con QuickCheck que la funciones concatR, -- concatP y concat son equivalentes. -- --------------------------------------------------------------------- -- La propiedad es prop_concat :: [[Int]] -> Bool prop_concat xss = concatR xss == ys && concatP xss == ys where ys = concat xss -- La comprobación es -- ghci> quickCheck prop_concat -- +++ OK, passed 100 tests. -- --------------------------------------------------------------------- -- Ejercicio 4.4. Comprobar con QuickCheck que la longitud de -- (concatP xss) es la suma de las longitudes de los elementos de xss. -- --------------------------------------------------------------------- -- La propiedad es prop_longConcat :: [[Int]] -> Bool prop_longConcat xss = length (concatP xss) == sum [length xs | xs <- xss] -- La comprobación es -- ghci> quickCheck prop_longConcat -- +++ OK, passed 100 tests. -- --------------------------------------------------------------------- -- Ejercicio 5.1. Definir, por comprensión, la función -- filtraAplicaC :: (a -> b) -> (a -> Bool) -> [a] -> [b] -- tal que (filtraAplicaC f p xs) es la lista obtenida aplicándole a los -- elementos de xs que cumplen el predicado p la función f. Por ejemplo, -- filtraAplicaC (4+) (<3) [1..7] => [5,6] -- --------------------------------------------------------------------- filtraAplicaC :: (a -> b) -> (a -> Bool) -> [a] -> [b] filtraAplicaC f p xs = [f x | x <- xs, p x] -- --------------------------------------------------------------------- -- Ejercicio 5.2. Definir, usando map y filter, la función -- filtraAplicaMF :: (a -> b) -> (a -> Bool) -> [a] -> [b] -- tal que (filtraAplicaMF f p xs) es la lista obtenida aplicándole a los -- elementos de xs que cumplen el predicado p la función f. Por ejemplo, -- filtraAplicaMF (4+) (<3) [1..7] => [5,6] -- --------------------------------------------------------------------- filtraAplicaMF :: (a -> b) -> (a -> Bool) -> [a] -> [b] filtraAplicaMF f p xs = map f (filter p xs) -- --------------------------------------------------------------------- -- Ejercicio 5.3. Definir, por recursión, la función -- filtraAplicaR :: (a -> b) -> (a -> Bool) -> [a] -> [b] -- tal que (filtraAplicaR f p xs) es la lista obtenida aplicándole a los -- elementos de xs que cumplen el predicado p la función f. Por ejemplo, -- filtraAplicaR (4+) (<3) [1..7] => [5,6] -- --------------------------------------------------------------------- filtraAplicaR :: (a -> b) -> (a -> Bool) -> [a] -> [b] filtraAplicaR _ _ [] = [] filtraAplicaR f p (x:xs) | p x = f x : filtraAplicaR f p xs | otherwise = filtraAplicaR f p xs -- --------------------------------------------------------------------- -- Ejercicio 5.4. Definir, por plegado, la función -- filtraAplicaP :: (a -> b) -> (a -> Bool) -> [a] -> [b] -- tal que (filtraAplicaP f p xs) es la lista obtenida aplicándole a los -- elementos de xs que cumplen el predicado p la función f. Por ejemplo, -- filtraAplicaP (4+) (<3) [1..7] => [5,6] -- --------------------------------------------------------------------- filtraAplicaP :: (a -> b) -> (a -> Bool) -> [a] -> [b] filtraAplicaP f p = foldr g [] where g x y | p x = f x : y | otherwise = y -- La definición por plegado usando lambda es filtraAplicaP2 :: (a -> b) -> (a -> Bool) -> [a] -> [b] filtraAplicaP2 f p = foldr (\x y -> if p x then f x : y else y) [] -- --------------------------------------------------------------------- -- Ejercicio 6.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 -- maximumR ["todo","es","falso"] == "todo" -- maximumR ["menos","alguna","cosa"] == "menos" -- -- 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)) maximumR _ = error "Imposible" -- --------------------------------------------------------------------- -- Ejercicio 6.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 -- maximumP ["todo","es","falso"] == "todo" -- maximumP ["menos","alguna","cosa"] == "menos" -- -- Nota: La función maximumP es equivalente a la predefinida maximum. -- --------------------------------------------------------------------- maximumP :: Ord a => [a] -> a maximumP = foldr1 max |
Los soluciones de esta relación, junto con las anteriores se encuentra recopidado en el libro de soluciones de ejercicios.