{"id":5261,"date":"2016-01-08T18:05:54","date_gmt":"2016-01-08T17:05:54","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=5261"},"modified":"2016-01-09T12:07:06","modified_gmt":"2016-01-09T11:07:06","slug":"i1m2015-mayorias-parlamentarias","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2015-mayorias-parlamentarias\/","title":{"rendered":"I1M2015: Mayor\u00edas parlamentarias"},"content":{"rendered":"<p>En la cuarta parte de la clase de hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-15\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> hemos comentado las soluciones a los ejercicios de la relaci\u00f3n 17 sobre mayor\u00edas parlamentarias como caso de estudio de tipos algebraicos.<\/p>\n<p>Los ejercicios y su soluci\u00f3n se muestran a continuaci\u00f3n<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\n-- ---------------------------------------------------------------------\n-- Introducci\u00f3n                                                       --\n-- ---------------------------------------------------------------------\n\n-- En esta relaci\u00f3n se presenta un caso de estudio de los tipos\n-- de datos algebraicos para estudiar las mayor\u00edas parlamentarias. \n-- Adem\u00e1s, con QuickCheck, se comprueban propiedades de las funciones\n-- definidas. \n\n-- ---------------------------------------------------------------------\n-- Importaci\u00f3n de librer\u00edas auxiliares                                --\n-- ---------------------------------------------------------------------\n\nimport Data.List\nimport Test.QuickCheck\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1. Definir el tipo de datos Partido para representar los\n-- partidos de un Parlamento. Los partidos son P1, P2,..., P8. La clase \n-- Partido est\u00e1 contenida en Eq, Ord y Show. \n-- ---------------------------------------------------------------------\n\ndata Partido\n    = P1 | P2 | P3 | P4 | P5 | P6 | P7 | P8\n    deriving (Eq, Ord, Show)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2. Definir el tipo Parlamentarios para representar el\n-- n\u00famero de parlamentarios que posee un partido en el parlamento. \n-- ---------------------------------------------------------------------\n\ntype Parlamentarios = Integer\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3. Definir el tipo (Tabla a b) para representar una lista\n-- de pares de elementos el primero de tipo a y el segundo de tipo\n-- b. Definir Asamblea para representar una tabla de partidos y\n-- parlamentarios.  \n-- ---------------------------------------------------------------------\n\ntype Tabla a b = [(a,b)]\ntype Asamblea  = Tabla Partido Parlamentarios\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4. Definir la funci\u00f3n\n--    partidos :: Asamblea -> [Partido]\n-- tal que (partidos a) es la lista de partidos en la asamblea a. Por\n-- ejemplo, \n--    partidos [(P1,3),(P3,5),(P4,3)]  ==>  [P1,P3,P4]\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa definici\u00f3n\npartidos :: Asamblea -> [Partido]\npartidos a = [p | (p,_) <- a]\n\n-- 2\u00aa definici\u00f3n\npartidos2 :: Asamblea -> [Partido]\npartidos2 = map fst\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 5. Definir la funci\u00f3n\n--    parlamentarios :: Asamblea -> Integer\n-- tal que (parlamentarios a) es el n\u00famero de parlamentarios en la\n-- asamblea a. Por ejemplo,\n--    parlamentarios [(P1,3),(P3,5),(P4,3)]  ==>  11\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa definici\u00f3n\nparlamentarios :: Asamblea -> Integer\nparlamentarios a = sum [e | (_,e) <- a]\n\n-- 2\u00aa definici\u00f3n\nparlamentarios2 :: Asamblea -> Integer\nparlamentarios2 = sum . map snd\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 6. Definir la funci\u00f3n\n--    busca :: Eq a => a -> Tabla a b -> b\n-- tal que (busca x t) es el valor correspondiente a x en la tabla\n-- t. Por ejemplo, \n--    ghci> busca P3 [(P1,2),(P3,19)]\n--    19\n--    ghci> busca P8 [(P1,2),(P3,19)]\n--    *** Exception: no tiene valor en la tabla\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa soluci\u00f3n (por comprensi\u00f3n)\nbusca :: Eq a => a -> Tabla a b -> b\nbusca x t | null xs   = error \"no tiene valor en la tabla\"\n          | otherwise = head xs\n   where xs = [b | (a,b) <- t, a == x]\n\n\n-- 2\u00aa definici\u00f3n (por recursi\u00f3n)\nbusca2 :: Eq a => a -> Tabla a b -> b\nbusca2 x []            = error \"no tiene valor en la tabla\"\nbusca2 x ((x',y):xys)\n    | x == x'         = y\n    | otherwise       = busca2 x xys\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 7. Definir la funci\u00f3n\n--    busca' :: Eq a => a -> Table a b -> Maybe b \n-- tal que (busca' x t) es justo el valor correspondiente a x en la\n-- tabla t, o Nothing si x no tiene valor. Por ejemplo, \n--    busca' P3 [(P1,2),(P3,19)]   ==   Just 19\n--    busca' P8 [(P1,2),(P3,19)]   ==   Nothing\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa definici\u00f3n\nbusca' :: Eq a => a -> Tabla a b -> Maybe b\nbusca' x t | null xs   = Nothing\n           | otherwise = Just (head xs)\n   where xs = [b | (a,b) <- t, a == x]\n\n-- 2\u00aa definici\u00f3n\nbusca'2 :: Eq a => a -> Tabla a b -> Maybe b\nbusca'2 x []          = Nothing\nbusca'2 x ((x',y):xys)\n    | x == x'         = Just y\n    | otherwise       = busca'2 x xys\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 8. Comprobar con QuickCheck que si (busca' x t) es\n-- Nothing, entonces x es distinto de todos los elementos de t. \n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_BuscaNothing :: Integer -> [(Integer,Integer)] -> Property\nprop_BuscaNothing x t =\n    busca' x t == Nothing ==>\n    x `notElem` [a | (a,_) <- t]\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_BuscaNothing\n--    OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 9. Comprobar que la funci\u00f3n busca' es equivalente a la\n-- funci\u00f3n lookup del Prelude. \n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_BuscaEquivLookup :: Integer -> [(Integer,Integer)] -> Bool\nprop_BuscaEquivLookup x t =\n    busca' x t == lookup x t\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_BuscaEquivLookup\n--    OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 10. Definir el tipo Coalicion como una lista de partidos.\n-- ---------------------------------------------------------------------\n\ntype Coalicion = [Partido]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 11. Definir la funci\u00f3n\n--    mayoria :: Asamblea -> Integer\n-- tal que (mayoria xs) es el n\u00famero de parlamentarios que se necesitan\n-- para tener la mayor\u00eda en la asamblea xs. Por ejemplo,\n--    mayoria [(P1,3),(P3,5),(P4,3)]   ==   6 \n--    mayoria [(P1,3),(P3,6)]          ==   5\n-- ---------------------------------------------------------------------\n\nmayoria :: Asamblea -> Integer\nmayoria xs = parlamentarios xs `div` 2 + 1 \n\n-- ---------------------------------------------------------------------\n-- Ejercicio 12. Definir la funci\u00f3n\n--    coaliciones :: Asamblea -> Integer -> [Coalicion]\n-- tal que (coaliciones xs n) es la lista de coaliciones necesarias para\n-- alcanzar n parlamentarios. Por ejemplo,\n--    coaliciones [(P1,3),(P2,2),(P3,1)] 3   ==  [[P2,P3],[P1]]\n--    coaliciones [(P1,3),(P3,5),(P4,3)] 6   ==  [[P3,P4],[P1,P4],[P1,P3]]\n--    coaliciones [(P1,3),(P3,5),(P4,3)] 9   ==  [[P1,P3,P4]]\n--    coaliciones [(P1,3),(P3,5),(P4,3)] 14  ==  []\n--    coaliciones [(P1,3),(P3,5),(P4,3)] 2   ==  [[P4],[P3],[P1]]\n--    coaliciones [(P1,2),(P3,5),(P4,3)] 6   ==  [[P3,P4],[P1,P3]]\n-- ---------------------------------------------------------------------\n\ncoaliciones :: Asamblea -> Integer -> [Coalicion]\ncoaliciones _ n | n <= 0  = [[]]\ncoaliciones [] n          = []\ncoaliciones ((p,m):xs) n  =\n    coaliciones xs n ++ [p:c | c <- coaliciones xs (n-m)]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 13. Definir la funci\u00f3n\n--    mayorias :: Asamblea -> [Coalicion]\n-- tal que (mayorias a) es la lista de coaliciones mayoritarias en la\n-- asamblea a. Por ejemplo,\n--    mayorias [(P1,3),(P3,5),(P4,3)]   ==   [[P3,P4],[P1,P4],[P1,P3]]\n--    mayorias [(P1,2),(P3,5),(P4,3)]   ==   [[P3,P4],[P1,P3]]\n-- ---------------------------------------------------------------------\n\nmayorias :: Asamblea -> [Coalicion]\nmayorias asamblea = \n    coaliciones asamblea (mayoria asamblea)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 14. Definir el tipo de datos Asamblea.\n-- ---------------------------------------------------------------------\n\ndata Asamblea2 = A Asamblea \n                 deriving Show\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 15. Definir la propiedad\n--    esMayoritaria :: Coalicion -> Asamblea -> Bool\n-- tal que (esMayoritaria c a) se verifica si la coalici\u00f3n c es\n-- mayoritaria en la asamblea a. Por ejemplo, \n--    esMayoritaria [P3,P4] [(P1,3),(P3,5),(P4,3)]   ==   True\n--    esMayoritaria [P4] [(P1,3),(P3,5),(P4,3)]      ==   False\n-- ---------------------------------------------------------------------\n\nesMayoritaria :: Coalicion -> Asamblea -> Bool\nesMayoritaria c a =\n    sum [busca p a | p <- c] >= mayoria a\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 16. Comprobar con QuickCheck que las coaliciones\n-- obtenidas por (mayorias asamblea) son coaliciones mayoritarias en la\n-- asamblea. \n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_MayoriasSonMayoritarias :: Asamblea2 -> Bool\nprop_MayoriasSonMayoritarias (A asamblea) =\n  and [esMayoritaria c asamblea | c <- mayorias asamblea]\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_MayoriasSonMayoritarias\n--    OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 17. Definir la funci\u00f3n\n--    esMayoritariaMinimal :: Coalicion -> Asamblea -> Bool\n-- tal que (esMayoritariaMinimal c a) se verifica si la coalici\u00f3n c es\n-- mayoritaria en la asamblea a, pero si se quita a c cualquiera de sus\n-- partidos la coalici\u00f3n resultante no es mayoritaria. Por ejemplo, \n--    esMayoritariaMinimal [P3,P4] [(P1,3),(P3,5),(P4,3)]     ==  True\n--    esMayoritariaMinimal [P1,P3,P4] [(P1,3),(P3,5),(P4,3)]  ==  False\n-- ---------------------------------------------------------------------\n\nesMayoritariaMinimal :: Coalicion -> Asamblea -> Bool\nesMayoritariaMinimal c a =\n    esMayoritaria c a &&\n    and [not(esMayoritaria (delete p c) a) | p <-c]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 18. Comprobar con QuickCheck si las coaliciones obtenidas\n-- por (mayorias asamblea) son coaliciones mayoritarias minimales en la\n-- asamblea.  \n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_MayoriasSonMayoritariasMinimales :: Asamblea2 -> Bool\nprop_MayoriasSonMayoritariasMinimales (A asamblea) =\n  and [esMayoritariaMinimal c asamblea | c <- mayorias asamblea]\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_MayoriasSonMayoritariasMinimales\n--    Falsifiable, after 0 tests:\n--    A [(P1,1),(P2,0),(P3,1),(P4,1),(P5,0),(P6,1),(P7,0),(P8,1)]\n\n-- Por tanto, no se cumple la propiedad. Para buscar una coalici\u00f3n no\n-- minimal generada por mayorias, definimos la funci\u00f3n\ncontraejemplo a =\n    head [c | c <- mayorias a, not(esMayoritariaMinimal c a)]\n\n-- el c\u00e1lculo del contraejemplo es\n-- ghci> contraejemplo [(P1,1),(P2,0),(P3,1),(P4,1),(P5,0),(P6,1),(P7,0),(P8,1)]\n-- [P4,P6,P7,P8]\n\n-- La coalici\u00f3n [P4,P6,P7,P8] no es minimal ya que [P4,P6,P8] tambi\u00e9n es\n-- mayoritaria. En efecto,\n--    ghci> esMayoritaria [P4,P6,P8] \n--                        [(P1,1),(P2,0),(P3,1),(P4,1),\n--                         (P5,0),(P6,1),(P7,0),(P8,1)]\n--    True\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 19. Definir la funci\u00f3n\n--    coalicionesMinimales :: Asamblea -> Integer -> [Coalicion,Parlamentarios]\n-- tal que (coalicionesMinimales xs n) es la lista de coaliciones\n-- minimales necesarias para alcanzar n parlamentarios. Por ejemplo, \n--    ghci> coalicionesMinimales [(P1,3),(P3,5),(P4,3)] 6\n--    [([P3,P4],8),([P1,P4],6),([P1,P3],8)]\n--    ghci> coalicionesMinimales [(P1,3),(P3,5),(P4,3)] 5\n--    [([P3],5),([P1,P4],6)]\n-- ---------------------------------------------------------------------\n\ncoalicionesMinimales :: Asamblea -> Integer -> [(Coalicion,Parlamentarios)]\ncoalicionesMinimales _ n | n <= 0  = [([],0)]\ncoalicionesMinimales [] n          = []\ncoalicionesMinimales ((p,m):xs) n  =\n    coalicionesMinimales xs n ++ \n    [(p:ys, t+m) | (ys,t) <- coalicionesMinimales xs (n-m), t<n]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 20. Definir la funci\u00f3n\n--    mayoriasMinimales :: Asamblea -> [Coalicion]\n-- tal que (mayoriasMinimales a) es la lista de coaliciones mayoritarias\n-- minimales en la asamblea a. Por ejemplo,\n--    mayoriasMinimales [(P1,3),(P3,5),(P4,3)] == [[P3,P4],[P1,P4],[P1,P3]]\n-- ---------------------------------------------------------------------\n\nmayoriasMinimales :: Asamblea -> [Coalicion]\nmayoriasMinimales asamblea = \n    [c | (c,_) <- coalicionesMinimales asamblea (mayoria asamblea)]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 21. Comprobar con QuickCheck que las coaliciones\n-- obtenidas por (mayoriasMinimales asamblea) son coaliciones\n-- mayoritarias minimales en la asamblea. \n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_MayoriasMinimalesSonMayoritariasMinimales :: Asamblea2 -> Bool\nprop_MayoriasMinimalesSonMayoritariasMinimales (A asamblea) =\n  and [esMayoritariaMinimal c asamblea \n       | c <- mayoriasMinimales asamblea]\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_MayoriasMinimalesSonMayoritariasMinimales\n--    OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Funciones auxiliares                                               --\n-- ---------------------------------------------------------------------\n\n-- (listaDe n g) es una lista de n elementos, donde cada elemento es\n-- generado por g. Por ejemplo, \n--    ghci> muestra (listaDe 3 (arbitrary :: Gen Int))\n--    [-1,1,-1]\n--    [-2,-4,-1]\n--    [1,-1,0]\n--    [1,-1,1]\n--    [1,-1,1]\n--    ghci> muestra (listaDe 3 (arbitrary :: Gen Bool))\n--    [False,True,False]\n--    [True,True,False]\n--    [False,False,True]\n--    [False,False,True]\n--    [True,False,True]\nlistaDe :: Int -> Gen a -> Gen [a]\nlistaDe n g = sequence [g | i <- [1..n]]\n\n-- paresDeIgualLongitud genera pares de listas de igual longitud. Por\n-- ejemplo, \n--    ghci> muestra (paresDeIgualLongitud (arbitrary :: Gen Int))\n--    ([-4,5],[-4,2])\n--    ([],[])\n--    ([0,0],[-2,-3])\n--    ([2,-2],[-2,1])\n--    ([0],[-1])\n--    ghci> muestra (paresDeIgualLongitud (arbitrary :: Gen Bool))\n--    ([False,True,False],[True,True,True])\n--    ([True],[True])\n--    ([],[])\n--    ([False],[False])\n--    ([],[])\nparesDeIgualLongitud :: Gen a -> Gen ([a],[a])\nparesDeIgualLongitud gen =\n    do n <- arbitrary\n       xs <- listaDe (abs n) gen\n       ys <- listaDe (abs n) gen\n       return (xs,ys)\n\n-- generaAsamblea esun generador de datos de tipo Asamblea. Por ejemplo, \n--    ghci> muestra generaAsamblea\n--    A [(P1,1),(P2,1),(P3,0),(P4,1),(P5,0),(P6,1),(P7,0),(P8,1)]\n--    A [(P1,0),(P2,1),(P3,1),(P4,1),(P5,0),(P6,1),(P7,0),(P8,1)]\n--    A [(P1,1),(P2,2),(P3,0),(P4,1),(P5,0),(P6,1),(P7,2),(P8,0)]\n--    A [(P1,1),(P2,0),(P3,1),(P4,0),(P5,0),(P6,1),(P7,1),(P8,1)]\n--    A [(P1,1),(P2,0),(P3,0),(P4,0),(P5,1),(P6,1),(P7,1),(P8,0)]\ngeneraAsamblea :: Gen Asamblea2\ngeneraAsamblea = \n    do xs <- listaDe 8 (arbitrary :: Gen Integer)\n       return (A (zip [P1,P2,P3,P4,P5,P6,P7,P8] (map abs xs)))\n\ninstance Arbitrary Asamblea2 where\n    arbitrary   = generaAsamblea\n    -- coarbitrary = undefined\n<\/pre>\n<p>El c\u00f3digo anterior se encuentra tambi\u00e9n en <a href=\"https:\/\/github.com\/jaalonso\/I1M-Ejercicios\/blob\/master\/Ejercicios\/Rel_17_sol.hs\">GitHub<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>En la cuarta parte de la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas hemos comentado las soluciones a los ejercicios de la relaci\u00f3n 17 sobre mayor\u00edas parlamentarias como caso de estudio de tipos algebraicos. Los ejercicios y su soluci\u00f3n se muestran a continuaci\u00f3n<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[250],"tags":[270,310,126],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_likes_enabled":false,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5261"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/comments?post=5261"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5261\/revisions"}],"predecessor-version":[{"id":5262,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5261\/revisions\/5262"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=5261"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=5261"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=5261"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}