I1M2013: Ejercicios sobre funciones de orden superior y plegados
En la clase de hoy del curso Informática (de 1º de Grado en Matemáticas) se han comentado las soluciones de los 5 primeros ejercicios 12ª relación. En los ejercicios se piden definiciones de funciones de orden superior y con plegados.
Los ejercicios y 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 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 |
-- --------------------------------------------------------------------- -- Importación de librerías auxiliares -- -- --------------------------------------------------------------------- import Test.QuickCheck -- --------------------------------------------------------------------- -- Ejercicio 1. 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 2. 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 -- --------------------------------------------------------------------- -- Ejercicio 3. 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 4.1. La función -- divideMedia :: [Double] -> ([Double],[Double]) -- dada una lista numérica, xs, calcula 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, -- divideMedia [6,7,2,8,6,3,4] == ([2.0,3.0,4.0],[6.0,7.0,8.0,6.0]) -- divideMedia [1,2,3] == ([1.0],[3.0]) -- Definir la función divideMedia por filtrado, comprensión y -- recursión. -- --------------------------------------------------------------------- -- La definición por filtrado es divideMediaF :: [Double] -> ([Double],[Double]) divideMediaF xs = (filter (<m) xs, filter (>m) xs) 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 -- Nota: En la definición de media se usa la función fromIntegral tal -- que (fromIntegral x) es el número real correspondiente al número -- entero x. media :: [Double] -> Double media xs = (sum xs) / fromIntegral (length xs) -- La definición por comprensión es divideMediaC :: [Double] -> ([Double],[Double]) divideMediaC xs = ([x | x <- xs, x < m], [x | x <- xs, x > m]) where m = media xs -- La definición por recursión es 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 4.2. 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 4.3. 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 4.4. 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 4.5. 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 5. 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,5,6,48,7,2] == [[],[2,0,4],[6,48],[2]] -- --------------------------------------------------------------------- segmentos :: (a -> Bool) -> [a] -> [[a]] segmentos _ [] = [] segmentos p xs = takeWhile p xs : (segmentos p (dropWhile (not.p) (dropWhile p xs))) |