I1M2015: Funciones de orden superior y definiciones por plegados
En la primera parte de la clase de hoy de Informática de 1º del Grado en Matemáticas hemos comentado las soluciones a los ejercicios de la relación 10 sobre Funciones de orden superior y definiciones por plegados.
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 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 |
-- --------------------------------------------------------------------- -- 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-15/temas/tema-7.html -- --------------------------------------------------------------------- -- Importación de librerías auxiliares -- -- --------------------------------------------------------------------- import Test.QuickCheck -- --------------------------------------------------------------------- -- Ejercicio 1.1. Definir, por recursión, la función -- takeWhileR :: (a -> Bool) -> [a] -> [a] -- tal que (takeWhileR p xs) es la lista de los elemento de xs hasta el -- primero que no cumple la propiedad p. Por ejemplo, -- takeWhileR (<7) [2,3,9,4,5] == [2,3] -- --------------------------------------------------------------------- takeWhileR :: (a -> Bool) -> [a] -> [a] takeWhileR _ [] = [] takeWhileR p (x:xs) | p x = x : takeWhileR p xs | otherwise = [] -- --------------------------------------------------------------------- -- Ejercicio 1.2. Comprobar con QuickCheck que, para cualquier lista de -- enteros xs, se verifica que (takeWhileR even xs) es igual que -- (takeWhile even xs) -- --------------------------------------------------------------------- -- La propiedad es prop_takeWhileR :: [Int] -> Bool prop_takeWhileR xs = takeWhileR even xs == takeWhile even xs -- La comprobación es -- ghci> quickCheck prop_takeWhile -- +++ OK, passed 100 tests. -- --------------------------------------------------------------------- -- Ejercicio 1.3. Comprobar con QuickCheck que, para cualquier lista de -- enteros xs, se verifica que todos los elementos de (takeWhileR even xs) -- son pares. -- --------------------------------------------------------------------- prop_takeWhileTodos :: [Int] -> Bool prop_takeWhileTodos xs = all even (takeWhileR even xs) -- --------------------------------------------------------------------- -- Ejercicio 2.1. Definir por recursión la función -- dropWhileR :: (a -> Bool) -> [a] -> [a] -- tal que (dropWhileR p xs) es la lista de eliminando los elemento de xs -- hasta el primero que cumple la propiedad p. Por ejemplo, -- dropWhileR (<7) [2,3,9,4,5] == [9,4,5] -- --------------------------------------------------------------------- dropWhileR :: (a -> Bool) -> [a] -> [a] dropWhileR _ [] = [] dropWhileR p (x:xs) | p x = dropWhileR p xs | otherwise = x:xs -- --------------------------------------------------------------------- -- Ejercicio 2.2. Comprobar con QuickCheck que, para cualquier lista de -- enteros xs, se verifica que la concatenación de (takeWhileR even xs) -- y (dropWhileR even xs) es igual a xs. -- --------------------------------------------------------------------- -- La propiedad es prop_takeDrop :: [Int] -> Bool prop_takeDrop xs = takeWhileR even xs ++ dropWhileR even xs == xs -- La comprobación es -- ghci> quickCheck prop_takeDrop -- +++ OK, passed 100 tests. -- --------------------------------------------------------------------- -- Ejercicio 3.1. Definir, por comprensión, la función -- divideMediaC :: [Double] -> ([Double],[Double]) -- tal que (divideMediaC xs) es el par (ys,zs), donde ys contiene los -- elementos de xs estrictamente menores que la media, mientras que zs -- contiene los elementos de xs estrictamente mayores que la media. Por -- ejemplo, -- divideMediaC [6,7,2,8,6,3,4] == ([2.0,3.0,4.0],[6.0,7.0,8.0,6.0]) -- divideMediaC [1,2,3] == ([1.0],[3.0]) -- --------------------------------------------------------------------- divideMediaC :: [Double] -> ([Double],[Double]) divideMediaC xs = ([x | x <- xs, x < m], [x | x <- xs, x > m]) where m = media xs -- (media xs) es la media de xs. Por ejemplo, -- media [1,2,3] == 2.0 -- media [1,-2,3.5,4] == 1.625 media :: [Double] -> Double media xs = (sum xs) / fromIntegral (length xs) -- --------------------------------------------------------------------- -- Ejercicio 3.2. Definir, con filter, la función -- divideMediaF :: [Double] -> ([Double],[Double]) -- tal que (divideMediaF xs) es el par (ys,zs), donde ys contiene los -- elementos de xs estrictamente menores que la media, mientras que zs -- contiene los elementos de xs estrictamente mayores que la media. Por -- ejemplo, -- divideMediaF [6,7,2,8,6,3,4] == ([2.0,3.0,4.0],[6.0,7.0,8.0,6.0]) -- divideMediaF [1,2,3] == ([1.0],[3.0]) -- --------------------------------------------------------------------- divideMediaF :: [Double] -> ([Double],[Double]) divideMediaF xs = (filter (<m) xs, filter (>m) xs) where m = media xs -- --------------------------------------------------------------------- -- Ejercicio 3.3. Definir, por recursión, la función -- divideMediaR :: [Double] -> ([Double],[Double]) -- tal que (divideMediaR xs) es el par (ys,zs), donde ys contiene los -- elementos de xs estrictamente menores que la media, mientras que zs -- contiene los elementos de xs estrictamente mayores que la media. Por -- ejemplo, -- divideMediaR [6,7,2,8,6,3,4] == ([2.0,3.0,4.0],[6.0,7.0,8.0,6.0]) -- divideMediaR [1,2,3] == ([1.0],[3.0]) -- --------------------------------------------------------------------- divideMediaR :: [Double] -> ([Double],[Double]) divideMediaR xs = divideMediaR' xs where m = media xs divideMediaR' [] = ([],[]) divideMediaR' (x:xs) | x < m = (x:ys, zs) | x == m = (ys, zs) | x > m = (ys, x:zs) where (ys, zs) = divideMediaR' xs -- --------------------------------------------------------------------- -- Ejercicio 3.4. Comprobar con QuickCheck que las tres definiciones -- anteriores divideMediaF, divideMediaC y divideMediaR son -- equivalentes. -- --------------------------------------------------------------------- -- La propiedad es prop_divideMedia :: [Double] -> Bool prop_divideMedia xs = divideMediaC xs == d && divideMediaR xs == d where d = divideMediaF xs -- La comprobación es -- ghci> quickCheck prop_divideMedia -- +++ OK, passed 100 tests. -- --------------------------------------------------------------------- -- Ejercicio 3.5. Comprobar con QuickCheck que si (ys,zs) es el par -- obtenido aplicándole la función divideMediaF a xs, entonces la suma -- de las longitudes de ys y zs es menor o igual que la longitud de xs. -- --------------------------------------------------------------------- -- La propiedad es prop_longitudDivideMedia :: [Double] -> Bool prop_longitudDivideMedia xs = length ys + length zs <= length xs where (ys,zs) = divideMediaF xs -- La comprobación es -- ghci> quickCheck prop_longitudDivideMedia -- +++ OK, passed 100 tests. -- --------------------------------------------------------------------- -- Ejercicio 3.6. Comprobar con QuickCheck que si (ys,zs) es el par -- obtenido aplicándole la función divideMediaF a xs, entonces todos los -- elementos de ys son menores que todos los elementos de zs. -- --------------------------------------------------------------------- -- La propiedad es prop_divideMediaMenores :: [Double] -> Bool prop_divideMediaMenores xs = and [y < z | y <- ys, z <- zs] where (ys,zs) = divideMediaF xs -- La comprobación es -- ghci> quickCheck prop_divideMediaMenores -- +++ OK, passed 100 tests. -- --------------------------------------------------------------------- -- Ejercicio 3.7. Comprobar con QuickCheck que si (ys,zs) es el par -- obtenido aplicándole la función divideMediaF a xs, entonces la -- media de xs no pertenece a ys ni a zs. -- -- Nota: Usar la función notElem tal que (notElem x ys) se verifica si y -- no pertenece a ys. -- --------------------------------------------------------------------- -- La propiedad es prop_divideMediaSinMedia :: [Double] -> Bool prop_divideMediaSinMedia xs = notElem m (ys ++ zs) where m = media xs (ys,zs) = divideMediaF xs -- La comprobación es -- ghci> quickCheck prop_divideMediaSinMedia -- +++ OK, passed 100 tests. -- --------------------------------------------------------------------- -- Ejercicio 4. 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 p [] = [] segmentos p (x:xs) | p x = takeWhile p (x:xs) : segmentos p (dropWhile p xs) | otherwise = segmentos p xs -- --------------------------------------------------------------------- -- Ejercicio 5.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 5.1. Definir, por comprensió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 6.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 6.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. -- --------------------------------------------------------------------- -- Ejercicio 7.1. Definir por recursión la función -- superparR :: Int -> Bool -- tal que (superparR n) se verifica si n es un número par tal que todos -- sus dígitos son pares. Por ejemplo, -- superparR 426 == True -- superparR 456 == False -- --------------------------------------------------------------------- superparR :: Int -> Bool superparR 0 = True superparR n = even n && superparR (div n 10) -- --------------------------------------------------------------------- -- Ejercicio 7.2. Definir por comprensión la función -- superparC :: Int -> Bool -- tal que (superparC n) se verifica si n es un número par tal que todos -- sus dígitos son pares. Por ejemplo, -- superparC 426 == True -- superparC 456 == False -- --------------------------------------------------------------------- superparC :: Int -> Bool superparC n = and [even d | d <- digitos n] digitos :: Int -> [Int] digitos n = [read [d] | d <- show n] -- --------------------------------------------------------------------- -- Ejercicio 7.3. Definir, por recursión sobre los dígitos, la función -- superparRD :: Int -> Bool -- tal que (superparRD n) se verifica si n es un número par tal que todos -- sus dígitos son pares. Por ejemplo, -- superparRD 426 == True -- superparRD 456 == False -- --------------------------------------------------------------------- superparRD :: Int -> Bool superparRD n = sonPares (digitos n) where sonPares [] = True sonPares (d:ds) = even d && sonPares ds -- --------------------------------------------------------------------- -- Ejercicio 7.4. Definir, usando all, la función -- superparA :: Int -> Bool -- tal que (superparA n) se verifica si n es un número par tal que todos -- sus dígitos son pares. Por ejemplo, -- superparA 426 == True -- superparA 456 == False -- --------------------------------------------------------------------- superparA :: Int -> Bool superparA n = all even (digitos n) -- --------------------------------------------------------------------- -- Ejercicio 7.5. Definir, usando filter, la función -- superparF :: Int -> Bool -- tal que (superparF n) se verifica si n es un número par tal que todos -- sus dígitos son pares. Por ejemplo, -- superparF 426 == True -- superparF 456 == False -- --------------------------------------------------------------------- superparF :: Int -> Bool superparF n = filter even (digitos n) == digitos n -- --------------------------------------------------------------------- -- Ejercicio 8.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 8.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 8.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 8.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 9.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 9.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 9.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 f p [] = [] filtraAplicaR f p (x:xs) | p x = f x : filtraAplicaR f p xs | otherwise = filtraAplicaR f p xs -- --------------------------------------------------------------------- -- Ejercicio 9.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 10.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)) -- --------------------------------------------------------------------- -- Ejercicio 10.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 -- --------------------------------------------------------------------- -- Ejercicio 10.3. Comprobar con QuickCheck que, para cualquier lista no -- vacía xs, (maximumP xs) es un elemento de xs que es mayor o igual que -- todos los elementos de xs. -- --------------------------------------------------------------------- -- La propiedad es prop_maximumP :: [Int] -> Property prop_maximumP xs = xs /= [] ==> m `elem` xs && all (<=m) xs where m = maximumP xs -- La comprobación es -- ghci> quickCheck prop_maximumP -- +++ OK, passed 100 tests. -- --------------------------------------------------------------------- -- Ejercicio 11.1. 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] == 2 -- minimumP ["todo","es","falso"] == "es" -- minimumP ["menos","alguna","cosa"] == "alguna" -- -- Nota: La función minimunP es equivalente a la predefinida minimun. -- --------------------------------------------------------------------- minimumP :: Ord a => [a] -> a minimumP = foldr1 min -- --------------------------------------------------------------------- -- Ejercicio 11.2. Comprobar con QuickCheck que, para cualquier lista no -- vacía xs, (minimumP xs) es un elemento de xs que es menor o igual que -- todos los elementos de xs. -- --------------------------------------------------------------------- -- La propiedad es prop_minimumP :: [Int] -> Property prop_minimumP xs = xs /= [] ==> m `elem` xs && all (>=m) xs where m = minimumP xs -- La comprobación es -- ghci> quickCheck prop_minimumP -- +++ OK, passed 100 tests. |
El código correspondiente se encuentra en GitHub.