I1M2013: El tipo abstracto de datos de los conjuntos en Haskell

En la clase de hoy de Informática de 1º del Grado en Matemáticas 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.

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

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 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)

Implementació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)

Implementación de los conjuntos 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

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

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

Implementación de los conjuntos mediante listas ordenadas sin duplicados

Se puede imprimir o compartir con