I1M2012: Funciones de orden superior (3)
En la clase de hoy de Informática de 1º del Grado en Matemáticas hemos continuado comentando las soluciones de los ejercicios de las relaciones 14 y 15 (de funciones de orden superior).
Los ejercicios, y sus soluciones, se muestran a continuación. Los de la relación 14:
|
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 |
-- --------------------------------------------------------------------- -- Importación de librerías auxiliares -- -- --------------------------------------------------------------------- import Test.QuickCheck -- --------------------------------------------------------------------- -- Ejercicio 8.1. Definir por recursión la función -- superpar :: Int -> Bool -- tal que (superpar n) se verifica si n es un número par tal que todos -- sus dígitos son pares. Por ejemplo, -- superpar 426 == True -- superpar 456 == False -- --------------------------------------------------------------------- superpar :: Int -> Bool superpar n | n < 10 = even n | otherwise = even n && superpar (n `div` 10) -- Otra forma equivalente es superpar' :: Int -> Bool superpar' 0 = True superpar' n = even n && superpar' (div n 10) -- --------------------------------------------------------------------- -- Ejercicio 8.2. Definir por comprensión la función -- superpar2 :: Int -> Bool -- tal que (superpar2 n) se verifica si n es un número par tal que todos -- sus dígitos son pares. Por ejemplo, -- superpar2 426 == True -- superpar2 456 == False -- --------------------------------------------------------------------- superpar2 :: Int -> Bool superpar2 n = and [even d | d <- digitos n] digitos :: Int -> [Int] digitos n = [read [d] | d <- show n] -- --------------------------------------------------------------------- -- Ejercicio 8.3. Definir, por recursión sobre los dígitos, la función -- superpar3 :: Int -> Bool -- tal que (superpar3 n) se verifica si n es un número par tal que todos -- sus dígitos son pares. Por ejemplo, -- superpar3 426 == True -- superpar3 456 == False -- --------------------------------------------------------------------- superpar3 :: Int -> Bool superpar3 n = sonPares (digitos n) where sonPares [] = True sonPares (d:ds) = even d && sonPares ds -- --------------------------------------------------------------------- -- Ejercicio 8.3. Definir, usando all, la función -- superpar4 :: Int -> Bool -- tal que (superpar4 n) se verifica si n es un número par tal que todos -- sus dígitos son pares. Por ejemplo, -- superpar4 426 == True -- superpar4 456 == False -- --------------------------------------------------------------------- superpar4 :: Int -> Bool superpar4 n = all even (digitos n) -- --------------------------------------------------------------------- -- Ejercicio 8.5. Definir, usando filter, la función -- superpar5 :: Int -> Bool -- tal que (superpar5 n) se verifica si n es un número par tal que todos -- sus dígitos son pares. Por ejemplo, -- superpar5 426 == True -- superpar5 456 == False -- --------------------------------------------------------------------- superpar5 :: Int -> Bool superpar5 n = filter even (digitos n) == digitos n -- --------------------------------------------------------------------- -- Ejercicio 9. Se considera la función -- filtraAplica :: (a -> b) -> (a -> Bool) -> [a] -> [b] -- tal que (filtraAplica 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, -- filtraAplica (4+) (<3) [1..7] => [5,6] -- Se pide, definir la función -- 1. por comprensión, -- 2. usando map y filter, -- 3. por recursión y -- 4. por plegado (con foldr). -- --------------------------------------------------------------------- -- La definición con lista de comprensión es filtraAplica_1 :: (a -> b) -> (a -> Bool) -> [a] -> [b] filtraAplica_1 f p xs = [f x | x <- xs, p x] -- La definición con map y filter es filtraAplica_2 :: (a -> b) -> (a -> Bool) -> [a] -> [b] filtraAplica_2 f p xs = map f (filter p xs) -- La definición por recursión es filtraAplica_3 :: (a -> b) -> (a -> Bool) -> [a] -> [b] filtraAplica_3 f p [] = [] filtraAplica_3 f p (x:xs) | p x = f x : filtraAplica_3 f p xs | otherwise = filtraAplica_3 f p xs -- La definición por plegado es filtraAplica_4 :: (a -> b) -> (a -> Bool) -> [a] -> [b] filtraAplica_4 f p = foldr g [] where g x y | p x = f x : y | otherwise = y -- La definición por plegado usando lambda es filtraAplica_4' :: (a -> b) -> (a -> Bool) -> [a] -> [b] filtraAplica_4' 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 -- 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 -- Nota: La función maximumP es equivalente a la predefinida maximum. -- --------------------------------------------------------------------- maximumP :: Ord a => [a] -> a maximumP = foldr1 max -- --------------------------------------------------------------------- -- Ejercicio 11. 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 -- Nota: La función minimunP es equivalente a la predefinida minimun. -- --------------------------------------------------------------------- minimumP :: Ord a => [a] -> a minimumP = foldr1 min |
Los de la relación 15
|
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 |
-- --------------------------------------------------------------------- -- Importación de librerías auxiliares -- -- --------------------------------------------------------------------- import Data.List import Test.QuickCheck -- --------------------------------------------------------------------- -- Ejercicio 1.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 1.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 inversaP2 :: [a] -> [a] inversaP2 = foldr f [] where f x = (++ [x]) -- --------------------------------------------------------------------- -- Ejercicio 1.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 1.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 1.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 1.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 |