{"id":5155,"date":"2015-11-04T11:39:28","date_gmt":"2015-11-04T10:39:28","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=5155"},"modified":"2015-11-07T11:48:28","modified_gmt":"2015-11-07T10:48:28","slug":"i1m2015-operaciones-conjuntistas-con-listas","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2015-operaciones-conjuntistas-con-listas\/","title":{"rendered":"I1M2015: Operaciones conjuntistas con listas"},"content":{"rendered":"<p>En la primera 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 9 sobre operaciones conjuntistas con listas.<\/p>\n<p>Los ejercicios y su soluci\u00f3n se muestran a continuaci\u00f3n<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\n-- I1M 2015-16: Rel_9_sol.hs (31 de Octubre de 2015)\n-- Operaciones conjuntistas con listas.\n-- Departamento de Ciencias de la Computaci\u00f3n e I.A.\n-- Universidad de Sevilla\n-- =====================================================================\n\n-- ---------------------------------------------------------------------\n-- Introducci\u00f3n                                                       --\n-- ---------------------------------------------------------------------\n\n-- En estas relaci\u00f3n se definen operaciones conjuntistas sobre listas.\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Librer\u00edas auxiliares                                             --\n-- ---------------------------------------------------------------------\n\nimport Test.QuickCheck\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1.1. Definir, por comprensi\u00f3n, la funci\u00f3n\n--    subconjunto :: Eq a => [a] -> [a] -> Bool\n-- tal que (subconjunto xs ys) se verifica si xs es un subconjunto de\n-- ys; es decir, si todos los elementos de xs pertenecen a ys. Por\n-- ejemplo, \n--    subconjunto [3,2,3] [2,5,3,5]  ==  True\n--    subconjunto [3,2,3] [2,5,6,5]  ==  False\n-- ---------------------------------------------------------------------\n\nsubconjunto :: Eq a => [a] -> [a] -> Bool\nsubconjunto xs ys = \n    [x | x <- xs, x `elem` ys] == xs\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1.2. Definir, por recursi\u00f3n, la funci\u00f3n\n--    subconjuntoR :: Eq a => [a] -> [a] -> Bool\n-- tal que (subconjuntoR xs ys) se verifica si xs es un subconjunto de\n-- ys; es decir, si todos los elementos de xs pertenecen a ys. Por\n-- ejemplo, \n--    subconjuntoR [3,2,3] [2,5,3,5]  ==  True\n--    subconjuntoR [3,2,3] [2,5,6,5]  ==  False\n-- ---------------------------------------------------------------------\n\nsubconjuntoR :: Eq a => [a] -> [a] -> Bool\nsubconjuntoR [] _      = True\nsubconjuntoR (x:xs) ys = x `elem` ys && subconjuntoR xs ys\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1.3. Comprobar con QuickCheck que las definiciones\n-- subconjunto y subconjuntoR son equivalentes.\n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_subconjuntoR :: [Int] -> [Int] -> Bool\nprop_subconjuntoR xs ys =\n    subconjuntoR xs ys == subconjunto xs ys\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_subconjuntoR\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1.4. Definir, mediante all, la funci\u00f3n \n--    subconjuntoA :: Eq a => [a] -> [a] -> Bool\n-- tal que (subconjuntoA xs ys) se verifica si xs es un subconjunto de\n-- ys. Por ejemplo,\n--    subconjuntoA [1,3,2,3] [1,2,3]  ==  True\n--    subconjuntoA [1,3,4,3] [1,2,3]  ==  False\n-- ---------------------------------------------------------------------\n \nsubconjuntoA :: Eq a => [a] -> [a] -> Bool\nsubconjuntoA xs ys = all (`elem` ys) xs\n \n-- ---------------------------------------------------------------------\n-- Ejercicio 1.5. Comprobar con QuickCheck que las funciones subconjunto\n-- y subconjuntoA son equivalentes.\n-- ---------------------------------------------------------------------\n \n-- La propiedad es\nprop_subconjuntoA :: [Int] -> [Int] -> Bool\nprop_subconjuntoA xs ys =\n    subconjunto xs ys == subconjuntoA xs ys  \n \n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_subconjuntoA\n--    OK, passed 100 tests.\n \n-- ---------------------------------------------------------------------\n-- Ejercicio 2. Definir la funci\u00f3n\n--    iguales :: Eq a => [a] -> [a] -> Bool\n-- tal que (iguales xs ys) se verifica si xs e ys son iguales; es decir,\n-- tienen los mismos elementos. Por ejemplo, \n--    iguales [3,2,3] [2,3]    ==  True\n--    iguales [3,2,3] [2,3,2]  ==  True\n--    iguales [3,2,3] [2,3,4]  ==  False\n--    iguales [2,3] [4,5]      ==  False\n-- ---------------------------------------------------------------------\n\niguales :: Eq a => [a] -> [a] -> Bool\niguales xs ys =\n    subconjunto xs ys && subconjunto ys xs\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3.1. Definir, por comprensi\u00f3n, la funci\u00f3n\n--    union :: Eq a => [a] -> [a] -> [a]\n-- tal que (union xs ys) es la uni\u00f3n de los conjuntos xs e ys. Por\n-- ejemplo, \n--    union [3,2,5] [5,7,3,4]  ==  [3,2,5,7,4]\n-- ---------------------------------------------------------------------\n\nunion :: Eq a => [a] -> [a] -> [a]\nunion xs ys = xs ++ [y | y <- ys, y `notElem` xs]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3.2. Definir, por recursi\u00f3n, la funci\u00f3n\n--    unionR :: Eq a => [a] -> [a] -> [a]\n-- tal que (unionR xs ys) es la uni\u00f3n de los conjuntos xs e ys. Por\n-- ejemplo, \n--    unionR [3,2,5] [5,7,3,4]  ==  [2,5,7,3,4]\n-- ---------------------------------------------------------------------\n\nunionR :: Eq a => [a] -> [a] -> [a]\nunionR []     ys = ys\nunionR (x:xs) ys | x `elem` ys = union xs ys\n                  | otherwise   = x : union xs ys\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3.3. Comprobar con QuickCheck que union y unionR son\n-- equivalentes. \n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_union :: [Int] -> [Int] -> Bool\nprop_union xs ys =\n    union xs ys `iguales` unionR xs ys\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_union\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Nota. En los ejercicios de comprobaci\u00f3n de propiedades, cuando se\n-- trata con igualdades se usa la igualdad conjuntista (definida por la\n-- funci\u00f3n iguales) en lugar de la igualdad de lista (definida por ==)\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4. Comprobar con QuickCheck que la uni\u00f3n es conmutativa.\n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_union_conmutativa :: [Int] -> [Int] -> Bool\nprop_union_conmutativa xs ys =\n    union xs ys `iguales` union ys xs\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_union_conmutativa\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 5.1. Definir, por comprensi\u00f3n, la funci\u00f3n\n--    interseccion :: Eq a => [a] -> [a] -> [a]\n-- tal que (interseccion xs ys) es la intersecci\u00f3n de xs e ys. Por\n-- ejemplo, \n--    interseccion [3,2,5] [5,7,3,4]  ==  [3,5]\n--    interseccion [3,2,5] [9,7,6,4]  ==  []\n-- ---------------------------------------------------------------------\n\ninterseccion :: Eq a => [a] -> [a] -> [a]\ninterseccion xs ys =\n    [x | x <- xs, x `elem` ys]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 5.2. Definir, por recursi\u00f3n, la funci\u00f3n\n--    interseccionR :: Eq a => [a] -> [a] -> [a]\n-- tal que (interseccionR xs ys) es la intersecci\u00f3n de xs e ys. Por\n-- ejemplo, \n--    interseccionR [3,2,5] [5,7,3,4]  ==  [3,5]\n--    interseccionR [3,2,5] [9,7,6,4]  ==  []\n-- ---------------------------------------------------------------------\n\ninterseccionR :: Eq a => [a] -> [a] -> [a]\ninterseccionR []     ys = []\ninterseccionR (x:xs) ys | x `elem` ys = x : interseccionR xs ys\n                        | otherwise   = interseccionR xs ys\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 5.3. Comprobar con QuickCheck que interseccion e\n-- interseccionR son equivalentes.\n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_interseccion :: [Int] -> [Int] -> Bool\nprop_interseccion xs ys =\n    interseccion xs ys `iguales` interseccionR xs ys\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_interseccion\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 6. Comprobar con QuickCheck si se cumple la siguiente\n-- propiedad \n--    A \u222a (B \u2229 C) = (A \u222a B) \u2229 C\n-- donde se considera la igualdad como conjuntos. En el caso de que no\n-- se cumpla verificar el contraejemplo calculado por QuickCheck.\n-- ---------------------------------------------------------------------\n\nprop_union_interseccion :: [Int] -> [Int] -> [Int] -> Bool\nprop_union_interseccion xs ys zs =\n    iguales (union xs (interseccion ys zs))\n            (interseccion (union xs ys) zs)\n\n-- La comprobaci\u00f3n es \n--    \u03bb> quickCheck prop_union_interseccion\n--    *** Failed! Falsifiable (after 3 tests and 2 shrinks): \n--    [0]\n--    []\n--    []\n-- \n-- Por tanto, la propiedad no se cumple y un contraejemplo es \n--    A = [0], B = [] y C = []\n-- ya que entonces,\n--    A \u222a (B \u2229 C) = [0] \u222a ([] \u2229 []) = [0] \u222a [] = [0] \n--    (A \u222a B) \u2229 C = ([0] \u222a []) \u2229 [] = [0] \u2229 [] = []\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 7.1. Definir, por comprensi\u00f3n, la funci\u00f3n\n--    diferencia :: Eq a => [a] -> [a] -> [a]\n-- tal que (diferencia xs ys) es la diferencia entre los conjuntos xs e\n-- ys; es decir, la lista de los elementos que s\u00f3lo pertenecen a xs. Por\n-- ejemplo,  \n--    diferencia [3,2,5,6] [5,7,3,4]  ==  [2,6]\n--    diferencia [3,2,5] [5,7,3,2]    ==  []\n-- ---------------------------------------------------------------------\n\ndiferencia :: Eq a => [a] -> [a] -> [a]\ndiferencia xs ys = [x | x <- xs, x `notElem` ys]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 7.2. Definir, por recursi\u00f3n, la funci\u00f3n\n--    diferenciaR :: Eq a => [a] -> [a] -> [a]\n-- tal que (diferenciaR xs ys) es la diferencia entre los conjuntos xs e\n-- ys; es decir, la lista de los elementos que s\u00f3lo pertenecen a xs. Por\n-- ejemplo,  \n--    diferenciaR [3,2,5,6] [5,7,3,4]  ==  [2,6]\n--    diferenciaR [3,2,5] [5,7,3,2]    ==  []\n-- ---------------------------------------------------------------------\n\ndiferenciaR :: Eq a => [a] -> [a] -> [a]\ndiferenciaR [] ys = []\ndiferenciaR (x:xs) ys | x `elem` ys = diferenciaR xs ys\n                      | otherwise   = x : diferenciaR xs ys\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 7.3. Comprobar con QuickCheck que diferencia y diferenciaR \n-- son equivalentes.\n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_diferencia :: [Int] -> [Int] -> Bool\nprop_diferencia xs ys =\n    diferencia xs ys `iguales` diferenciaR xs ys\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_diferencia\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 8. Comprobar con QuickCheck si la diferencia es\n-- conmutativa. \n-- ---------------------------------------------------------------------\n\nprop_diferencia_conmutativa :: [Int] -> [Int] -> Bool\nprop_diferencia_conmutativa xs ys =\n    iguales (diferencia xs ys) (diferencia ys xs)\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_diferencia_conmutativa\n--    *** Failed! Falsifiable (after 2 tests and 2 shrinks): \n--    [0]\n--    []\n-- que es un contraejemplo, ya que\n--    [0] - [] = [0]\n--    [] - [0] = []\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 9. Comprobar con QuickCheck si se cumple la siguiente\n-- propiedad: A \\ B \u2282 A\n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_diferencia_subconjunto :: [Int] -> [Int] -> Bool\nprop_diferencia_subconjunto xs ys =\n    subconjunto (diferencia xs ys) xs\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_diferencia_subconjunto\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 10. Comprobar con QuickCheck si se cumple la siguiente\n-- propiedad: (A \\ B) \u2229 B = \u2205.\n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_diferencia_interseccion :: [Int] -> [Int] -> Bool\nprop_diferencia_interseccion xs ys =\n    interseccion (diferencia xs ys) ys == []\n                \n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_diferencia_interseccion\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 11.1. Definir, por comprensi\u00f3n, la funci\u00f3n\n--    producto :: [a] -> [a] -> [(a,a)]\n-- tal que (producto xs ys) es el producto cartesiano de xs e ys. Por\n-- ejemplo, \n--   producto [1,3] [2,4] == [(1,2),(1,4),(3,2),(3,4)]\n-- ---------------------------------------------------------------------\n\nproducto :: [a] -> [a] -> [(a,a)]\nproducto xs ys = [(x,y) | x <- xs, y <- ys]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 11.2. Definir, por recursi\u00f3n, la funci\u00f3n\n--    productoR :: [a] -> [a] -> [(a,a)]\n-- tal que (productoR xs ys) es el producto cartesiano de xs e ys. Por\n-- ejemplo, \n--   productoR [1,3] [2,4] == [(1,2),(1,4),(3,2),(3,4)]\n-- ---------------------------------------------------------------------\n\nproductoR :: [a] -> [a] -> [(a,a)]\nproductoR []     _  = []\nproductoR (x:xs) ys = [(x,y) | y <- ys] ++ productoR xs ys\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 11.3. Comprobar con QuickCheck que producto y productoR \n-- son equivalentes.\n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_producto :: [Int] -> [Int] -> Bool\nprop_producto xs ys =\n    producto xs ys `iguales` productoR xs ys\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_producto\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 12. Comprobar con QuickCheck que el n\u00famero de elementos\n-- de (producto xs ys) es el producto del n\u00famero de elementos de xs y de\n-- ys. \n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_elementos_producto :: [Int] -> [Int] -> Bool\nprop_elementos_producto xs ys =\n    length (producto xs ys) == length xs * length ys\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_elementos_producto\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 13. Definir la funci\u00f3n \n--    subconjuntos :: [a] -> [[a]]\n-- tal que (subconjuntos xs) es la lista de las subconjuntos de la lista\n-- xs. Por ejemplo, \n--    ghci> subconjuntos [2,3,4]\n--    [[2,3,4],[2,3],[2,4],[2],[3,4],[3],[4],[]]\n--    ghci> subconjuntos [1,2,3,4]\n--    [[1,2,3,4],[1,2,3],[1,2,4],[1,2],[1,3,4],[1,3],[1,4],[1],\n--       [2,3,4],  [2,3],  [2,4],  [2],  [3,4],  [3],  [4], []]\n-- ---------------------------------------------------------------------\n\nsubconjuntos :: [a] -> [[a]]\nsubconjuntos []     = [[]]\nsubconjuntos (x:xs) = [x:ys | ys <- sub] ++ sub\n    where sub = subconjuntos xs  \n\n-- Cambiando la comprensi\u00f3n por map se obtiene\nsubconjuntos' :: [a] -> [[a]]\nsubconjuntos' []     = [[]]\nsubconjuntos' (x:xs) = sub ++ map (x:) sub\n    where sub = subconjuntos' xs  \n\n-- ---------------------------------------------------------------------\n-- Ejercicio 14. Comprobar con QuickChek que el n\u00famero de elementos de\n-- (subconjuntos xs) es 2 elevado al n\u00famero de elementos de xs.\n--\n-- Nota. Al hacer la comprobaci\u00f3n limitar el tama\u00f1o de las pruebas como\n-- se indica a continuaci\u00f3n\n--    quickCheckWith (stdArgs {maxSize=7}) prop_subconjuntos\n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_subconjuntos :: [Int] -> Bool\nprop_subconjuntos xs =\n    length (subconjuntos xs) == 2 ^ length xs\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheckWith (stdArgs {maxSize=7}) prop_subconjuntos\n--    +++ OK, passed 100 tests.\n\n<\/pre>\n<p>El c\u00f3digo correspondiente se encuentra en <a href=\"http:\/\/bit.ly\/1kgH8M7\">GitHub<\/a>.<\/p>\n<p>En la segunda parte se han comentado las soluciones a los problemas de Exercitium propuestos del 21 al 27 de octubre:<\/p>\n<ul>\n<li><a href=\"http:\/\/bit.ly\/1HyV2xJ\">Refinamiento de listas<\/a>.<\/li>\n<li><a href=\"http:\/\/bit.ly\/1HyV5tz\">Centro de masas<\/a>.<\/li>\n<li><a href=\"http:\/\/bit.ly\/1HyV2Ol\">Entero positivo con ciertas propiedades<\/a>.<\/li>\n<li><a href=\"http:\/\/bit.ly\/1HyV34J\">Mayor resto<\/a>.<\/li>\n<li><a href=\"http:\/\/bit.ly\/1HyV60v\">Lista con repeticiones<\/a>.<\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>En la primera 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 9 sobre operaciones conjuntistas con listas. 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],"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\/5155"}],"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=5155"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5155\/revisions"}],"predecessor-version":[{"id":5157,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5155\/revisions\/5157"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=5155"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=5155"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=5155"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}