El tipo abstracto de datos de los conjuntos en Haskell

En este artículo continúo la serie dedicada a los tipos de datos abstractos (TAD) en Haskell. El objetivo de la serie es la elaboración del tema de TAD del curso de Informática del Grado en Matemáticas.

En el artículo anterior presenté el TAD de polinomios. En éste voy a presentar los TAD de conjuntos y sus implementaciones en Haskell.

Al igual que hice en el de polinomio usaré módulos, importaciones cualificadas, indefiniciones y funciones de escritura para conseguir la abstracción e independencia de los resultados de las implementaciones.

El contenido del resto del artículo es el siguiente: el TAD de los conjuntos y su implementación mediante listas no ordenadas con y sin duplicados, el TAD de los conjuntos ordenados y su implementación mediante listas ordenadas sin duplicados, el TAD de los conjuntos de números naturales y su implementación
mediante números binarios.

Conjuntos.hs: El TAD de los conjuntos

module Conjunto
    (Conj,conjuntoVacio,esConjuntoVacio,enConj,agregaConj,eliminaConj) where

-- (Conj a) es el tipo de los conjunto cuyos elementos son del tipo a.
data Conj a = Undefined

-- conjuntoVacio es el conjunto vacío.
conjuntoVacio :: Conj a                         
conjuntoVacio = undefined  

-- (esConjuntoVacio c) se verifica si c es el conjunto vacío.
esConjuntoVacio :: Conj a -> Bool                
esConjuntoVacio = undefined 

-- (enConj x c) se verifica si x pertenece al conjunto c.
enConj :: Eq a => a -> Conj a -> Bool 
enConj = undefined

-- (agregaConj x c) es el conjunto obtenido añadiéndole el elemento x al
-- conjunto c. 
agregaConj :: Eq a => a -> Conj a -> Conj a
agregaConj = undefined

-- (eliminaConj x c) es el conjunto obtenido eliminando el elemento x
-- del conjunto c.
eliminaConj :: Eq a => a -> Conj a -> Conj a
eliminaConj = undefined

module Conjunto

(Conj,conjuntoVacio,esConjuntoVacio,enConj,agregaConj,eliminaConj) where

-- (Conj a) es el tipo de los conjunto cuyos elementos son del tipo a.

data Conj a = Undefined

-- conjuntoVacio es el conjunto vacío.

conjuntoVacio :: Conj a

conjuntoVacio = undefined

-- (esConjuntoVacio c) se verifica si c es el conjunto vacío.

esConjuntoVacio :: Conj a -> Bool

esConjuntoVacio = undefined

-- (enConj x c) se verifica si x pertenece al conjunto c.

enConj :: Eq a => a -> Conj a -> Bool

enConj = undefined

-- (agregaConj x c) es el conjunto obtenido añadiéndole el elemento x al

-- conjunto c.

agregaConj :: Eq a => a -> Conj a -> Conj a

agregaConj = undefined

-- (eliminaConj x c) es el conjunto obtenido eliminando el elemento x

-- del conjunto c.

eliminaConj :: Eq a => a -> Conj a -> Conj a

eliminaConj = undefined

Implemetación de los conjuntos mediante listas no ordenadas con duplicados

import qualified Conjunto
import Data.List

-- Conjuntos como listas no ordenadas con repeticiones:
newtype Conj a = Cj [a]

-- Escritura de los conjuntos.
instance (Show a) => Show (Conj a) where
    showsPrec _ (Cj s) cad = showConj s cad

showConj []     cad = showString "{}" cad
showConj (x:xs) cad = showChar '{' (shows x (showl xs cad))
     where showl []     cad = showChar '}' cad
           showl (x:xs) cad = showChar ',' (shows x (showl xs cad))

-- Ejemplo de conjunto:
--    > c1
--    {2,5,1,3,7,5,3,2,1,9,0}
c1 = foldr agregaConj conjuntoVacio [2,5,1,3,7,5,3,2,1,9,0]

-- conjuntoVacio es el conjunto vacío. Por ejemplo,
--    > conjuntoVacio
--    {}
conjuntoVacio = Cj []

-- (esConjuntoVacio c) se verifica si c es el conjunto vacío. Por
-- ejemplo, 
--    esConjuntoVacio c1             ==  False
--    esConjuntoVacio conjuntoVacio  ==  True
esConjuntoVacio (Cj []) = True
esConjuntoVacio _       = False

-- (enConj x c) se verifica si x pertenece al conjunto c. Por ejemplo, 
--    c1           ==  {2,5,1,3,7,5,3,2,1,9,0}
--    enConj 3 c1  ==  True
--    enConj 4 c1  ==  False
enConj x (Cj xs) = elem x xs

-- (agregaConj x c) es el conjunto obtenido añadiéndole el elemento x al
-- conjunto c. Por ejemplo,
--    c1               ==  {2,5,1,3,7,5,3,2,1,9,0}
--    agregaConj 5 c1  ==  {5,2,5,1,3,7,5,3,2,1,9,0}
agregaConj x (Cj a) = Cj (x:a)

-- (eliminaConj x c) es el conjunto obtenido eliminando el elemento x
-- del conjunto c. Por ejemplo,
--    c1                ==  {2,5,1,3,7,5,3,2,1,9,0}
--    eliminaConj 3 c1  ==  {2,5,1,7,5,2,1,9,0}
eliminaConj x (Cj xs) = Cj (filter (/= x) xs)

import qualified Conjunto

import Data.List

-- Conjuntos como listas no ordenadas con repeticiones:

newtype Conj a = Cj [a]

-- Escritura de los conjuntos.

instance (Show a) => Show (Conj a) where

showsPrec _ (Cj s) cad = showConj s cad

showConj [] cad = showString "{}" cad

showConj (x:xs) cad = showChar '{' (shows x (showl xs cad))

where showl [] cad = showChar '}' cad

showl (x:xs) cad = showChar ',' (shows x (showl xs cad))

-- Ejemplo de conjunto:

-- > c1

-- {2,5,1,3,7,5,3,2,1,9,0}

c1 = foldr agregaConj conjuntoVacio [2,5,1,3,7,5,3,2,1,9,0]

-- conjuntoVacio es el conjunto vacío. Por ejemplo,

-- > conjuntoVacio

-- {}

conjuntoVacio = Cj []

-- (esConjuntoVacio c) se verifica si c es el conjunto vacío. Por

-- ejemplo,

-- esConjuntoVacio c1 == False

-- esConjuntoVacio conjuntoVacio == True

esConjuntoVacio (Cj []) = True

esConjuntoVacio _ = False

-- (enConj x c) se verifica si x pertenece al conjunto c. Por ejemplo,

-- c1 == {2,5,1,3,7,5,3,2,1,9,0}

-- enConj 3 c1 == True

-- enConj 4 c1 == False

enConj x (Cj xs) = elem x xs

-- (agregaConj x c) es el conjunto obtenido añadiéndole el elemento x al

-- conjunto c. Por ejemplo,

-- c1 == {2,5,1,3,7,5,3,2,1,9,0}

-- agregaConj 5 c1 == {5,2,5,1,3,7,5,3,2,1,9,0}

agregaConj x (Cj a) = Cj (x:a)

-- (eliminaConj x c) es el conjunto obtenido eliminando el elemento x

-- del conjunto c. Por ejemplo,

-- c1 == {2,5,1,3,7,5,3,2,1,9,0}

-- eliminaConj 3 c1 == {2,5,1,7,5,2,1,9,0}

eliminaConj x (Cj xs) = Cj (filter (/= x) xs)

Implemetación de los conjuntos mediante listas no ordenadas sin duplicados

import qualified Conjunto
import Data.List

-- Conjuntos como listas no ordenadas sin repeticiones:
newtype Conj a = Cj [a]

-- Escritura de los conjuntos.
instance (Show a) => Show (Conj a) where
    showsPrec _ (Cj s) cad = showConj s cad

showConj []     cad = showString "{}" cad
showConj (x:xs) cad = showChar '{' (shows x (showl xs cad))
     where showl []     cad = showChar '}' cad
           showl (x:xs) cad = showChar ',' (shows x (showl xs cad))

-- Ejemplo de conjunto:
--    > c1
--    {7,5,3,2,1,9,0}
c1 = foldr agregaConj conjuntoVacio [2,5,1,3,7,5,3,2,1,9,0]

-- conjuntoVacio es el conjunto vacío. Por ejemplo,
--    > conjuntoVacio
--    {}
conjuntoVacio = Cj []

-- (esConjuntoVacio c) se verifica si c es el conjunto vacío. Por
-- ejemplo, 
--    esConjuntoVacio c1             ==  False
--    esConjuntoVacio conjuntoVacio  ==  True
esConjuntoVacio (Cj []) = True
esConjuntoVacio _       = False

-- (enConj x c) se verifica si x pertenece al conjunto c. Por ejemplo, 
--    c1           ==  {2,5,1,3,7,5,3,2,1,9,0}
--    enConj 3 c1  ==  True
--    enConj 4 c1  ==  False
enConj x (Cj xs) = elem x xs

-- (agregaConj x c) es el conjunto obtenido añadiéndole el elemento x al
-- conjunto c. Por ejemplo,
--    c1               ==  {7,5,3,2,1,9,0}
--    agregaConj 5 c1  ==  {7,5,3,2,1,9,0}
--    agregaConj 4 c1  ==  {4,7,5,3,2,1,9,0}
agregaConj x s@(Cj xs) | enConj x s = s
                       | otherwise  = Cj (x:xs)

-- (eliminaConj x c) es el conjunto obtenido eliminando el elemento x
-- del conjunto c. Por ejemplo,
--    c1                ==  {7,5,3,2,1,9,0}
--    eliminaConj 3 c1  ==  {7,5,2,1,9,0}
eliminaConj x (Cj s) = Cj (delete x s)

import qualified Conjunto

import Data.List

-- Conjuntos como listas no ordenadas sin repeticiones:

newtype Conj a = Cj [a]

-- Escritura de los conjuntos.

instance (Show a) => Show (Conj a) where

showsPrec _ (Cj s) cad = showConj s cad

showConj [] cad = showString "{}" cad

showConj (x:xs) cad = showChar '{' (shows x (showl xs cad))

where showl [] cad = showChar '}' cad

showl (x:xs) cad = showChar ',' (shows x (showl xs cad))

-- Ejemplo de conjunto:

-- > c1

-- {7,5,3,2,1,9,0}

c1 = foldr agregaConj conjuntoVacio [2,5,1,3,7,5,3,2,1,9,0]

-- conjuntoVacio es el conjunto vacío. Por ejemplo,

-- > conjuntoVacio

-- {}

conjuntoVacio = Cj []

-- (esConjuntoVacio c) se verifica si c es el conjunto vacío. Por

-- ejemplo,

-- esConjuntoVacio c1 == False

-- esConjuntoVacio conjuntoVacio == True

esConjuntoVacio (Cj []) = True

esConjuntoVacio _ = False

-- (enConj x c) se verifica si x pertenece al conjunto c. Por ejemplo,

-- c1 == {2,5,1,3,7,5,3,2,1,9,0}

-- enConj 3 c1 == True

-- enConj 4 c1 == False

enConj x (Cj xs) = elem x xs

-- (agregaConj x c) es el conjunto obtenido añadiéndole el elemento x al

-- conjunto c. Por ejemplo,

-- c1 == {7,5,3,2,1,9,0}

-- agregaConj 5 c1 == {7,5,3,2,1,9,0}

-- agregaConj 4 c1 == {4,7,5,3,2,1,9,0}

agregaConj x s@(Cj xs) | enConj x s = s

| otherwise = Cj (x:xs)

-- (eliminaConj x c) es el conjunto obtenido eliminando el elemento x

-- del conjunto c. Por ejemplo,

-- c1 == {7,5,3,2,1,9,0}

-- eliminaConj 3 c1 == {7,5,2,1,9,0}

eliminaConj x (Cj s) = Cj (delete x s)

ConjuntosOrd.hs: TAD de los conjuntos ordenados

module ConjuntoOrd
    (Conj,conjuntoVacio,esConjuntoVacio,enConj,agregaConj,eliminaConj) where

-- (Conj a) es el tipo de los conjunto cuyos elementos son del tipo a.
data Conj a = Undefined

-- conjuntoVacio es el conjunto vacío.
conjuntoVacio :: Conj a                         
conjuntoVacio = undefined  

-- (esConjuntoVacio c) se verifica si c es el conjunto vacío.
esConjuntoVacio :: Conj a -> Bool                
esConjuntoVacio = undefined 

-- (enConj x c) se verifica si x pertenece al conjunto c.
enConj :: Ord a => a -> Conj a -> Bool 
enConj = undefined

-- (agregaConj x c) es el conjunto obtenido añadiéndole el elemento x al
-- conjunto c.
agregaConj :: Ord a => a -> Conj a -> Conj a
agregaConj = undefined

-- (eliminaConj x c) es el conjunto obtenido eliminando el elemento x
-- del conjunto c.
eliminaConj :: Ord a => a -> Conj a -> Conj a
eliminaConj = undefined

module ConjuntoOrd

(Conj,conjuntoVacio,esConjuntoVacio,enConj,agregaConj,eliminaConj) where

-- (Conj a) es el tipo de los conjunto cuyos elementos son del tipo a.

data Conj a = Undefined

-- conjuntoVacio es el conjunto vacío.

conjuntoVacio :: Conj a

conjuntoVacio = undefined

-- (esConjuntoVacio c) se verifica si c es el conjunto vacío.

esConjuntoVacio :: Conj a -> Bool

esConjuntoVacio = undefined

-- (enConj x c) se verifica si x pertenece al conjunto c.

enConj :: Ord a => a -> Conj a -> Bool

enConj = undefined

-- (agregaConj x c) es el conjunto obtenido añadiéndole el elemento x al

-- conjunto c.

agregaConj :: Ord a => a -> Conj a -> Conj a

agregaConj = undefined

-- (eliminaConj x c) es el conjunto obtenido eliminando el elemento x

-- del conjunto c.

eliminaConj :: Ord a => a -> Conj a -> Conj a

eliminaConj = undefined

Implementación de los conjuntos ordenados mediante listas ordenadas sin duplicados

import qualified ConjuntoOrd
import Data.List

-- Conjuntos como listas ordenadas sin repeticiones:
newtype Conj a = Cj [a]

-- Escritura de los conjuntos.
instance (Show a) => Show (Conj a) where
    showsPrec _ (Cj s) cad = showConj s cad

showConj []     cad = showString "{}" cad
showConj (x:xs) cad = showChar '{' (shows x (showl xs cad))
     where showl []     cad = showChar '}' cad
           showl (x:xs) cad = showChar ',' (shows x (showl xs cad))

-- Ejemplo de conjunto:
--    > c1
--    {0,1,2,3,5,7,9}
c1 = foldr agregaConj conjuntoVacio [2,5,1,3,7,5,3,2,1,9,0]

-- conjuntoVacio es el conjunto vacío. Por ejemplo,
--    > conjuntoVacio
--    {}
conjuntoVacio = Cj []

-- (esConjuntoVacio c) se verifica si c es el conjunto vacío. Por
-- ejemplo, 
--    esConjuntoVacio c1             ==  False
--    esConjuntoVacio conjuntoVacio  ==  True
esConjuntoVacio (Cj []) = True
esConjuntoVacio _       = False

-- (enConj x c) se verifica si x pertenece al conjunto c. Por ejemplo, 
--    c1           ==  {0,1,2,3,5,7,9}
--    enConj 3 c1  ==  True
--    enConj 4 c1  ==  False
enConj x (Cj s) = elem x (takeWhile (<= x) s)

-- (agregaConj x c) es el conjunto obtenido añadiéndole el elemento x al
-- conjunto c. Por ejemplo,
--    c1               ==  {0,1,2,3,5,7,9}
--    agregaConj 5 c1  ==  {0,1,2,3,5,7,9}
--    agregaConj 4 c1  ==  {0,1,2,3,4,5,7,9}
agregaConj x (Cj s) = Cj (agrega x s)
    where agrega x []                    = [x]                
          agrega x s@(y:ys) | (x>y)      = y : (agrega x ys)
                            | (x<y)      = x : s
                            | otherwise  = s

-- (eliminaConj x c) es el conjunto obtenido eliminando el elemento x
-- del conjunto c. Por ejemplo,
--    c1                ==  {0,1,2,3,5,7,9}
--    eliminaConj 3 c1  ==  {0,1,2,5,7,9}
eliminaConj x (Cj s) = Cj (elimina x s)
    where elimina x []                   = []
          elimina x s@(y:ys) | (x>y)     = y : (elimina x ys)
                             | (x<y)     = s
                             | otherwise = ys

import qualified ConjuntoOrd

import Data.List

-- Conjuntos como listas ordenadas sin repeticiones:

newtype Conj a = Cj [a]

-- Escritura de los conjuntos.

instance (Show a) => Show (Conj a) where

showsPrec _ (Cj s) cad = showConj s cad

showConj [] cad = showString "{}" cad

showConj (x:xs) cad = showChar '{' (shows x (showl xs cad))

where showl [] cad = showChar '}' cad

showl (x:xs) cad = showChar ',' (shows x (showl xs cad))

-- Ejemplo de conjunto:

-- > c1

-- {0,1,2,3,5,7,9}

c1 = foldr agregaConj conjuntoVacio [2,5,1,3,7,5,3,2,1,9,0]

-- conjuntoVacio es el conjunto vacío. Por ejemplo,

-- > conjuntoVacio

-- {}

conjuntoVacio = Cj []

-- (esConjuntoVacio c) se verifica si c es el conjunto vacío. Por

-- ejemplo,

-- esConjuntoVacio c1 == False

-- esConjuntoVacio conjuntoVacio == True

esConjuntoVacio (Cj []) = True

esConjuntoVacio _ = False

-- (enConj x c) se verifica si x pertenece al conjunto c. Por ejemplo,

-- c1 == {0,1,2,3,5,7,9}

-- enConj 3 c1 == True

-- enConj 4 c1 == False

enConj x (Cj s) = elem x (takeWhile (<= x) s)

-- (agregaConj x c) es el conjunto obtenido añadiéndole el elemento x al

-- conjunto c. Por ejemplo,

-- c1 == {0,1,2,3,5,7,9}

-- agregaConj 5 c1 == {0,1,2,3,5,7,9}

-- agregaConj 4 c1 == {0,1,2,3,4,5,7,9}

agregaConj x (Cj s) = Cj (agrega x s)

where agrega x [] = [x]

agrega x s@(y:ys) | (x>y) = y : (agrega x ys)

| (x<y) = x : s

| otherwise = s

-- (eliminaConj x c) es el conjunto obtenido eliminando el elemento x

-- del conjunto c. Por ejemplo,

-- c1 == {0,1,2,3,5,7,9}

-- eliminaConj 3 c1 == {0,1,2,5,7,9}

eliminaConj x (Cj s) = Cj (elimina x s)

where elimina x [] = []

elimina x s@(y:ys) | (x>y) = y : (elimina x ys)

| (x<y) = s

| otherwise = ys

ConjuntoInt.hs: TAD de los conjuntos de números enteros

module ConjuntoInt 
    (Conj,conjuntoVacio,esConjuntoVacio,enConj,agregaConj,eliminaConj) where

-- Conj es el tipo de los conjunto cuyos elementos son números enteros.
data Conj = Undefined

-- conjuntoVacio es el conjunto vacío.
conjuntoVacio :: Conj        
conjuntoVacio = undefined  

-- (esConjuntoVacio c) se verifica si c es el conjunto vacío.
esConjuntoVacio :: Conj -> Bool            
esConjuntoVacio = undefined 

-- (enConj x c) se verifica si x pertenece al conjunto c.
enConj :: Int -> Conj -> Bool
enConj = undefined

-- (agregaConj x c) es el conjunto obtenido añadiéndole el elemento x al
-- conjunto c. 
agregaConj :: Int -> Conj -> Conj 
agregaConj = undefined

-- (eliminaConj x c) es el conjunto obtenido eliminando el elemento x
-- del conjunto c.
eliminaConj :: Int -> Conj -> Conj 
eliminaConj = undefined

module ConjuntoInt

(Conj,conjuntoVacio,esConjuntoVacio,enConj,agregaConj,eliminaConj) where

-- Conj es el tipo de los conjunto cuyos elementos son números enteros.

data Conj = Undefined

-- conjuntoVacio es el conjunto vacío.

conjuntoVacio :: Conj

conjuntoVacio = undefined

-- (esConjuntoVacio c) se verifica si c es el conjunto vacío.

esConjuntoVacio :: Conj -> Bool

esConjuntoVacio = undefined

-- (enConj x c) se verifica si x pertenece al conjunto c.

enConj :: Int -> Conj -> Bool

enConj = undefined

-- (agregaConj x c) es el conjunto obtenido añadiéndole el elemento x al

-- conjunto c.

agregaConj :: Int -> Conj -> Conj

agregaConj = undefined

-- (eliminaConj x c) es el conjunto obtenido eliminando el elemento x

-- del conjunto c.

eliminaConj :: Int -> Conj -> Conj

eliminaConj = undefined

Implementación de los conjuntos de números naturales mediante números binarios

-- Los conjuntos que sólo contiene números (de tipo Int) entre 0 y n-1,
-- se pueden representar como números binarios con n bits donde el bit i 
-- (0 <= i < n) es 1 syss el número i pertenece al conjunto. Por
-- ejemplo, 
--                       43210 
--    {3,4}     mediante 11000 en decimal es 24 
--    {1,2,3,4} mediante 11110 en decimal es 30
--    {1,2,4}   mediante 10110 en decimal es 22

import qualified ConjuntoInt

-- Conjuntos de números enteros como números binarios:
newtype Conj = Cj Int

-- Escritura de conjuntos.
instance Show Conj where
    showsPrec _ s cad = showConj (conj2Lista s) cad

-- (conj2Lista c) es la lista de los elementos del conjunto c. Por
-- ejemplo, 
--   conj2Lista (Cj 24)  ==  [3,4]
--   conj2Lista (Cj 30)  ==  [1,2,3,4]
--   conj2Lista (Cj 22)  ==  [1,2,4]
conj2Lista (Cj s) = c2l s 0
    where c2l 0 _             = []
          c2l n i | odd n     = i : c2l (n `div` 2) (i+1)
                  | otherwise = c2l (n `div` 2) (i+1)

showConj []     cad = showString "{}" cad
showConj (x:xs) cad = showChar '{' (shows x (showl xs cad))
     where showl []     cad = showChar '}' cad
           showl (x:xs) cad = showChar ',' (shows x (showl xs cad))

-- maxConj es el máximo número que puede pertenecer al conjunto. Depende
-- de la implementación de Haskell. Por ejemplo,
--    maxConj  ==  29
maxConj = truncate (logBase 2 (fromIntegral (maxBound::Int))) - 1

-- Ejemplo de conjunto:
--    > c1
--    {0,1,2,3,5,7,9}
c1 = foldr agregaConj conjuntoVacio [2,5,1,3,7,5,3,2,1,9,0]

-- conjuntoVacio es el conjunto vacío. Por ejemplo,
--    > conjuntoVacio
--    {}
conjuntoVacio = Cj 0

-- (esConjuntoVacio c) se verifica si c es el conjunto vacío. Por
-- ejemplo, 
--    esConjuntoVacio c1             ==  False
--    esConjuntoVacio conjuntoVacio  ==  True
esConjuntoVacio (Cj n) = n==0

-- (enConj x c) se verifica si x pertenece al conjunto c. Por ejemplo, 
--    c1           ==  {0,1,2,3,5,7,9}
--    enConj 3 c1  ==  True
--    enConj 4 c1  ==  False
enConj i (Cj s)
    | (i>=0) && (i<=maxConj) = odd (s `div` (2^i))
    | otherwise              = error ("enConj: elemento ilegal =" ++ show i)

-- (agregaConj x c) es el conjunto obtenido añadiéndole el elemento x al
-- conjunto c. Por ejemplo,
--    c1               ==  {0,1,2,3,5,7,9}
--    agregaConj 5 c1  ==  {0,1,2,3,5,7,9}
--    agregaConj 4 c1  ==  {0,1,2,3,4,5,7,9}
agregaConj i (Cj s)
    | (i>=0) && (i<=maxConj) = Cj (d'*e+m)
    | otherwise              = error ("agregaConj: elemento ilegal =" ++
                                      show i)
    where (d,m) = divMod s e
          e     = 2^i
          d'    = if odd d then d else d+1

-- (eliminaConj x c) es el conjunto obtenido eliminando el elemento x
-- del conjunto c. Por ejemplo,
--    c1                ==  {0,1,2,3,5,7,9}
--    eliminaConj 3 c1  ==  {0,1,2,5,7,9}
eliminaConj i (Cj s)
    | (i>=0) && (i<=maxConj) = Cj (d'*e+m)
    | otherwise              = error ("eliminaConj: elemento ilegal =" ++
                                      show i)
    where (d,m) = divMod s e
          e     = 2^i
          d'    = if odd d then d-1 else d

-- Los conjuntos que sólo contiene números (de tipo Int) entre 0 y n-1,

-- se pueden representar como números binarios con n bits donde el bit i

-- (0 <= i < n) es 1 syss el número i pertenece al conjunto. Por

-- ejemplo,

-- 43210

-- {3,4} mediante 11000 en decimal es 24

-- {1,2,3,4} mediante 11110 en decimal es 30

-- {1,2,4} mediante 10110 en decimal es 22

import qualified ConjuntoInt

-- Conjuntos de números enteros como números binarios:

newtype Conj = Cj Int

-- Escritura de conjuntos.

instance Show Conj where

showsPrec _ s cad = showConj (conj2Lista s) cad

-- (conj2Lista c) es la lista de los elementos del conjunto c. Por

-- ejemplo,

-- conj2Lista (Cj 24) == [3,4]

-- conj2Lista (Cj 30) == [1,2,3,4]

-- conj2Lista (Cj 22) == [1,2,4]

conj2Lista (Cj s) = c2l s 0

where c2l 0 _ = []

c2l n i | odd n = i : c2l (n `div` 2) (i+1)

| otherwise = c2l (n `div` 2) (i+1)

showConj [] cad = showString "{}" cad

showConj (x:xs) cad = showChar '{' (shows x (showl xs cad))

where showl [] cad = showChar '}' cad

showl (x:xs) cad = showChar ',' (shows x (showl xs cad))

-- maxConj es el máximo número que puede pertenecer al conjunto. Depende

-- de la implementación de Haskell. Por ejemplo,

-- maxConj == 29

maxConj = truncate (logBase 2 (fromIntegral (maxBound::Int))) - 1

-- Ejemplo de conjunto:

-- > c1

-- {0,1,2,3,5,7,9}

c1 = foldr agregaConj conjuntoVacio [2,5,1,3,7,5,3,2,1,9,0]

-- conjuntoVacio es el conjunto vacío. Por ejemplo,

-- > conjuntoVacio

-- {}

conjuntoVacio = Cj 0

-- (esConjuntoVacio c) se verifica si c es el conjunto vacío. Por

-- ejemplo,

-- esConjuntoVacio c1 == False

-- esConjuntoVacio conjuntoVacio == True

esConjuntoVacio (Cj n) = n==0

-- (enConj x c) se verifica si x pertenece al conjunto c. Por ejemplo,

-- c1 == {0,1,2,3,5,7,9}

-- enConj 3 c1 == True

-- enConj 4 c1 == False

enConj i (Cj s)

| (i>=0) && (i<=maxConj) = odd (s `div` (2^i))

| otherwise = error ("enConj: elemento ilegal =" ++ show i)

-- (agregaConj x c) es el conjunto obtenido añadiéndole el elemento x al

-- conjunto c. Por ejemplo,

-- c1 == {0,1,2,3,5,7,9}

-- agregaConj 5 c1 == {0,1,2,3,5,7,9}

-- agregaConj 4 c1 == {0,1,2,3,4,5,7,9}

agregaConj i (Cj s)

| (i>=0) && (i<=maxConj) = Cj (d'*e+m)

| otherwise = error ("agregaConj: elemento ilegal =" ++

show i)

where (d,m) = divMod s e

e = 2^i

d' = if odd d then d else d+1

-- (eliminaConj x c) es el conjunto obtenido eliminando el elemento x

-- del conjunto c. Por ejemplo,

-- c1 == {0,1,2,3,5,7,9}

-- eliminaConj 3 c1 == {0,1,2,5,7,9}

eliminaConj i (Cj s)

| (i>=0) && (i<=maxConj) = Cj (d'*e+m)

| otherwise = error ("eliminaConj: elemento ilegal =" ++

show i)

where (d,m) = divMod s e

e = 2^i

d' = if odd d then d-1 else d

Conjuntos.hs: El TAD de los conjuntos

Implemetación de los conjuntos mediante listas no ordenadas con duplicados

Implemetación de los conjuntos mediante listas no ordenadas sin duplicados

ConjuntosOrd.hs: TAD de los conjuntos ordenados

Implementación de los conjuntos ordenados mediante listas ordenadas sin duplicados

ConjuntoInt.hs: TAD de los conjuntos de números enteros

Implementación de los conjuntos de números naturales mediante números binarios

Se puede imprimir o compartir con