{"id":4266,"date":"2014-04-22T23:49:23","date_gmt":"2014-04-22T21:49:23","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=4266"},"modified":"2014-05-11T13:41:21","modified_gmt":"2014-05-11T11:41:21","slug":"i1m2013-el-tipo-abstracto-de-datos-de-los-conjuntos-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2013-el-tipo-abstracto-de-datos-de-los-conjuntos-en-haskell\/","title":{"rendered":"I1M2013: El tipo abstracto de datos de los conjuntos en Haskell"},"content":{"rendered":"<p>En la clase de hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-13\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> hemos estudiado el tipo abstracto de datos de los conjuntos y tres de sus implementaciones en Haskell:<\/p>\n<ul>\n<li>mediante listas no ordenadas con duplicados,<\/li>\n<li>mediante listas no ordenadas sin duplicados y<\/li>\n<li>mediante listas ordenadas sin duplicados.<br \/>\n<!--more--><\/li>\n<\/ul>\n<h2>Implementaci\u00f3n de los conjuntos mediante listas no ordenadas con duplicados<\/h2>\n<pre lang=\"haskell\">\nimport Data.List\n\n-- Conjuntos como listas no ordenadas con repeticiones:\nnewtype Conj a = Cj [a]\n\n-- Escritura de los conjuntos.\ninstance (Show a) => Show (Conj a) where\n    showsPrec _ (Cj s) cad = showConj s cad\n\nshowConj []     cad = showString \"{}\" cad\nshowConj (x:xs) cad = showChar '{' (shows x (showl xs cad))\n     where showl []     cad = showChar '}' cad\n           showl (x:xs) cad = showChar ',' (shows x (showl xs cad))\n\n-- Ejemplo de conjunto:\n--    > c1\n--    {2,5,1,3,7,5,3,2,1,9,0}\nc1 = foldr agregaConj conjuntoVacio [2,5,1,3,7,5,3,2,1,9,0]\n\n-- conjuntoVacio es el conjunto vac\u00edo. Por ejemplo,\n--    > conjuntoVacio\n--    {}\nconjuntoVacio = Cj []\n\n-- (esConjuntoVacio c) se verifica si c es el conjunto vac\u00edo. Por\n-- ejemplo, \n--    esConjuntoVacio c1             ==  False\n--    esConjuntoVacio conjuntoVacio  ==  True\nesConjuntoVacio (Cj []) = True\nesConjuntoVacio _       = False\n\n-- (enConj x c) se verifica si x pertenece al conjunto c. Por ejemplo, \n--    c1           ==  {2,5,1,3,7,5,3,2,1,9,0}\n--    enConj 3 c1  ==  True\n--    enConj 4 c1  ==  False\nenConj x (Cj xs) = elem x xs\n\n-- (agregaConj x c) es el conjunto obtenido a\u00f1adi\u00e9ndole el elemento x al\n-- conjunto c. Por ejemplo,\n--    c1               ==  {2,5,1,3,7,5,3,2,1,9,0}\n--    agregaConj 5 c1  ==  {5,2,5,1,3,7,5,3,2,1,9,0}\nagregaConj x (Cj a) = Cj (x:a)\n\n-- (eliminaConj x c) es el conjunto obtenido eliminando el elemento x\n-- del conjunto c. Por ejemplo,\n--    c1                ==  {2,5,1,3,7,5,3,2,1,9,0}\n--    eliminaConj 3 c1  ==  {2,5,1,7,5,2,1,9,0}\neliminaConj x (Cj xs) = Cj (filter (\/= x) xs)\n<\/pre>\n<h2>Implementaci\u00f3n de los conjuntos mediante listas no ordenadas sin duplicados<\/h2>\n<pre lang=\"haskell\">\nimport qualified Conjunto\nimport Data.List\n\n-- Conjuntos como listas no ordenadas sin repeticiones:\nnewtype Conj a = Cj [a]\n\n-- Escritura de los conjuntos.\ninstance (Show a) => Show (Conj a) where\n    showsPrec _ (Cj s) cad = showConj s cad\n\nshowConj []     cad = showString \"{}\" cad\nshowConj (x:xs) cad = showChar '{' (shows x (showl xs cad))\n     where showl []     cad = showChar '}' cad\n           showl (x:xs) cad = showChar ',' (shows x (showl xs cad))\n\n-- Ejemplo de conjunto:\n--    > c1\n--    {7,5,3,2,1,9,0}\nc1 = foldr agregaConj conjuntoVacio [2,5,1,3,7,5,3,2,1,9,0]\n\n-- conjuntoVacio es el conjunto vac\u00edo. Por ejemplo,\n--    > conjuntoVacio\n--    {}\nconjuntoVacio = Cj []\n\n-- (esConjuntoVacio c) se verifica si c es el conjunto vac\u00edo. Por\n-- ejemplo, \n--    esConjuntoVacio c1             ==  False\n--    esConjuntoVacio conjuntoVacio  ==  True\nesConjuntoVacio (Cj []) = True\nesConjuntoVacio _       = False\n\n-- (enConj x c) se verifica si x pertenece al conjunto c. Por ejemplo, \n--    c1           ==  {2,5,1,3,7,5,3,2,1,9,0}\n--    enConj 3 c1  ==  True\n--    enConj 4 c1  ==  False\nenConj x (Cj xs) = elem x xs\n\n-- (agregaConj x c) es el conjunto obtenido a\u00f1adi\u00e9ndole el elemento x al\n-- conjunto c. Por ejemplo,\n--    c1               ==  {7,5,3,2,1,9,0}\n--    agregaConj 5 c1  ==  {7,5,3,2,1,9,0}\n--    agregaConj 4 c1  ==  {4,7,5,3,2,1,9,0}\nagregaConj x s@(Cj xs) | enConj x s = s\n                       | otherwise  = Cj (x:xs)\n\n-- (eliminaConj x c) es el conjunto obtenido eliminando el elemento x\n-- del conjunto c. Por ejemplo,\n--    c1                ==  {7,5,3,2,1,9,0}\n--    eliminaConj 3 c1  ==  {7,5,2,1,9,0}\neliminaConj x (Cj s) = Cj (delete x s)\n<\/pre>\n<h2>Implementaci\u00f3n de los conjuntos mediante listas ordenadas sin duplicados<\/h2>\n<pre lang=\"haskell\">\nimport qualified ConjuntoOrd\nimport Data.List\n\n-- Conjuntos como listas ordenadas sin repeticiones:\nnewtype Conj a = Cj [a]\n\n-- Escritura de los conjuntos.\ninstance (Show a) => Show (Conj a) where\n    showsPrec _ (Cj s) cad = showConj s cad\n\nshowConj []     cad = showString \"{}\" cad\nshowConj (x:xs) cad = showChar '{' (shows x (showl xs cad))\n     where showl []     cad = showChar '}' cad\n           showl (x:xs) cad = showChar ',' (shows x (showl xs cad))\n\n-- Ejemplo de conjunto:\n--    > c1\n--    {0,1,2,3,5,7,9}\nc1 = foldr agregaConj conjuntoVacio [2,5,1,3,7,5,3,2,1,9,0]\n\n-- conjuntoVacio es el conjunto vac\u00edo. Por ejemplo,\n--    > conjuntoVacio\n--    {}\nconjuntoVacio = Cj []\n\n-- (esConjuntoVacio c) se verifica si c es el conjunto vac\u00edo. Por\n-- ejemplo, \n--    esConjuntoVacio c1             ==  False\n--    esConjuntoVacio conjuntoVacio  ==  True\nesConjuntoVacio (Cj []) = True\nesConjuntoVacio _       = False\n\n-- (enConj x c) se verifica si x pertenece al conjunto c. Por ejemplo, \n--    c1           ==  {0,1,2,3,5,7,9}\n--    enConj 3 c1  ==  True\n--    enConj 4 c1  ==  False\nenConj x (Cj s) = elem x (takeWhile (<= x) s)\n\n-- (agregaConj x c) es el conjunto obtenido a\u00f1adi\u00e9ndole el elemento x al\n-- conjunto c. Por ejemplo,\n--    c1               ==  {0,1,2,3,5,7,9}\n--    agregaConj 5 c1  ==  {0,1,2,3,5,7,9}\n--    agregaConj 4 c1  ==  {0,1,2,3,4,5,7,9}\nagregaConj x (Cj s) = Cj (agrega x s)\n    where agrega x []                    = [x]                \n          agrega x s@(y:ys) | (x>y)      = y : (agrega x ys)\n                            | (x<y)      = x : s\n                            | otherwise  = s\n\n-- (eliminaConj x c) es el conjunto obtenido eliminando el elemento x\n-- del conjunto c. Por ejemplo,\n--    c1                ==  {0,1,2,3,5,7,9}\n--    eliminaConj 3 c1  ==  {0,1,2,5,7,9}\neliminaConj x (Cj s) = Cj (elimina x s)\n    where elimina x []                   = []\n          elimina x s@(y:ys) | (x>y)     = y : (elimina x ys)\n                             | (x<y)     = s\n                             | otherwise = ys\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas hemos estudiado el tipo abstracto de datos de los conjuntos y tres de sus implementaciones en Haskell: mediante listas no ordenadas con duplicados, mediante listas no ordenadas sin duplicados y mediante listas ordenadas sin duplicados.<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","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":[1],"tags":[270,300,194],"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\/4266"}],"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=4266"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4266\/revisions"}],"predecessor-version":[{"id":4267,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4266\/revisions\/4267"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=4266"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=4266"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=4266"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}