{"id":692,"date":"2010-10-03T22:21:23","date_gmt":"2010-10-03T22:21:23","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=692"},"modified":"2010-12-22T16:47:11","modified_gmt":"2010-12-22T16:47:11","slug":"el-tipo-abstracto-de-datos-de-los-conjuntos-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/el-tipo-abstracto-de-datos-de-los-conjuntos-en-haskell\/","title":{"rendered":"El tipo abstracto de datos de los conjuntos en Haskell"},"content":{"rendered":"

\nEn este art\u00edculo contin\u00fao la serie dedicada a los tipos de datos abstractos (TAD) en Haskell. El objetivo de la serie es la elaboraci\u00f3n del tema de TAD del curso de Inform\u00e1tica del Grado en Matem\u00e1ticas<\/a>.<\/p>\n

\nEn el art\u00edculo anterior present\u00e9 el TAD de polinomios. En \u00e9ste voy a presentar los TAD de conjuntos y sus implementaciones en Haskell. <\/p>\n

\nAl igual que hice en el de polinomio usar\u00e9 m\u00f3dulos, importaciones cualificadas, indefiniciones y funciones de escritura para conseguir la abstracci\u00f3n e independencia de los resultados de las implementaciones.<\/p>\n

\nEl contenido del resto del art\u00edculo es el siguiente: el TAD de los conjuntos y su implementaci\u00f3n mediante listas no ordenadas con y sin duplicados, el TAD de los conjuntos ordenados y su implementaci\u00f3n mediante listas ordenadas sin duplicados, el TAD de los conjuntos de n\u00fameros naturales y su implementaci\u00f3n
\nmediante n\u00fameros binarios.
\n<\/p>\n

Conjuntos.hs<\/i>: El TAD de los conjuntos<\/h3>\n
\r\nmodule Conjunto\r\n    (Conj,conjuntoVacio,esConjuntoVacio,enConj,agregaConj,eliminaConj) where\r\n\r\n-- (Conj a) es el tipo de los conjunto cuyos elementos son del tipo a.\r\ndata Conj a = Undefined\r\n\r\n-- conjuntoVacio es el conjunto vac\u00edo.\r\nconjuntoVacio :: Conj a                         \r\nconjuntoVacio = undefined  \r\n\r\n-- (esConjuntoVacio c) se verifica si c es el conjunto vac\u00edo.\r\nesConjuntoVacio :: Conj a -> Bool                \r\nesConjuntoVacio = undefined \r\n\r\n-- (enConj x c) se verifica si x pertenece al conjunto c.\r\nenConj :: Eq a => a -> Conj a -> Bool \r\nenConj = undefined\r\n\r\n-- (agregaConj x c) es el conjunto obtenido a\u00f1adi\u00e9ndole el elemento x al\r\n-- conjunto c. \r\nagregaConj :: Eq a => a -> Conj a -> Conj a\r\nagregaConj = undefined\r\n\r\n-- (eliminaConj x c) es el conjunto obtenido eliminando el elemento x\r\n-- del conjunto c.\r\neliminaConj :: Eq a => a -> Conj a -> Conj a\r\neliminaConj = undefined\r\n<\/pre>\n
Implemetaci\u00f3n de los conjuntos mediante listas no ordenadas con duplicados<\/h3>\n
\r\nimport qualified Conjunto\r\nimport Data.List\r\n\r\n-- Conjuntos como listas no ordenadas con repeticiones:\r\nnewtype Conj a = Cj [a]\r\n\r\n-- Escritura de los conjuntos.\r\ninstance (Show a) => Show (Conj a) where\r\n    showsPrec _ (Cj s) cad = showConj s cad\r\n\r\nshowConj []     cad = showString \"{}\" cad\r\nshowConj (x:xs) cad = showChar '{' (shows x (showl xs cad))\r\n     where showl []     cad = showChar '}' cad\r\n           showl (x:xs) cad = showChar ',' (shows x (showl xs cad))\r\n\r\n-- Ejemplo de conjunto:\r\n--    > c1\r\n--    {2,5,1,3,7,5,3,2,1,9,0}\r\nc1 = foldr agregaConj conjuntoVacio [2,5,1,3,7,5,3,2,1,9,0]\r\n\r\n-- conjuntoVacio es el conjunto vac\u00edo. Por ejemplo,\r\n--    > conjuntoVacio\r\n--    {}\r\nconjuntoVacio = Cj []\r\n\r\n-- (esConjuntoVacio c) se verifica si c es el conjunto vac\u00edo. Por\r\n-- ejemplo, \r\n--    esConjuntoVacio c1             ==  False\r\n--    esConjuntoVacio conjuntoVacio  ==  True\r\nesConjuntoVacio (Cj []) = True\r\nesConjuntoVacio _       = False\r\n\r\n-- (enConj x c) se verifica si x pertenece al conjunto c. Por ejemplo, \r\n--    c1           ==  {2,5,1,3,7,5,3,2,1,9,0}\r\n--    enConj 3 c1  ==  True\r\n--    enConj 4 c1  ==  False\r\nenConj x (Cj xs) = elem x xs\r\n\r\n-- (agregaConj x c) es el conjunto obtenido a\u00f1adi\u00e9ndole el elemento x al\r\n-- conjunto c. Por ejemplo,\r\n--    c1               ==  {2,5,1,3,7,5,3,2,1,9,0}\r\n--    agregaConj 5 c1  ==  {5,2,5,1,3,7,5,3,2,1,9,0}\r\nagregaConj x (Cj a) = Cj (x:a)\r\n\r\n-- (eliminaConj x c) es el conjunto obtenido eliminando el elemento x\r\n-- del conjunto c. Por ejemplo,\r\n--    c1                ==  {2,5,1,3,7,5,3,2,1,9,0}\r\n--    eliminaConj 3 c1  ==  {2,5,1,7,5,2,1,9,0}\r\neliminaConj x (Cj xs) = Cj (filter (\/= x) xs)\r\n<\/pre>\n
Implemetaci\u00f3n de los conjuntos mediante listas no ordenadas sin duplicados<\/h3>\n
\r\nimport qualified Conjunto\r\nimport Data.List\r\n\r\n-- Conjuntos como listas no ordenadas sin repeticiones:\r\nnewtype Conj a = Cj [a]\r\n\r\n-- Escritura de los conjuntos.\r\ninstance (Show a) => Show (Conj a) where\r\n    showsPrec _ (Cj s) cad = showConj s cad\r\n\r\nshowConj []     cad = showString \"{}\" cad\r\nshowConj (x:xs) cad = showChar '{' (shows x (showl xs cad))\r\n     where showl []     cad = showChar '}' cad\r\n           showl (x:xs) cad = showChar ',' (shows x (showl xs cad))\r\n\r\n-- Ejemplo de conjunto:\r\n--    > c1\r\n--    {7,5,3,2,1,9,0}\r\nc1 = foldr agregaConj conjuntoVacio [2,5,1,3,7,5,3,2,1,9,0]\r\n\r\n-- conjuntoVacio es el conjunto vac\u00edo. Por ejemplo,\r\n--    > conjuntoVacio\r\n--    {}\r\nconjuntoVacio = Cj []\r\n\r\n-- (esConjuntoVacio c) se verifica si c es el conjunto vac\u00edo. Por\r\n-- ejemplo, \r\n--    esConjuntoVacio c1             ==  False\r\n--    esConjuntoVacio conjuntoVacio  ==  True\r\nesConjuntoVacio (Cj []) = True\r\nesConjuntoVacio _       = False\r\n\r\n-- (enConj x c) se verifica si x pertenece al conjunto c. Por ejemplo, \r\n--    c1           ==  {2,5,1,3,7,5,3,2,1,9,0}\r\n--    enConj 3 c1  ==  True\r\n--    enConj 4 c1  ==  False\r\nenConj x (Cj xs) = elem x xs\r\n\r\n-- (agregaConj x c) es el conjunto obtenido a\u00f1adi\u00e9ndole el elemento x al\r\n-- conjunto c. Por ejemplo,\r\n--    c1               ==  {7,5,3,2,1,9,0}\r\n--    agregaConj 5 c1  ==  {7,5,3,2,1,9,0}\r\n--    agregaConj 4 c1  ==  {4,7,5,3,2,1,9,0}\r\nagregaConj x s@(Cj xs) | enConj x s = s\r\n                       | otherwise  = Cj (x:xs)\r\n\r\n-- (eliminaConj x c) es el conjunto obtenido eliminando el elemento x\r\n-- del conjunto c. Por ejemplo,\r\n--    c1                ==  {7,5,3,2,1,9,0}\r\n--    eliminaConj 3 c1  ==  {7,5,2,1,9,0}\r\neliminaConj x (Cj s) = Cj (delete x s)\r\n<\/pre>\n
ConjuntosOrd.hs<\/i>: TAD de los conjuntos ordenados<\/h3>\n
\r\nmodule ConjuntoOrd\r\n    (Conj,conjuntoVacio,esConjuntoVacio,enConj,agregaConj,eliminaConj) where\r\n\r\n-- (Conj a) es el tipo de los conjunto cuyos elementos son del tipo a.\r\ndata Conj a = Undefined\r\n\r\n-- conjuntoVacio es el conjunto vac\u00edo.\r\nconjuntoVacio :: Conj a                         \r\nconjuntoVacio = undefined  \r\n\r\n-- (esConjuntoVacio c) se verifica si c es el conjunto vac\u00edo.\r\nesConjuntoVacio :: Conj a -> Bool                \r\nesConjuntoVacio = undefined \r\n\r\n-- (enConj x c) se verifica si x pertenece al conjunto c.\r\nenConj :: Ord a => a -> Conj a -> Bool \r\nenConj = undefined\r\n\r\n-- (agregaConj x c) es el conjunto obtenido a\u00f1adi\u00e9ndole el elemento x al\r\n-- conjunto c.\r\nagregaConj :: Ord a => a -> Conj a -> Conj a\r\nagregaConj = undefined\r\n\r\n-- (eliminaConj x c) es el conjunto obtenido eliminando el elemento x\r\n-- del conjunto c.\r\neliminaConj :: Ord a => a -> Conj a -> Conj a\r\neliminaConj = undefined\r\n<\/pre>\n
Implementaci\u00f3n de los conjuntos ordenados mediante listas ordenadas sin duplicados<\/h3>\n
\r\nimport qualified ConjuntoOrd\r\nimport Data.List\r\n\r\n-- Conjuntos como listas ordenadas sin repeticiones:\r\nnewtype Conj a = Cj [a]\r\n\r\n-- Escritura de los conjuntos.\r\ninstance (Show a) => Show (Conj a) where\r\n    showsPrec _ (Cj s) cad = showConj s cad\r\n\r\nshowConj []     cad = showString \"{}\" cad\r\nshowConj (x:xs) cad = showChar '{' (shows x (showl xs cad))\r\n     where showl []     cad = showChar '}' cad\r\n           showl (x:xs) cad = showChar ',' (shows x (showl xs cad))\r\n\r\n-- Ejemplo de conjunto:\r\n--    > c1\r\n--    {0,1,2,3,5,7,9}\r\nc1 = foldr agregaConj conjuntoVacio [2,5,1,3,7,5,3,2,1,9,0]\r\n\r\n-- conjuntoVacio es el conjunto vac\u00edo. Por ejemplo,\r\n--    > conjuntoVacio\r\n--    {}\r\nconjuntoVacio = Cj []\r\n\r\n-- (esConjuntoVacio c) se verifica si c es el conjunto vac\u00edo. Por\r\n-- ejemplo, \r\n--    esConjuntoVacio c1             ==  False\r\n--    esConjuntoVacio conjuntoVacio  ==  True\r\nesConjuntoVacio (Cj []) = True\r\nesConjuntoVacio _       = False\r\n\r\n-- (enConj x c) se verifica si x pertenece al conjunto c. Por ejemplo, \r\n--    c1           ==  {0,1,2,3,5,7,9}\r\n--    enConj 3 c1  ==  True\r\n--    enConj 4 c1  ==  False\r\nenConj x (Cj s) = elem x (takeWhile (<= x) s)\r\n\r\n-- (agregaConj x c) es el conjunto obtenido a\u00f1adi\u00e9ndole el elemento x al\r\n-- conjunto c. Por ejemplo,\r\n--    c1               ==  {0,1,2,3,5,7,9}\r\n--    agregaConj 5 c1  ==  {0,1,2,3,5,7,9}\r\n--    agregaConj 4 c1  ==  {0,1,2,3,4,5,7,9}\r\nagregaConj x (Cj s) = Cj (agrega x s)\r\n    where agrega x []                    = [x]                \r\n          agrega x s@(y:ys) | (x>y)      = y : (agrega x ys)\r\n                            | (xy)     = y : (elimina x ys)\r\n                             | (x\n
ConjuntoInt.hs<\/i>: TAD de los conjuntos de n\u00fameros enteros<\/h3>\n
\r\nmodule ConjuntoInt \r\n    (Conj,conjuntoVacio,esConjuntoVacio,enConj,agregaConj,eliminaConj) where\r\n\r\n-- Conj es el tipo de los conjunto cuyos elementos son n\u00fameros enteros.\r\ndata Conj = Undefined\r\n\r\n-- conjuntoVacio es el conjunto vac\u00edo.\r\nconjuntoVacio :: Conj        \r\nconjuntoVacio = undefined  \r\n\r\n-- (esConjuntoVacio c) se verifica si c es el conjunto vac\u00edo.\r\nesConjuntoVacio :: Conj -> Bool            \r\nesConjuntoVacio = undefined \r\n\r\n-- (enConj x c) se verifica si x pertenece al conjunto c.\r\nenConj :: Int -> Conj -> Bool\r\nenConj = undefined\r\n\r\n-- (agregaConj x c) es el conjunto obtenido a\u00f1adi\u00e9ndole el elemento x al\r\n-- conjunto c. \r\nagregaConj :: Int -> Conj -> Conj \r\nagregaConj = undefined\r\n\r\n-- (eliminaConj x c) es el conjunto obtenido eliminando el elemento x\r\n-- del conjunto c.\r\neliminaConj :: Int -> Conj -> Conj \r\neliminaConj = undefined\r\n<\/pre>\n
Implementaci\u00f3n de los conjuntos de n\u00fameros naturales mediante n\u00fameros binarios<\/h3>\n
\r\n-- Los conjuntos que s\u00f3lo contiene n\u00fameros (de tipo Int) entre 0 y n-1,\r\n-- se pueden representar como n\u00fameros binarios con n bits donde el bit i \r\n-- (0 <= i < n) es 1 syss el n\u00famero i pertenece al conjunto. Por\r\n-- ejemplo, \r\n--                       43210 \r\n--    {3,4}     mediante 11000 en decimal es 24 \r\n--    {1,2,3,4} mediante 11110 en decimal es 30\r\n--    {1,2,4}   mediante 10110 en decimal es 22\r\n\r\nimport qualified ConjuntoInt\r\n\r\n-- Conjuntos de n\u00fameros enteros como n\u00fameros binarios:\r\nnewtype Conj = Cj Int\r\n\r\n-- Escritura de conjuntos.\r\ninstance Show Conj where\r\n    showsPrec _ s cad = showConj (conj2Lista s) cad\r\n\r\n-- (conj2Lista c) es la lista de los elementos del conjunto c. Por\r\n-- ejemplo, \r\n--   conj2Lista (Cj 24)  ==  [3,4]\r\n--   conj2Lista (Cj 30)  ==  [1,2,3,4]\r\n--   conj2Lista (Cj 22)  ==  [1,2,4]\r\nconj2Lista (Cj s) = c2l s 0\r\n    where c2l 0 _             = []\r\n          c2l n i | odd n     = i : c2l (n `div` 2) (i+1)\r\n                  | otherwise = c2l (n `div` 2) (i+1)\r\n\r\nshowConj []     cad = showString \"{}\" cad\r\nshowConj (x:xs) cad = showChar '{' (shows x (showl xs cad))\r\n     where showl []     cad = showChar '}' cad\r\n           showl (x:xs) cad = showChar ',' (shows x (showl xs cad))\r\n\r\n-- maxConj es el m\u00e1ximo n\u00famero que puede pertenecer al conjunto. Depende\r\n-- de la implementaci\u00f3n de Haskell. Por ejemplo,\r\n--    maxConj  ==  29\r\nmaxConj = truncate (logBase 2 (fromIntegral (maxBound::Int))) - 1\r\n\r\n-- Ejemplo de conjunto:\r\n--    > c1\r\n--    {0,1,2,3,5,7,9}\r\nc1 = foldr agregaConj conjuntoVacio [2,5,1,3,7,5,3,2,1,9,0]\r\n\r\n-- conjuntoVacio es el conjunto vac\u00edo. Por ejemplo,\r\n--    > conjuntoVacio\r\n--    {}\r\nconjuntoVacio = Cj 0\r\n\r\n-- (esConjuntoVacio c) se verifica si c es el conjunto vac\u00edo. Por\r\n-- ejemplo, \r\n--    esConjuntoVacio c1             ==  False\r\n--    esConjuntoVacio conjuntoVacio  ==  True\r\nesConjuntoVacio (Cj n) = n==0\r\n\r\n-- (enConj x c) se verifica si x pertenece al conjunto c. Por ejemplo, \r\n--    c1           ==  {0,1,2,3,5,7,9}\r\n--    enConj 3 c1  ==  True\r\n--    enConj 4 c1  ==  False\r\nenConj i (Cj s)\r\n    | (i>=0) && (i<=maxConj) = odd (s `div` (2^i))\r\n    | otherwise              = error (\"enConj: elemento ilegal =\" ++ show i)\r\n\r\n-- (agregaConj x c) es el conjunto obtenido a\u00f1adi\u00e9ndole el elemento x al\r\n-- conjunto c. Por ejemplo,\r\n--    c1               ==  {0,1,2,3,5,7,9}\r\n--    agregaConj 5 c1  ==  {0,1,2,3,5,7,9}\r\n--    agregaConj 4 c1  ==  {0,1,2,3,4,5,7,9}\r\nagregaConj i (Cj s)\r\n    | (i>=0) && (i<=maxConj) = Cj (d'*e+m)\r\n    | otherwise              = error (\"agregaConj: elemento ilegal =\" ++\r\n                                      show i)\r\n    where (d,m) = divMod s e\r\n          e     = 2^i\r\n          d'    = if odd d then d else d+1\r\n\r\n-- (eliminaConj x c) es el conjunto obtenido eliminando el elemento x\r\n-- del conjunto c. Por ejemplo,\r\n--    c1                ==  {0,1,2,3,5,7,9}\r\n--    eliminaConj 3 c1  ==  {0,1,2,5,7,9}\r\neliminaConj i (Cj s)\r\n    | (i>=0) && (i<=maxConj) = Cj (d'*e+m)\r\n    | otherwise              = error (\"eliminaConj: elemento ilegal =\" ++\r\n                                      show i)\r\n    where (d,m) = divMod s e\r\n          e     = 2^i\r\n          d'    = if odd d then d-1 else d\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
En este art\u00edculo contin\u00fao la serie dedicada a los tipos de datos abstractos (TAD) en Haskell. El objetivo de la serie es la elaboraci\u00f3n del tema de TAD del curso de Inform\u00e1tica del Grado en Matem\u00e1ticas. En el art\u00edculo anterior present\u00e9 el TAD de polinomios. En \u00e9ste voy a presentar los TAD de conjuntos y…<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"closed","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":[5],"tags":[131,270,124],"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\/692"}],"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=692"}],"version-history":[{"count":5,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/692\/revisions"}],"predecessor-version":[{"id":1029,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/692\/revisions\/1029"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=692"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=692"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=692"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}