I1M2010: Ejercicios de Haskell (relaciones 16, 17 y 18)
En la clase de hoy de Informática de 1º del Grado en Matemáticas hemos comentado la resolución de ejercicios de las relaciones 16, 17 y 18 cuyas soluciones se muestran a continuación.
Las soluciones de los ejercicios de la relación 16 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 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 |
-- --------------------------------------------------------------------- -- Ejercicio 1. Usando el tipo de dato Nat y la función suma definidas -- en las transparencias del tema 9, definir la función -- producto :: Nat -> Nat -> Nat -- tal que (producto m n) es el producto de los números naturales m y -- n. Por ejemplo, -- *Main> producto (Suc (Suc Cero)) (Suc (Suc (Suc Cero))) -- Suc (Suc (Suc (Suc (Suc (Suc Cero))))) -- --------------------------------------------------------------------- data Nat = Cero | Suc Nat deriving (Eq, Show) suma :: Nat -> Nat -> Nat suma Cero n = n suma (Suc m) n = Suc (suma m n) producto :: Nat -> Nat -> Nat producto Cero _ = Cero producto (Suc m) n = suma n (producto m n) -- --------------------------------------------------------------------- -- Nota. En los siguientes ejercicios se trabajará con árboles binarios -- definidos como sigue -- data Arbol = Hoja Int -- | Nodo Arbol Int Arbol -- deriving (Show, Eq) -- Por ejemplo, el árbol -- 5 -- / \ -- / \ -- 3 7 -- / \ / \ -- 1 4 6 9 -- se representa por -- Nodo (Nodo (Hoja 1) 3 (Hoja 4)) -- 5 -- (Nodo (Hoja 6) 7 (Hoja 9)) -- --------------------------------------------------------------------- data Arbol = Hoja Int | Nodo Arbol Int Arbol deriving (Show, Eq) ejArbol :: Arbol ejArbol = Nodo (Nodo (Hoja 1) 3 (Hoja 4)) 5 (Nodo (Hoja 6) 7 (Hoja 9)) -- -------------------------------------------------------------------- -- Ejercicio 2. Definir la función -- ocurre :: Int -> Arbol -> Bool -- tal que (ocurre x a) se verifica si x ocurre en el árbol a como valor -- de un nodo o de una hoja. Por ejemplo, -- ocurre 4 ejArbol == True -- ocurre 10 ejArbol == False -- --------------------------------------------------------------------- ocurre :: Int -> Arbol -> Bool ocurre m (Hoja n) = m == n ocurre m (Nodo i n d) = m == n || ocurre m i || ocurre m d -- --------------------------------------------------------------------- -- Ejercicio 3. En el preludio está definido el tipo de datos -- data Ordering = LT | EQ | GT -- junto con la función -- compare :: Ord a => a -> a -> Ordering -- que decide si un valor en un tipo ordenado es menor (LT), igual (EQ) -- o mayor (GT) que otro. -- -- Usando esta función, redefinir la función -- ocurre :: Int -> Arbol -> Bool -- del ejercicio anterior. -- --------------------------------------------------------------------- ocurre' :: Int -> Arbol -> Bool ocurre' m (Hoja n) = m == n ocurre' m (Nodo i n d) = case compare m n of LT -> ocurre' m i EQ -> True GT -> ocurre' m d -- --------------------------------------------------------------------- -- Ejercicio 4. ¿Porqué la segunda definición de ocurre es más eficiente -- que la primera? -- --------------------------------------------------------------------- -- La nueva definición es más eficiente porque sólo necesita una -- comparación por nodo, mientras que la definición de las -- transparencias necesita dos comparaciones por nodo. -- --------------------------------------------------------------------- -- Nota. En los siguientes ejercicios se trabajará con árboles binarios -- definidos como sigue -- type ArbolB = HojaB Int -- | NodoB ArbolB ArbolB -- deriving Show -- Por ejemplo, el árbol -- . -- / \ -- / \ -- . . -- / \ / \ -- 1 4 6 9 -- se representa por -- NodoB (NodoB (HojaB 1) (HojaB 4)) -- (NodoB (HojaB 6) (HojaB 9)) -- --------------------------------------------------------------------- data ArbolB = HojaB Int | NodoB ArbolB ArbolB deriving Show ejArbolB :: ArbolB ejArbolB = NodoB (NodoB (HojaB 1) (HojaB 4)) (NodoB (HojaB 6) (HojaB 9)) -- --------------------------------------------------------------------- -- Ejercicio 5. Definir la función -- nHojas :: ArbolB -> Int -- tal que (nHojas a) es el número de hojas del árbol a. Por ejemplo, -- nHojas (NodoB (HojaB 5) (NodoB (HojaB 3) (HojaB 7))) == 3 -- nHojas ejArbolB == 4 -- --------------------------------------------------------------------- nHojas :: ArbolB -> Int nHojas (HojaB _) = 1 nHojas (NodoB a1 a2) = nHojas a1 + nHojas a2 -- --------------------------------------------------------------------- -- Ejercicio 6. Se dice que un árbol de este tipo es balanceado si es -- una hoja o bien si para cada nodo se tiene que el número de hojas en -- cada uno de sus subárboles difiere como máximo en uno y sus -- subárboles son balanceados. Definir la función -- balanceado :: ArbolB -> BoolB -- tal que (balanceado a) se verifica si a es un árbol balanceado. Por -- ejemplo, -- bakaceado ejArbolB -- ==> True -- balanceado (NodoB (HojaB 5) (NodoB (HojaB 3) (HojaB 7))) -- ==> True -- balanceado (NodoB (HojaB 5) (NodoB (HojaB 3) (NodoB (HojaB 5) (HojaB 7)))) -- ==> False -- --------------------------------------------------------------------- balanceado :: ArbolB -> Bool balanceado (HojaB _) = True balanceado (NodoB a1 a2) = abs (nHojas a1 - nHojas a2) <= 1 && balanceado a1 && balanceado a2 -- --------------------------------------------------------------------- -- Ejercicio 7. Definir la función -- mitades :: [a] -> ([a],[a]) -- tal que (mitades xs) es un par de listas que se obtiene al dividir xs -- en dos mitades cuya longitud difiere como máximo en uno. Por ejemplo, -- mitades [2,3,5,1,4,7] == ([2,3,5],[1,4,7]) -- mitades [2,3,5,1,4,7,9] == ([2,3,5],[1,4,7,9]) -- --------------------------------------------------------------------- mitades :: [a] -> ([a],[a]) mitades xs = splitAt (length xs `div` 2) xs -- --------------------------------------------------------------------- -- Ejercicio 8. Definir la función -- arbolBalanceado :: [Int] -> ArbolB -- tal que (arbolBalanceado xs) es el árbol balanceado correspondiente -- a la lista xs. Por ejemplo, -- *Main> arbolBalanceado [2,5,3] -- NodoB (HojaB 2) (NodoB (HojaB 5) (HojaB 3)) -- *Main> arbolBalanceado [2,5,3,7] -- NodoB (NodoB (HojaB 2) (HojaB 5)) (NodoB (HojaB 3) (HojaB 7)) -- --------------------------------------------------------------------- arbolBalanceado :: [Int] -> ArbolB arbolBalanceado [x] = HojaB x arbolBalanceado xs = NodoB (arbolBalanceado ys) (arbolBalanceado zs) where (ys,zs) = mitades xs -- --------------------------------------------------------------------- -- Ejercicio 9. Los números naturales menores que 10 que son múltiplos -- de 3 ó 5 son 3, 5, 6 y 9. La suma de estos múltiplos es 23. Definir -- la función -- sumaMultiplosMenores :: Integer -> Integer -- tal que (sumaMultiplosMenores n) es la suma de todos los múltiplos de -- 3 ó 5 menores que n. Por ejemplo, -- sumaMultiplosMenores 10 => 23 -- Calcular la suma de todos los múltiplos de 3 ó 5 menores que 1000, -- indicando el tiempo y el espacio empleado. -- --------------------------------------------------------------------- sumaMultiplosMenores :: Integer -> Integer sumaMultiplosMenores n = sum [x | x <- [1..n-1], multiplo x 3 || multiplo x 5] where multiplo x y = mod x y == 0 -- Cálculo: -- *Main> :set +s -- *Main> sumaMultiplosMenores 1000 -- 233168 -- (0.03 secs, 1053460 bytes) -- --------------------------------------------------------------------- -- Ejercicio 10. Definir la función -- productoCartesiano :: [[a]] -> [[a]] -- tal que (productoCartesiano xss) es el producto cartesiano de los conjuntos -- xss. Por ejemplo, -- *Main> productoCartesiano [[1,3],[2,5]] -- [[1,2],[1,5],[3,2],[3,5]] -- *Main> productoCartesiano [[1,3],[2,5],[6,4]] -- [[1,2,6],[1,2,4],[1,5,6],[1,5,4],[3,2,6],[3,2,4],[3,5,6],[3,5,4]] -- *Main> productoCartesiano [[1,3,5],[2,4]] -- [[1,2],[1,4],[3,2],[3,4],[5,2],[5,4]] -- *Main> productoCartesiano [] -- [[]] -- --------------------------------------------------------------------- productoCartesiano :: [[a]] -> [[a]] productoCartesiano [] = [[]] productoCartesiano (xs:xss) = [x:ys | x <- xs, ys <- productoCartesiano xss] -- --------------------------------------------------------------------- -- Ejercicio 11. Definir (por recursión, plegado y comprensión) el -- predicado -- comprueba :: [[Int]] -> Bool -- tal que tal que (comprueba xss) se verifica si cada elemento de la -- lista de listas xss contiene algún número par. Por ejemplo, -- comprueba [[1,2],[3,4,5],[8]] == True -- comprueba [[1,2],[3,5]] == False -- --------------------------------------------------------------------- -- La definición por recursión es compruebaR :: [[Int]] -> Bool compruebaR [] = True compruebaR (xs:xss) = tienePar xs && compruebaR xss -- (tienePar xs) se verifica si xs contiene algún número par. tienePar :: [Int] -> Bool tienePar [] = False tienePar (x:xs) = even x || tienePar xs -- La definición por plegado es compruebaP :: [[Int]] -> Bool compruebaP = foldr f True where f x y = tienePar x && y -- La definición por comprensión es compruebaC :: [[Int]] -> Bool compruebaC xss = and [or [even x | x <- xs] | xs <- xss] -- --------------------------------------------------------------------- -- Ejercicio 12. Definir la función -- pertenece :: Ord a => a -> [a] -> Bool -- tal que (pertenece x ys) se verifica si x pertenece a la lista -- ordenada creciente, finita o infinita, ys. Por ejemplo, -- pertenece 22 [1,3,22,34] ==> True -- pertenece 22 [1,3,34] ==> False -- pertenece 23 [1,3..] ==> True -- pertenece 22 [1,3..] ==> False -- --------------------------------------------------------------------- pertenece :: Ord a => a -> [a] -> Bool pertenece _ [] = False pertenece x (y:ys) | x > y = pertenece x ys | x == y = True | otherwise = False -- La definición de pertenece puede simplificarse pertenece' :: Ord a => a -> [a] -> Bool pertenece' x ys = elem x (takeWhile (<= x) ys) -- --------------------------------------------------------------------- -- Ejercicio 13. Definir la función -- listasMayores :: [[Int]] -> [[Int]] -- tal que (listasMayores xss) es la lista de las listas de xss de mayor -- suma. Por ejemplo, -- *Main> listasMayores [[1,3,5],[2,7],[1,1,2],[3],[5]] -- [[1,3,5],[2,7]] -- --------------------------------------------------------------------- listasMayores :: [[Int]] -> [[Int]] listasMayores xss = [xs | xs <- xss, sum xs == m] where m = maximum [sum xs | xs <- xss] -- --------------------------------------------------------------------- -- Ejercicio 14. Definir la constante -- pares :: Int -- tal que pares es la lista de todos los pares de números enteros -- positivos ordenada según la suma de sus componentes y el valor de la -- primera componente. Por ejemplo, -- *Main> take 11 pares -- [(1,1),(1,2),(2,1),(1,3),(2,2),(3,1),(1,4),(2,3),(3,2),(4,1),(1,5)] -- --------------------------------------------------------------------- pares :: [(Integer,Integer)] pares = [(x,z-x) | z <- [1..], x <- [1..z-1]] -- --------------------------------------------------------------------- -- Ejercicio 15. Definir la constante -- paresDestacados :: [(Integer,Integer)] -- tal que paresDestadados es la lista de pares de números enteros (x,y) -- tales que 11 divide a x+13y y 13 divide a x+11y. -- --------------------------------------------------------------------- paresDestacados :: [(Integer,Integer)] paresDestacados = [(x,y) | (x,y) <- pares, mod (x+13*y) 11 == 0, mod (x+11*y) 13 == 0] -- --------------------------------------------------------------------- -- Ejercicio 16. Definir la constante -- parDestacadoConMenorSuma :: Integer -- tal que pardestacadoconmenorsuma es el par destacado con menor suma y -- calcular su valor y su posición en la lista pares. -- --------------------------------------------------------------------- -- La definición es parDestacadoConMenorSuma :: (Integer,Integer) parDestacadoConMenorSuma = head paresDestacados -- El valor es -- *Main> parDestacadoConMenorSuma -- (23,5) -- La posición es -- *Main> 1 + length (takeWhile (/=parDestacadoConMenorSuma) pares) -- 374 -- --------------------------------------------------------------------- -- Ejercicio 17. Definir la función -- limite :: (Num a, Enum a, Num b, Ord b) => (a -> b) -> b -> b -- tal que (limite f a) es el valor de f en el primer término x tal que -- para todo y entre x+1 y x+100, el valor absoluto de f(y)-f(x) es -- menor que a. Por ejemplo, -- limite (\n -> (2*n+1)/(n+5)) 0.001 == 1.9900110987791344 -- limite (\n -> (1+1/n)**n) 0.001 == 2.714072874546881 -- --------------------------------------------------------------------- limite :: (Num a, Enum a, Num b, Ord b) => (a -> b) -> b -> b limite f a = head [f x | x <- [1..], maximum [abs(f y - f x) | y <- [x+1..x+100]] < a] -- --------------------------------------------------------------------- -- Ejercicio 18. Definir la función -- esLimite :: (Num a, Enum a, Num b, Ord b) => (a -> b) -> b -> b -> Bool -- tal que (esLimite f b a) se verifica si existe un x tal que para todo -- y entre x+1 y x+100, el valor absoluto de f(y)-b es menor que a. Por -- ejemplo, -- esLimite (\n -> (2*n+1)/(n+5)) 2 0.01 == True -- esLimite (\n -> (1+1/n)**n) (exp 1) 0.01 == True -- --------------------------------------------------------------------- esLimite :: (Num a, Enum a, Num b, Ord b) => (a -> b) -> b -> b -> Bool esLimite f b a = not (null [x | x <- [1..], maximum [abs(f y - b) | y <- [x+1..x+100]] < a]) |
Las soluciones de los ejercicios de la relación 17 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 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 |
-- --------------------------------------------------------------------- -- Importación de librerías auxiliares -- --------------------------------------------------------------------- import Test.QuickCheck import Data.List -- --------------------------------------------------------------------- -- Nota. En los siguientes ejercicios se pide adaptar funciones sobre -- lista a funciones sobre árboles definidos por -- data Arbol a = Hoja | Nodo (Arbol a) a (Arbol a) deriving Show -- --------------------------------------------------------------------- data Arbol a = Hoja | Nodo (Arbol a) a (Arbol a) deriving Show -- --------------------------------------------------------------------- -- Ejercicio 1. La función take está definida por -- take :: Int -> [a] -> [a] -- take 0 = [] -- take (n+1) [] = [] -- take (n+1) (x:xs) = x : take n xs -- Definir la función -- takeArbol :: Int -> Arbol a -> Arbol a -- tal que (takeArbol n t) es el subárbol de t de profundidad n. Por -- ejemplo, -- *Main> takeArbol 0 (Nodo Hoja 6 (Nodo (Nodo Hoja 5 Hoja) 7 Hoja)) -- Hoja -- *Main> takeArbol 1 (Nodo Hoja 6 (Nodo (Nodo Hoja 5 Hoja) 7 Hoja)) -- Nodo Hoja 6 Hoja -- *Main> takeArbol 2 (Nodo Hoja 6 (Nodo (Nodo Hoja 5 Hoja) 7 Hoja)) -- Nodo Hoja 6 (Nodo Hoja 7 Hoja) -- *Main> takeArbol 3 (Nodo Hoja 6 (Nodo (Nodo Hoja 5 Hoja) 7 Hoja)) -- Nodo Hoja 6 (Nodo (Nodo Hoja 5 Hoja) 7 Hoja) -- *Main> takeArbol 4 (Nodo Hoja 6 (Nodo (Nodo Hoja 5 Hoja) 7 Hoja)) -- Nodo Hoja 6 (Nodo (Nodo Hoja 5 Hoja) 7 Hoja) -- --------------------------------------------------------------------- takeArbol 0 _ = Hoja takeArbol (n+1) Hoja = Hoja takeArbol (n+1) (Nodo l x r) = Nodo (takeArbol n l) x (takeArbol n r) -- --------------------------------------------------------------------- -- Ejercicio 2. La función -- repeat :: a -> [a] -- está definida de forma que (repeat x) es la lista formada por -- infinitos elementos x. Por ejemplo, -- repeat 3 ==> [3,3,3,3,3,3,3,3,3,3,3,3,3,... -- La definición de repeat es -- repeat x = xs where xs = x:xs -- Definir la función -- repeatArbol :: a -> Arbol a -- tal que (repeatArbol x) es es árbol con infinitos nodos x. Por -- ejemplo, -- Main> takeArbol 0 (repeatArbol 3) -- Hoja -- *Main> takeArbol 1 (repeatArbol 3) -- Nodo Hoja 3 Hoja -- *Main> takeArbol 2 (repeatArbol 3) -- Nodo (Nodo Hoja 3 Hoja) 3 (Nodo Hoja 3 Hoja) -- --------------------------------------------------------------------- repeatArbol :: a -> Arbol a repeatArbol x = Nodo t x t where t = repeatArbol x -- --------------------------------------------------------------------- -- Ejercicio 3. La función -- replicate :: Int -> a -> [a] -- está definida por -- replicate n = take n . repeat -- es tal que (replicate n x) es la lista de longitud n cuyos elementos -- son x. Por ejemplo, -- replicate 3 5 ==> [5,5,5] -- Definir la función -- replicateArbol :: Int -> a -> Arbol a -- tal que (replicate n x) es el árbol de profundidad n cuyos nodos son -- x. Por ejemplo, -- *Main> replicateArbol 0 5 -- Hoja -- *Main> replicateArbol 1 5 -- Nodo Hoja 5 Hoja -- *Main> replicateArbol 2 5 -- Nodo (Nodo Hoja 5 Hoja) 5 (Nodo Hoja 5 Hoja) -- --------------------------------------------------------------------- replicateArbol :: Int -> a -> Arbol a replicateArbol n = takeArbol n . repeatArbol -- --------------------------------------------------------------------- -- Ejercicio 4. Extender el procedimiento de decisión de tautologías -- para incluir las disyunciones (Disj) y las equivalencias (Equi). Por -- ejemplo, -- *Main> esTautologia (Equi (Var 'A') (Disj (Var 'A') (Var 'A'))) -- True -- *Main> esTautologia (Equi (Var 'A') (Disj (Var 'A') (Var 'B'))) -- False -- Se incluye el código del procedimiento visto en clase para que se -- extienda de manera adecuada. -- --------------------------------------------------------------------- data FProp = Const Bool | Var Char | Neg FProp | Conj FProp FProp | Disj FProp FProp -- Añadido | Impl FProp FProp | Equi FProp FProp -- Añadido deriving Show type Interpretacion = [(Char, Bool)] valor :: Interpretacion -> FProp -> Bool valor _ (Const b) = b valor i (Var x) = busca x i valor i (Neg p) = not (valor i p) valor i (Conj p q) = valor i p && valor i q valor i (Disj p q) = valor i p || valor i q -- Añadido valor i (Impl p q) = valor i p <= valor i q valor i (Equi p q) = valor i p == valor i q -- Añadido busca :: Eq c => c -> [(c,v)] -> v busca c t = head [v | (c',v) <- t, c == c'] variables :: FProp -> [Char] variables (Const _) = [] variables (Var x) = [x] variables (Neg p) = variables p variables (Conj p q) = variables p ++ variables q variables (Disj p q) = variables p ++ variables q -- Añadido variables (Impl p q) = variables p ++ variables q variables (Equi p q) = variables p ++ variables q -- Añadido interpretacionesVar :: Int -> [[Bool]] interpretacionesVar 0 = [[]] interpretacionesVar (n+1) = map (False:) bss ++ map (True:) bss where bss = interpretacionesVar n interpretaciones :: FProp -> [Interpretacion] interpretaciones p = map (zip vs) (interpretacionesVar (length vs)) where vs = nub (variables p) esTautologia :: FProp -> Bool esTautologia p = and [valor i p | i <- interpretaciones p] -- --------------------------------------------------------------------- -- Ejercicio 5. Definir la función -- interpretacionesVar' :: Int -> [[Bool]] -- que sea equivalente a interpretacionesVar pero que en su definición -- use listas de comprensión en lugar de map. Por ejemplo, -- *Main> interpretacionesVar' 2 -- [[False,False],[False,True],[True,False],[True,True]] -- --------------------------------------------------------------------- interpretacionesVar' :: Int -> [[Bool]] interpretacionesVar' 0 = [[]] interpretacionesVar' (n+1) = [False:bs | bs <- bss] ++ [True:bs | bs <- bss] where bss = interpretacionesVar' n -- --------------------------------------------------------------------- -- Ejercicio 6. Definir la función -- interpretaciones' :: FProp -> [Interpretacion] -- que sea equivalente a interpretaciones pero que en su definición -- use listas de comprensión en lugar de map. Por ejemplo, -- *Main> interpretaciones' (Impl (Var 'A') (Conj (Var 'A') (Var 'B'))) -- [[('A',False),('B',False)], -- [('A',False),('B',True)], -- [('A',True),('B',False)], -- [('A',True),('B',True)]] -- --------------------------------------------------------------------- interpretaciones' :: FProp -> [Interpretacion] interpretaciones' p = [zip vs i | i <- is] where vs = nub (variables p) is = interpretacionesVar (length vs) |
Las soluciones de los ejercicios de la relación 18 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 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 |
-- ---------------------------------------------------------------------------- -- Importación de librerías auxiliares -- -- ---------------------------------------------------------------------------- import Test.QuickCheck import Data.Char import Data.List -- ---------------------------------------------------------------------------- -- Ejercicio 1 (Modelización de un juego de cartas) -- ---------------------------------------------------------------------------- -- Ejercicio resuelto. Definir el tipo de datos Palo para representar los cuatro -- palos de la baraja: picas, corazones, diamantes y tréboles. Hacer que -- Palo sea instancia de Eq y Show. -- ---------------------------------------------------------------------------- -- La definición es data Palo = Picas | Corazones | Diamantes | Treboles deriving (Eq, Show) -- ---------------------------------------------------------------------------- -- Nota: Para que QuickCheck pueda generar elementos del tipo Palo se usa la -- siguiente función. -- ---------------------------------------------------------------------------- instance Arbitrary Palo where arbitrary = elements [Picas, Corazones, Diamantes, Treboles] -- ---------------------------------------------------------------------------- -- Ejercicio resuelto. Definir el tipo de dato Color para representar los -- colores de las cartas: rojo y negro. Hacer que Color sea instancia de Show. -- ---------------------------------------------------------------------------- data Color = Rojo | Negro deriving Show -- ---------------------------------------------------------------------------- -- Ejercicio 1.1. Definir la función -- color :: Palo -> Color -- tal que (color p) es el color del palo p. Por ejemplo, -- color Corazones ==> Rojo -- Nota: Los corazones y los diamantes son rojos. Las picas y los -- tréboles son negros. -- ---------------------------------------------------------------------------- color :: Palo -> Color color Picas = Negro color Corazones = Rojo color Diamantes = Rojo color Treboles = Negro -- ---------------------------------------------------------------------------- -- Ejercicio resuelto. Los valores de las cartas se dividen en los numéricos -- (del 2 al 10) y las figuras (sota, reina, rey y as). Definir el tipo -- de datos Valor para representar los valores de las cartas. Hacer que -- Valor sea instancia de Eq y Show. -- Main> :type Sota -- Sota :: Valor -- Main> :type Reina -- Reina :: Valor -- Main> :type Rey -- Rey :: Valor -- Main> :type As -- As :: Valor -- Main> :type Numerico 3 -- Numerico 3 :: Valor -- ---------------------------------------------------------------------------- data Valor = Numerico Int | Sota | Reina | Rey | As deriving (Eq, Show) -- ---------------------------------------------------------------------------- -- Nota: Para que QuickCheck pueda generar elementos del tipo Valor se usa la -- siguiente función. -- ---------------------------------------------------------------------------- instance Arbitrary Valor where arbitrary = oneof $ [ do return c | c <- [Sota,Reina,Rey,As] ] ++ [ do n <- choose (2,10) return (Numerico n) ] -- ---------------------------------------------------------------------------- -- Ejercicio 1.2. El orden de valor de las cartas (de mayor a menor) es -- as, rey, reina, sota y las numéricas según su valor. Definir la función -- mayor :: Valor -> Valor -> Bool -- tal que (mayor x y) se verifica si la carta x es de mayor valor que -- la carta y. Por ejemplo, -- mayor Sota (Numerico 7) ==> True -- mayor (Numerico 10) Reina ==> False -- ---------------------------------------------------------------------------- mayor :: Valor -> Valor -> Bool mayor _ As = False mayor As _ = True mayor _ Rey = False mayor Rey _ = True mayor _ Reina = False mayor Reina _ = True mayor _ Sota = False mayor Sota _ = True mayor (Numerico m) (Numerico n) = m > n -- ---------------------------------------------------------------------------- -- Ejercicio 1.3. Comprobar con QuickCheck si dadas dos cartas, una -- siempre tiene mayor valor que la otra. En caso de que no se verifique, -- añadir la menor precondición para que lo haga. -- ---------------------------------------------------------------------------- -- La propiedad es prop_MayorValor1 a b = mayor a b || mayor b a -- La comprobación es -- Main> quickCheck prop_MayorValor1 -- Falsifiable, after 2 tests: -- Sota -- Sota -- que indica que la propiedad es falsa porque la sota no tiene mayor -- valor que la sota. -- La precondición es que las cartas sean distintas: prop_MayorValor a b = a /= b ==> mayor a b || mayor b a -- La comprobación es -- Main> quickCheck prop_MayorValor -- OK, passed 100 tests. -- ---------------------------------------------------------------------------- -- Ejercicio resuelto. Definir el tipo de datos Carta para representar las -- cartas mediante un valor y un palo. Hacer que Carta sea instancia de -- Eq y Show. Por ejemplo, -- Main> :type Carta Rey Corazones -- Carta Rey Corazones :: Carta -- Main> :type Carta (Numerico 4) Corazones -- Carta (Numerico 4) Corazones :: Carta -- ---------------------------------------------------------------------------- data Carta = Carta Valor Palo deriving (Eq, Show) -- ---------------------------------------------------------------------------- -- Ejercicio 1.4. Definir la función -- valor :: Carta -> Valor -- tal que (valor c) es el valor de la carta c. Por ejemplo, -- valor (Carta Rey Corazones) ==> Rey -- ---------------------------------------------------------------------------- valor :: Carta -> Valor valor (Carta v p) = v -- ---------------------------------------------------------------------------- -- Ejercicio 1.5. Definir la función -- palo :: Carta -> Valor -- tal que (palo c) es el palo de la carta c. Por ejemplo, -- palo (Carta Rey Corazones) ==> Corazones -- ---------------------------------------------------------------------------- palo :: Carta -> Palo palo (Carta v p) = p -- ---------------------------------------------------------------------------- -- Nota: Para que QuickCheck pueda generar elementos del tipo Carta se usa la -- siguiente función. -- ---------------------------------------------------------------------------- instance Arbitrary Carta where arbitrary = do v <- arbitrary p <- arbitrary return (Carta v p) -- ---------------------------------------------------------------------------- -- Ejercicio 1.6. Definir la función -- ganaCarta :: Palo -> Carta -> Carta -> Bool -- tal que (ganaCarta p c1 c2) se verifica si la carta c1 le gana a la -- carta c2 cuando el palo de triunfo es p (es decir, las cartas son del -- mismo palo y el valor de c1 es mayor que el de c2 o c1 es del palo de -- triunfo). Por ejemplo, -- ganaCarta Corazones (Carta Sota Picas) (Carta (Numerico 5) Picas) -- ==> True -- ganaCarta Corazones (Carta (Numerico 3) Picas) (Carta Sota Picas) -- ==> False -- ganaCarta Corazones (Carta (Numerico 3) Corazones) (Carta Sota Picas) -- ==> True -- ganaCarta Treboles (Carta (Numerico 3) Corazones) (Carta Sota Picas) -- ==> False -- ---------------------------------------------------------------------------- ganaCarta :: Palo -> Carta -> Carta -> Bool ganaCarta triunfo c c' | palo c == palo c' = mayor (valor c) (valor c') | palo c == triunfo = True | otherwise = False -- ---------------------------------------------------------------------------- -- Ejercicio 1.7. Comprobar con QuickCheck si dadas dos cartas, una -- siempre gana a la otra. -- ---------------------------------------------------------------------------- -- La propiedad es prop_GanaCarta t c1 c2 = ganaCarta t c1 c2 || ganaCarta t c2 c1 -- La comprobación es -- Main> quickCheck prop_GanaCarta -- Falsifiable, after 0 tests: -- Diamantes -- Carta Rey Corazones -- Carta As Treboles -- que indica que la propiedad no se verifica ya que cuando el triunfo -- es diamantes, ni el rey de corazones le gana al as de tréboles ni el -- as de tréboles le gana al rey de corazones. -- ---------------------------------------------------------------------------- -- Ejercicio resuelto. Definir el tipo de datos Mano para representar una -- mano en el juego de cartas. Una mano es vacía o se obtiene agregando -- una carta a una mano. Hacer Mano instancia de Eq y Show. Por ejemplo, -- Main> :type Agrega (Carta Rey Corazones) Vacia -- Agrega (Carta Rey Corazones) Vacia :: Mano -- ---------------------------------------------------------------------------- data Mano = Vacia | Agrega Carta Mano deriving (Eq, Show) -- ---------------------------------------------------------------------------- -- Nota: Para que QuickCheck pueda generar elementos del tipo Mano se usa la -- siguiente función. -- ---------------------------------------------------------------------------- instance Arbitrary Mano where arbitrary = do cs <- arbitrary let mano [] = Vacia mano (c:cs) = Agrega c (mano cs) return (mano cs) -- ---------------------------------------------------------------------------- -- Ejercicio 1.8. Una mano gana a una carta c si alguna carta de la mano -- le gana a c. Definir la función -- ganaMano :: Palo -> Mano -> Carta -> Bool -- tal que (gana t m c) se verifica si la mano m le gana a la carta c -- cuando el triunfo es t. Por ejemplo, -- ganaMano Picas (Agrega (Carta Sota Picas) Vacia) (Carta Rey Corazones) -- ==> True -- ganaMano Picas (Agrega (Carta Sota Picas) Vacia) (Carta Rey Picas) -- ==> False -- ---------------------------------------------------------------------------- ganaMano :: Palo -> Mano -> Carta -> Bool ganaMano triunfo Vacia c' = False ganaMano triunfo (Agrega c m) c' = ganaCarta triunfo c c' || ganaMano triunfo m c' -- ---------------------------------------------------------------------------- -- Ejercicio 1.9. Definir la función -- eligeCarta :: Palo -> Carta -> Mano -> Carta -- tal que (eligeCarta t c1 m) es la mejor carta de la mano m frente a -- la carta c cuando el triunfo es t. La estrategia para elegir la mejor -- carta es la siguiente: -- * Si la mano sólo tiene una carta, se elige dicha carta. -- * Si la primera carta de la mano es del palo de c1 y la mejor del -- resto no es del palo de c1, se elige la primera de la mano, -- * Si la primera carta de la mano no es del palo de c1 y la mejor -- del resto es del palo de c1, se elige la mejor del resto. -- * Si la primera carta de la mano le gana a c1 y la mejor del -- resto no le gana a c1, se elige la primera de la mano, -- * Si la mejor del resto le gana a c1 y la primera carta de la mano -- no le gana a c1, se elige la mejor del resto. -- * Si el valor de la primera carta es mayor que el de la mejor del -- resto, se elige la mejor del resto. -- * Si el valor de la primera carta no es mayor que el de la mejor -- del resto, se elige la primera carta. -- ---------------------------------------------------------------------------- eligeCarta :: Palo -> Carta -> Mano -> Carta eligeCarta triunfo c1 (Agrega c Vacia) = c -- 1 eligeCarta triunfo c1 (Agrega c resto) | palo c == palo c1 && palo c' /= palo c1 = c -- 2 | palo c /= palo c1 && palo c' == palo c1 = c' -- 3 | ganaCarta triunfo c c1 && not (ganaCarta triunfo c' c1) = c -- 4 | ganaCarta triunfo c' c1 && not (ganaCarta triunfo c c1) = c' -- 5 | mayor (valor c) (valor c') = c' -- 6 | otherwise = c -- 7 where c' = eligeCarta triunfo c1 resto -- ---------------------------------------------------------------------------- -- Ejercicio 1.10. Comprobar con QuickCheck que si una mano es ganadora, -- entonces la carta elegida es ganadora. -- ---------------------------------------------------------------------------- -- La propiedad es prop_eligeCartaGanaSiEsPosible triunfo c m = m /= Vacia ==> ganaMano triunfo m c == ganaCarta triunfo (eligeCarta triunfo c m) c -- La comprobación es -- Main> quickCheck prop_eligeCartaGanaSiEsPosible -- Falsifiable, after 12 tests: -- Corazones -- Carta Rey Treboles -- Agrega (Carta (Numerico 6) Diamantes) -- (Agrega (Carta Sota Picas) -- (Agrega (Carta Rey Corazones) -- (Agrega (Carta (Numerico 10) Treboles) -- Vacia))) -- La carta elegida es el 10 de tréboles (porque tiene que ser del mismo -- palo), aunque el mano hay una carta (el rey de corazones) que gana. |