I1M2015: Mayorías parlamentarias
En la cuarta parte de la clase de hoy de Informática de 1º del Grado en Matemáticas hemos comentado las soluciones a los ejercicios de la relación 17 sobre mayorías parlamentarias como caso de estudio de tipos algebraicos.
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 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 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 |
-- --------------------------------------------------------------------- -- Introducción -- -- --------------------------------------------------------------------- -- En esta relación se presenta un caso de estudio de los tipos -- de datos algebraicos para estudiar las mayorías parlamentarias. -- Además, con QuickCheck, se comprueban propiedades de las funciones -- definidas. -- --------------------------------------------------------------------- -- Importación de librerías auxiliares -- -- --------------------------------------------------------------------- import Data.List import Test.QuickCheck -- --------------------------------------------------------------------- -- Ejercicio 1. Definir el tipo de datos Partido para representar los -- partidos de un Parlamento. Los partidos son P1, P2,..., P8. La clase -- Partido está contenida en Eq, Ord y Show. -- --------------------------------------------------------------------- data Partido = P1 | P2 | P3 | P4 | P5 | P6 | P7 | P8 deriving (Eq, Ord, Show) -- --------------------------------------------------------------------- -- Ejercicio 2. Definir el tipo Parlamentarios para representar el -- número de parlamentarios que posee un partido en el parlamento. -- --------------------------------------------------------------------- type Parlamentarios = Integer -- --------------------------------------------------------------------- -- Ejercicio 3. Definir el tipo (Tabla a b) para representar una lista -- de pares de elementos el primero de tipo a y el segundo de tipo -- b. Definir Asamblea para representar una tabla de partidos y -- parlamentarios. -- --------------------------------------------------------------------- type Tabla a b = [(a,b)] type Asamblea = Tabla Partido Parlamentarios -- --------------------------------------------------------------------- -- Ejercicio 4. Definir la función -- partidos :: Asamblea -> [Partido] -- tal que (partidos a) es la lista de partidos en la asamblea a. Por -- ejemplo, -- partidos [(P1,3),(P3,5),(P4,3)] ==> [P1,P3,P4] -- --------------------------------------------------------------------- -- 1ª definición partidos :: Asamblea -> [Partido] partidos a = [p | (p,_) <- a] -- 2ª definición partidos2 :: Asamblea -> [Partido] partidos2 = map fst -- --------------------------------------------------------------------- -- Ejercicio 5. Definir la función -- parlamentarios :: Asamblea -> Integer -- tal que (parlamentarios a) es el número de parlamentarios en la -- asamblea a. Por ejemplo, -- parlamentarios [(P1,3),(P3,5),(P4,3)] ==> 11 -- --------------------------------------------------------------------- -- 1ª definición parlamentarios :: Asamblea -> Integer parlamentarios a = sum [e | (_,e) <- a] -- 2ª definición parlamentarios2 :: Asamblea -> Integer parlamentarios2 = sum . map snd -- --------------------------------------------------------------------- -- Ejercicio 6. Definir la función -- busca :: Eq a => a -> Tabla a b -> b -- tal que (busca x t) es el valor correspondiente a x en la tabla -- t. Por ejemplo, -- ghci> busca P3 [(P1,2),(P3,19)] -- 19 -- ghci> busca P8 [(P1,2),(P3,19)] -- *** Exception: no tiene valor en la tabla -- --------------------------------------------------------------------- -- 1ª solución (por comprensión) busca :: Eq a => a -> Tabla a b -> b busca x t | null xs = error "no tiene valor en la tabla" | otherwise = head xs where xs = [b | (a,b) <- t, a == x] -- 2ª definición (por recursión) busca2 :: Eq a => a -> Tabla a b -> b busca2 x [] = error "no tiene valor en la tabla" busca2 x ((x',y):xys) | x == x' = y | otherwise = busca2 x xys -- --------------------------------------------------------------------- -- Ejercicio 7. Definir la función -- busca' :: Eq a => a -> Table a b -> Maybe b -- tal que (busca' x t) es justo el valor correspondiente a x en la -- tabla t, o Nothing si x no tiene valor. Por ejemplo, -- busca' P3 [(P1,2),(P3,19)] == Just 19 -- busca' P8 [(P1,2),(P3,19)] == Nothing -- --------------------------------------------------------------------- -- 1ª definición busca' :: Eq a => a -> Tabla a b -> Maybe b busca' x t | null xs = Nothing | otherwise = Just (head xs) where xs = [b | (a,b) <- t, a == x] -- 2ª definición busca'2 :: Eq a => a -> Tabla a b -> Maybe b busca'2 x [] = Nothing busca'2 x ((x',y):xys) | x == x' = Just y | otherwise = busca'2 x xys -- --------------------------------------------------------------------- -- Ejercicio 8. Comprobar con QuickCheck que si (busca' x t) es -- Nothing, entonces x es distinto de todos los elementos de t. -- --------------------------------------------------------------------- -- La propiedad es prop_BuscaNothing :: Integer -> [(Integer,Integer)] -> Property prop_BuscaNothing x t = busca' x t == Nothing ==> x `notElem` [a | (a,_) <- t] -- La comprobación es -- ghci> quickCheck prop_BuscaNothing -- OK, passed 100 tests. -- --------------------------------------------------------------------- -- Ejercicio 9. Comprobar que la función busca' es equivalente a la -- función lookup del Prelude. -- --------------------------------------------------------------------- -- La propiedad es prop_BuscaEquivLookup :: Integer -> [(Integer,Integer)] -> Bool prop_BuscaEquivLookup x t = busca' x t == lookup x t -- La comprobación es -- ghci> quickCheck prop_BuscaEquivLookup -- OK, passed 100 tests. -- --------------------------------------------------------------------- -- Ejercicio 10. Definir el tipo Coalicion como una lista de partidos. -- --------------------------------------------------------------------- type Coalicion = [Partido] -- --------------------------------------------------------------------- -- Ejercicio 11. Definir la función -- mayoria :: Asamblea -> Integer -- tal que (mayoria xs) es el número de parlamentarios que se necesitan -- para tener la mayoría en la asamblea xs. Por ejemplo, -- mayoria [(P1,3),(P3,5),(P4,3)] == 6 -- mayoria [(P1,3),(P3,6)] == 5 -- --------------------------------------------------------------------- mayoria :: Asamblea -> Integer mayoria xs = parlamentarios xs `div` 2 + 1 -- --------------------------------------------------------------------- -- Ejercicio 12. Definir la función -- coaliciones :: Asamblea -> Integer -> [Coalicion] -- tal que (coaliciones xs n) es la lista de coaliciones necesarias para -- alcanzar n parlamentarios. Por ejemplo, -- coaliciones [(P1,3),(P2,2),(P3,1)] 3 == [[P2,P3],[P1]] -- coaliciones [(P1,3),(P3,5),(P4,3)] 6 == [[P3,P4],[P1,P4],[P1,P3]] -- coaliciones [(P1,3),(P3,5),(P4,3)] 9 == [[P1,P3,P4]] -- coaliciones [(P1,3),(P3,5),(P4,3)] 14 == [] -- coaliciones [(P1,3),(P3,5),(P4,3)] 2 == [[P4],[P3],[P1]] -- coaliciones [(P1,2),(P3,5),(P4,3)] 6 == [[P3,P4],[P1,P3]] -- --------------------------------------------------------------------- coaliciones :: Asamblea -> Integer -> [Coalicion] coaliciones _ n | n <= 0 = [[]] coaliciones [] n = [] coaliciones ((p,m):xs) n = coaliciones xs n ++ [p:c | c <- coaliciones xs (n-m)] -- --------------------------------------------------------------------- -- Ejercicio 13. Definir la función -- mayorias :: Asamblea -> [Coalicion] -- tal que (mayorias a) es la lista de coaliciones mayoritarias en la -- asamblea a. Por ejemplo, -- mayorias [(P1,3),(P3,5),(P4,3)] == [[P3,P4],[P1,P4],[P1,P3]] -- mayorias [(P1,2),(P3,5),(P4,3)] == [[P3,P4],[P1,P3]] -- --------------------------------------------------------------------- mayorias :: Asamblea -> [Coalicion] mayorias asamblea = coaliciones asamblea (mayoria asamblea) -- --------------------------------------------------------------------- -- Ejercicio 14. Definir el tipo de datos Asamblea. -- --------------------------------------------------------------------- data Asamblea2 = A Asamblea deriving Show -- --------------------------------------------------------------------- -- Ejercicio 15. Definir la propiedad -- esMayoritaria :: Coalicion -> Asamblea -> Bool -- tal que (esMayoritaria c a) se verifica si la coalición c es -- mayoritaria en la asamblea a. Por ejemplo, -- esMayoritaria [P3,P4] [(P1,3),(P3,5),(P4,3)] == True -- esMayoritaria [P4] [(P1,3),(P3,5),(P4,3)] == False -- --------------------------------------------------------------------- esMayoritaria :: Coalicion -> Asamblea -> Bool esMayoritaria c a = sum [busca p a | p <- c] >= mayoria a -- --------------------------------------------------------------------- -- Ejercicio 16. Comprobar con QuickCheck que las coaliciones -- obtenidas por (mayorias asamblea) son coaliciones mayoritarias en la -- asamblea. -- --------------------------------------------------------------------- -- La propiedad es prop_MayoriasSonMayoritarias :: Asamblea2 -> Bool prop_MayoriasSonMayoritarias (A asamblea) = and [esMayoritaria c asamblea | c <- mayorias asamblea] -- La comprobación es -- ghci> quickCheck prop_MayoriasSonMayoritarias -- OK, passed 100 tests. -- --------------------------------------------------------------------- -- Ejercicio 17. Definir la función -- esMayoritariaMinimal :: Coalicion -> Asamblea -> Bool -- tal que (esMayoritariaMinimal c a) se verifica si la coalición c es -- mayoritaria en la asamblea a, pero si se quita a c cualquiera de sus -- partidos la coalición resultante no es mayoritaria. Por ejemplo, -- esMayoritariaMinimal [P3,P4] [(P1,3),(P3,5),(P4,3)] == True -- esMayoritariaMinimal [P1,P3,P4] [(P1,3),(P3,5),(P4,3)] == False -- --------------------------------------------------------------------- esMayoritariaMinimal :: Coalicion -> Asamblea -> Bool esMayoritariaMinimal c a = esMayoritaria c a && and [not(esMayoritaria (delete p c) a) | p <-c] -- --------------------------------------------------------------------- -- Ejercicio 18. Comprobar con QuickCheck si las coaliciones obtenidas -- por (mayorias asamblea) son coaliciones mayoritarias minimales en la -- asamblea. -- --------------------------------------------------------------------- -- La propiedad es prop_MayoriasSonMayoritariasMinimales :: Asamblea2 -> Bool prop_MayoriasSonMayoritariasMinimales (A asamblea) = and [esMayoritariaMinimal c asamblea | c <- mayorias asamblea] -- La comprobación es -- ghci> quickCheck prop_MayoriasSonMayoritariasMinimales -- Falsifiable, after 0 tests: -- A [(P1,1),(P2,0),(P3,1),(P4,1),(P5,0),(P6,1),(P7,0),(P8,1)] -- Por tanto, no se cumple la propiedad. Para buscar una coalición no -- minimal generada por mayorias, definimos la función contraejemplo a = head [c | c <- mayorias a, not(esMayoritariaMinimal c a)] -- el cálculo del contraejemplo es -- ghci> contraejemplo [(P1,1),(P2,0),(P3,1),(P4,1),(P5,0),(P6,1),(P7,0),(P8,1)] -- [P4,P6,P7,P8] -- La coalición [P4,P6,P7,P8] no es minimal ya que [P4,P6,P8] también es -- mayoritaria. En efecto, -- ghci> esMayoritaria [P4,P6,P8] -- [(P1,1),(P2,0),(P3,1),(P4,1), -- (P5,0),(P6,1),(P7,0),(P8,1)] -- True -- --------------------------------------------------------------------- -- Ejercicio 19. Definir la función -- coalicionesMinimales :: Asamblea -> Integer -> [Coalicion,Parlamentarios] -- tal que (coalicionesMinimales xs n) es la lista de coaliciones -- minimales necesarias para alcanzar n parlamentarios. Por ejemplo, -- ghci> coalicionesMinimales [(P1,3),(P3,5),(P4,3)] 6 -- [([P3,P4],8),([P1,P4],6),([P1,P3],8)] -- ghci> coalicionesMinimales [(P1,3),(P3,5),(P4,3)] 5 -- [([P3],5),([P1,P4],6)] -- --------------------------------------------------------------------- coalicionesMinimales :: Asamblea -> Integer -> [(Coalicion,Parlamentarios)] coalicionesMinimales _ n | n <= 0 = [([],0)] coalicionesMinimales [] n = [] coalicionesMinimales ((p,m):xs) n = coalicionesMinimales xs n ++ [(p:ys, t+m) | (ys,t) <- coalicionesMinimales xs (n-m), t<n] -- --------------------------------------------------------------------- -- Ejercicio 20. Definir la función -- mayoriasMinimales :: Asamblea -> [Coalicion] -- tal que (mayoriasMinimales a) es la lista de coaliciones mayoritarias -- minimales en la asamblea a. Por ejemplo, -- mayoriasMinimales [(P1,3),(P3,5),(P4,3)] == [[P3,P4],[P1,P4],[P1,P3]] -- --------------------------------------------------------------------- mayoriasMinimales :: Asamblea -> [Coalicion] mayoriasMinimales asamblea = [c | (c,_) <- coalicionesMinimales asamblea (mayoria asamblea)] -- --------------------------------------------------------------------- -- Ejercicio 21. Comprobar con QuickCheck que las coaliciones -- obtenidas por (mayoriasMinimales asamblea) son coaliciones -- mayoritarias minimales en la asamblea. -- --------------------------------------------------------------------- -- La propiedad es prop_MayoriasMinimalesSonMayoritariasMinimales :: Asamblea2 -> Bool prop_MayoriasMinimalesSonMayoritariasMinimales (A asamblea) = and [esMayoritariaMinimal c asamblea | c <- mayoriasMinimales asamblea] -- La comprobación es -- ghci> quickCheck prop_MayoriasMinimalesSonMayoritariasMinimales -- OK, passed 100 tests. -- --------------------------------------------------------------------- -- Funciones auxiliares -- -- --------------------------------------------------------------------- -- (listaDe n g) es una lista de n elementos, donde cada elemento es -- generado por g. Por ejemplo, -- ghci> muestra (listaDe 3 (arbitrary :: Gen Int)) -- [-1,1,-1] -- [-2,-4,-1] -- [1,-1,0] -- [1,-1,1] -- [1,-1,1] -- ghci> muestra (listaDe 3 (arbitrary :: Gen Bool)) -- [False,True,False] -- [True,True,False] -- [False,False,True] -- [False,False,True] -- [True,False,True] listaDe :: Int -> Gen a -> Gen [a] listaDe n g = sequence [g | i <- [1..n]] -- paresDeIgualLongitud genera pares de listas de igual longitud. Por -- ejemplo, -- ghci> muestra (paresDeIgualLongitud (arbitrary :: Gen Int)) -- ([-4,5],[-4,2]) -- ([],[]) -- ([0,0],[-2,-3]) -- ([2,-2],[-2,1]) -- ([0],[-1]) -- ghci> muestra (paresDeIgualLongitud (arbitrary :: Gen Bool)) -- ([False,True,False],[True,True,True]) -- ([True],[True]) -- ([],[]) -- ([False],[False]) -- ([],[]) paresDeIgualLongitud :: Gen a -> Gen ([a],[a]) paresDeIgualLongitud gen = do n <- arbitrary xs <- listaDe (abs n) gen ys <- listaDe (abs n) gen return (xs,ys) -- generaAsamblea esun generador de datos de tipo Asamblea. Por ejemplo, -- ghci> muestra generaAsamblea -- A [(P1,1),(P2,1),(P3,0),(P4,1),(P5,0),(P6,1),(P7,0),(P8,1)] -- A [(P1,0),(P2,1),(P3,1),(P4,1),(P5,0),(P6,1),(P7,0),(P8,1)] -- A [(P1,1),(P2,2),(P3,0),(P4,1),(P5,0),(P6,1),(P7,2),(P8,0)] -- A [(P1,1),(P2,0),(P3,1),(P4,0),(P5,0),(P6,1),(P7,1),(P8,1)] -- A [(P1,1),(P2,0),(P3,0),(P4,0),(P5,1),(P6,1),(P7,1),(P8,0)] generaAsamblea :: Gen Asamblea2 generaAsamblea = do xs <- listaDe 8 (arbitrary :: Gen Integer) return (A (zip [P1,P2,P3,P4,P5,P6,P7,P8] (map abs xs))) instance Arbitrary Asamblea2 where arbitrary = generaAsamblea -- coarbitrary = undefined |
El código anterior se encuentra también en GitHub.