I1M2015: Ejercicios sobre el TAD de los montículos en Haskell
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 sobre el TAD de los montículos en Haskell de la relación 31.
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 |
-- --------------------------------------------------------------------- -- Introducción -- -- --------------------------------------------------------------------- -- El objetivo de esta relación de ejercicios es definir funciones sobre -- el TAD de las montículos, utilizando las implementaciones estudiadas -- en el tema 20 que se encuenta en -- http://www.cs.us.es/~jalonso/cursos/i1m-15/temas/tema-20.html -- -- Para realizar los ejercicios hay que tener instalada la librería I1M -- que contiene la implementación de TAD de los montículos. Los pasos -- para instalarla son los siguientes: -- + Descargar el paquete I1M desde http://bit.ly/1pbnDqm -- + Descomprimirlo (y se crea el directorio I1M-master.zip). -- + Cambiar al directorio I1M-master. -- + Ejecutar cabal install I1M.cabal -- -- Otra forma es descargar la implementación del TAD de montículos: -- + Monticulo.hs que está en http://bit.ly/1oNy2HT -- --------------------------------------------------------------------- -- Importación de librerías -- -- --------------------------------------------------------------------- {-# LANGUAGE FlexibleInstances #-} import Test.QuickCheck -- Hay que elegir una implementación del TAD montículos: -- import Monticulo import I1M.Monticulo -- --------------------------------------------------------------------- -- Ejemplos -- -- --------------------------------------------------------------------- -- Para los ejemplos se usarán los siguientes montículos. m1, m2, m3 :: Monticulo Int m1 = foldr inserta vacio [6,1,4,8] m2 = foldr inserta vacio [7,5] m3 = foldr inserta vacio [6,1,4,8,7,5] -- --------------------------------------------------------------------- -- Ejercicio 1. Definir la función -- numeroDeNodos :: Ord a => Monticulo a -> Int -- tal que (numeroDeNodos m) es el número de nodos del montículo m. Por -- ejemplo, -- numeroDeNodos m1 == 4 -- --------------------------------------------------------------------- numeroDeNodos :: Ord a => Monticulo a -> Int numeroDeNodos m | esVacio m = 0 | otherwise = 1 + numeroDeNodos (resto m) -- --------------------------------------------------------------------- -- Ejercicio 2. Definir la función -- filtra :: Ord a => (a -> Bool) -> Monticulo a -> Monticulo a -- tal que (filtra p m) es el montículo con los nodos del montículo m -- que cumplen la propiedad p. Por ejemplo, -- ghci> m1 -- M 1 2 (M 4 1 (M 8 1 Vacio Vacio) Vacio) (M 6 1 Vacio Vacio) -- ghci> filtra even m1 -- M 4 1 (M 6 1 (M 8 1 Vacio Vacio) Vacio) Vacio -- ghci> filtra odd m1 -- M 1 1 Vacio Vacio -- --------------------------------------------------------------------- filtra :: Ord a => (a -> Bool) -> Monticulo a -> Monticulo a filtra p m | esVacio m = vacio | p mm = inserta mm (filtra p rm) | otherwise = filtra p rm where mm = menor m rm = resto m -- --------------------------------------------------------------------- -- Ejercicio 3. Definir la función -- menores :: Ord a => Int -> Monticulo a -> [a] -- tal que (menores n m) es la lista de los n menores elementos del -- montículo m. Por ejemplo, -- ghci> m1 -- M 1 2 (M 4 1 (M 8 1 Vacio Vacio) Vacio) (M 6 1 Vacio Vacio) -- ghci> menores 3 m1 -- [1,4,6] -- λ> menores 10 m1 -- [1,4,6,8] -- --------------------------------------------------------------------- menores :: Ord a => Int -> Monticulo a -> [a] menores 0 m = [] menores n m | esVacio m = [] | otherwise = menor m : menores (n-1) (resto m) -- --------------------------------------------------------------------- -- Ejercicio 4. Definir la función -- restantes :: Ord a => Int -> Monticulo a -> Monticulo a -- tal que (restantes n m) es el montículo obtenido eliminando los n -- menores elementos del montículo m. Por ejemplo, -- ghci> m1 -- M 1 2 (M 4 1 (M 8 1 Vacio Vacio) Vacio) (M 6 1 Vacio Vacio) -- ghci> restantes 3 m1 -- M 8 1 Vacio Vacio -- ghci> restantes 2 m1 -- M 6 1 (M 8 1 Vacio Vacio) Vacio -- λ> restantes 7 m1 -- Vacio -- --------------------------------------------------------------------- restantes :: Ord a => Int -> Monticulo a -> Monticulo a restantes 0 m = m restantes n m | esVacio m = vacio | otherwise = restantes (n-1) (resto m) -- --------------------------------------------------------------------- -- Ejercicio 5. Definir la función -- lista2Monticulo :: Ord a => [a] -> Monticulo a -- tal que (lista2Monticulo xs) es el montículo cuyos nodos son los -- elementos de la lista xs. Por ejemplo, -- ghci> lista2Monticulo [2,5,3,7] -- M 2 1 (M 3 2 (M 7 1 Vacio Vacio) (M 5 1 Vacio Vacio)) Vacio -- --------------------------------------------------------------------- lista2Monticulo :: Ord a => [a] -> Monticulo a lista2Monticulo = foldr inserta vacio -- --------------------------------------------------------------------- -- Ejercicio 6. Definir la función -- monticulo2Lista :: Ord a => Monticulo a -> [a] -- tal que (monticulo2Lista m) es la lista ordenada de los nodos del -- montículo m. Por ejemplo, -- ghci> m1 -- M 1 2 (M 4 1 (M 8 1 Vacio Vacio) Vacio) (M 6 1 Vacio Vacio) -- ghci> monticulo2Lista m1 -- [1,4,6,8] -- --------------------------------------------------------------------- monticulo2Lista :: Ord a => Monticulo a -> [a] monticulo2Lista m | esVacio m = [] | otherwise = menor m : monticulo2Lista (resto m) -- --------------------------------------------------------------------- -- Ejercicio 7. Definir la función -- ordenada :: Ord a => [a] -> Bool -- tal que (ordenada xs) se verifica si xs es una lista ordenada de -- forma creciente. Por ejemplo, -- ordenada [3,5,9] == True -- ordenada [3,5,4] == False -- ordenada [7,5,4] == False -- --------------------------------------------------------------------- ordenada :: Ord a => [a] -> Bool ordenada (x:y:zs) = x <= y && ordenada (y:zs) ordenada _ = True -- --------------------------------------------------------------------- -- Ejercicio 8. Comprobar con QuickCheck que para todo montículo m, -- (monticulo2Lista m) es una lista ordenada creciente. -- --------------------------------------------------------------------- -- La propiedad es prop_monticulo2Lista_ordenada :: Monticulo Int -> Bool prop_monticulo2Lista_ordenada m = ordenada (monticulo2Lista m) -- La comprobación es -- ghci> quickCheck prop_monticulo2Lista_ordenada -- +++ OK, passed 100 tests. -- --------------------------------------------------------------------- -- Ejercicio 10. Usando monticulo2Lista y lista2Monticulo, definir la -- función -- ordena :: Ord a => [a] -> [a] -- tal que (ordena xs) es la lista obtenida ordenando de forma creciente -- los elementos de xs. Por ejemplo, -- ordena [7,5,3,6,5] == [3,5,5,6,7] -- --------------------------------------------------------------------- ordena :: Ord a => [a] -> [a] ordena = monticulo2Lista . lista2Monticulo -- --------------------------------------------------------------------- -- Ejercicio 11. Comprobar con QuickCheck que para toda lista xs, -- (ordena xs) es una lista ordenada creciente. -- --------------------------------------------------------------------- -- La propiedad es prop_ordena_ordenada :: [Int] -> Bool prop_ordena_ordenada xs = ordenada (ordena xs) -- La comprobación es -- ghci> quickCheck prop_ordena_ordenada -- +++ OK, passed 100 tests. -- --------------------------------------------------------------------- -- Ejercicio 12. Definir la función -- borra :: Eq a => a -> [a] -> [a] -- tal que (borra x xs) es la lista obtenida borrando una ocurrencia de -- x en la lista xs. Por ejemplo, -- borra 1 [1,2,1] == [2,1] -- borra 3 [1,2,1] == [1,2,1] -- --------------------------------------------------------------------- borra :: Eq a => a -> [a] -> [a] borra x [] = [] borra x (y:ys) | x == y = ys | otherwise = y : borra x ys -- --------------------------------------------------------------------- -- Ejercicio 14. Definir la función esPermutación tal que -- (esPermutación xs ys) se verifique si xs es una permutación de -- ys. Por ejemplo, -- esPermutación [1,2,1] [2,1,1] == True -- esPermutación [1,2,1] [1,2,2] == False -- --------------------------------------------------------------------- esPermutacion :: Eq a => [a] -> [a] -> Bool esPermutacion [] [] = True esPermutacion [] (y:ys) = False esPermutacion (x:xs) ys = elem x ys && esPermutacion xs (borra x ys) -- --------------------------------------------------------------------- -- Ejercicio 15. Comprobar con QuickCheck que para toda lista xs, -- (ordena xs) es una permutación de xs. -- --------------------------------------------------------------------- -- La propiedad es prop_ordena_permutacion :: [Int] -> Bool prop_ordena_permutacion xs = esPermutacion (ordena xs) xs -- La comprobación es -- ghci> quickCheck prop_ordena_permutacion -- +++ OK, passed 100 tests. -- --------------------------------------------------------------------- -- Generador de montículos -- -- --------------------------------------------------------------------- -- genMonticulo es un generador de montículos. Por ejemplo, -- ghci> sample genMonticulo -- VacioM -- M (-1) 1 (M 1 1 VacioM VacioM) VacioM -- ... genMonticulo :: Gen (Monticulo Int) genMonticulo = do xs <- listOf arbitrary return (foldr inserta vacio xs) -- Montículo es una instancia de la clase arbitraria. instance Arbitrary (Monticulo Int) where arbitrary = genMonticulo |