I1M2011: Ejercicios sobre funciones de orden superior y plegados
La clase de hoy de Informática de 1º del Grado en Matemáticas hemos comentando las soluciones de ejercicios de la 3ª y 4ª parte de la 9ª relación y los 2 primeros de la 10ª relación
La 3ª parte contiene ejercicios sobre funciones de orden superior. En concreto, se estudian funciones para calcular
- el segmento inicial cuyos elementos verifican una propiedad y
- el complementario del segmento inicial cuyos elementos verifican una propiedad.
La 4ª parte contiene ejercicios sobre definiciones mediante map, filter y plegado. En concreto, se estudian funciones para calcular
- la lista de los valores de los elementos que cumplen una propiedad,
- la concatenación de una lista de listas,
- la redefinición de la función map y
- la redefinición de la función filter.
La 10ª relación 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,
Estos ejercicios corresponden al tema 7.
Los ejercicios, y sus soluciones, se muestran a continuación.
Los ejercicios de la 9ª relación 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 |
-- --------------------------------------------------------------------- -- Funciones de orden superior -- -- --------------------------------------------------------------------- -- --------------------------------------------------------------------- -- Ejercicio 8. Redefinir por recursión la función -- takeWhile :: (a -> Bool) -> [a] -> [a] -- tal que (takeWhile p xs) es la lista de los elemento de xs hasta el -- primero que no cumple la propiedad p. Por ejemplo, -- takeWhile (<7) [2,3,9,4,5] == [2,3] -- --------------------------------------------------------------------- takeWhile' :: (a -> Bool) -> [a] -> [a] takeWhile' _ [] = [] takeWhile' p (x:xs) | p x = x : takeWhile' p xs | otherwise = [] -- --------------------------------------------------------------------- -- Ejercicio 9. Redefinir por recursión la función -- dropWhile :: (a -> Bool) -> [a] -> [a] -- tal que (dropWhile p xs) es la lista de eliminando los elemento de xs -- hasta el primero que cumple la propiedad p. Por ejemplo, -- dropWhile (<7) [2,3,9,4,5] => [9,4,5] -- --------------------------------------------------------------------- dropWhile' :: (a -> Bool) -> [a] -> [a] dropWhile' _ [] = [] dropWhile' p (x:xs) | p x = dropWhile' p xs | otherwise = x:xs -- --------------------------------------------------------------------- -- 4. Definiciones mediante map, filter y plegado -- -- --------------------------------------------------------------------- -- --------------------------------------------------------------------- -- Ejercicio 10. 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 11. Redefinir, usando foldr, la función concat. Por ejemplo, -- concat' [[1,3],[2,4,6],[1,9]] == [1,3,2,4,6,1,9] -- --------------------------------------------------------------------- -- La definición por recursión es concatR :: [[a]] -> [a] concatR [] = [] concatR (xs:xss) = xs ++ concatR xss -- La definición por plegado es concat' :: [[a]] -> [a] concat' = foldr (++) [] -- --------------------------------------------------------------------- -- Ejercicio 14. Redefinir, usando foldr, la función map. Por ejemplo, -- map' (+2) [1,7,3] == [3,9,5] -- --------------------------------------------------------------------- -- La definición por recursión es mapR :: (a -> b) -> [a] -> [b] mapR f [] = [] mapR f (x:xs) = f x : mapR f xs -- La definición por plegado es map' :: (a -> b) -> [a] -> [b] map' f = foldr g [] where g x xs = f x : xs -- La definición por plegado usando lambda es map'' :: (a -> b) -> [a] -> [b] map'' f = foldr (\x y -> f x:y) [] -- Otra definición es map''' :: (a -> b) -> [a] -> [b] map''' f = foldr ((:) . f) [] -- --------------------------------------------------------------------- -- Ejercicio 15. Redefinir, usando foldr, la función filter. Por -- ejemplo, -- filter' (<4) [1,7,3,2] => [1,3,2] -- --------------------------------------------------------------------- -- La definición por recursión es filterR :: (a -> Bool) -> [a] -> [a] filterR p [] = [] filterR p (x:xs) | p x = x : filterR p xs | otherwise = filterR p xs -- La definición por plegado es filter' :: (a -> Bool) -> [a] -> [a] filter' p = foldr g [] where g x y | p x = x:y | otherwise = y -- La definición por plegado y lambda es filter' :: (a -> Bool) -> [a] -> [a] filter' p = foldr (\x y -> if (p x) then (x:y) else y) [] |
Los ejercicios de la 10ª relación 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 |
-- --------------------------------------------------------------------- -- 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 |