1 Introducción

• Los conjuntos permiten almacenar elementos en los que no importa el orden ni las repeticiones.

• En esta tema se presentan ejemplos de las funciones de la librería de conjuntos Data.Set 0.6.2.1.

• En los ejemplos se supone que se ha importado la siguiente librería

ghci> import Data.Set as S

• Debido a que Data.Set exporta funciones que colisionan con las de Prelude y Data.List, se suele importar de forma cualificada.

import qualified Data.Set as S

2 El tipo de los conjuntos

• (Set a) es el tipo de los conjuntos con elementos de tipo a. Por ejemplo,

ghci> c1 = fromList [3,2,5,3]
ghci> :type c1
c1 :: (Ord a, Num a) => Set a
ghci> c1
fromList [2,3,5]
ghci> c2 = fromList [2,5,2,3]
ghci> c1 == c2
True

3 Resumen de funciones básicas

• empty es el conjunto vacío. Por ejemplo,

ghci> empty
fromList []

• (insert x c) es el conjunto obtenido insertando el elemento x en el conjunto c. Por ejemplo,

ghci> insert 7 (fromList [3,2,5])
fromList [2,3,5,7]
ghci> insert 2 (fromList [3,2,5])
fromList [2,3,5]

• (delete x c) es el conjunto obtenido eliminando el elemento x del conjunto c. Por ejemplo,

ghci> delete 3 (fromList [3,2,5,3,4])
fromList [2,4,5]
ghci> delete 7 (fromList [3,2,5,3,4])
fromList [2,3,4,5]

• (member x c) se verifica si x es un elemento del conjunto c. Por ejemplo,

ghci> member 5 (fromList [3,2,5])
True
ghci> member 7 (fromList [3,2,5])
False

• (null c) se verifica si c es el conjunto vacío. Por ejemplo,

ghci> S.null (fromList [])
True
ghci> S.null (fromList [5,2])
False

4 Otras funciones sobre conjuntos

4.1 De listas a conjuntos

• (fromList xs) es el conjunto cuyos elementos son los de la lista xs. Por ejemplo,

ghci> fromList [3,2,5,2,15]
fromList [2,3,5,15]
ghci> :t it
it :: (Ord a, Num a) => Set a

4.2 De conjuntos a listas

• (elems c) es la lista de los elementos del conjunto c ordenados crecientemente. Por ejemplo,

ghci> elems (fromList [3,2,5,2,1,5])
[1,2,3,5]

• (toList c) es la lista de los elementos del conjunto c ordenados crecientemente. Por ejemplo,

ghci> toList (fromList [3,2,5,2,1,5])
[1,2,3,5]

4.3 Operaciones y relaciones usuales

• (union cs c2) es la unión de los conjuntos c1 y c2. Por ejemplo,

ghci> union (fromList [3,2,5]) (fromList [2,7,5])
fromList [2,3,5,7]

• (intersection cs c2) es la intersecciṕn de los conjuntos c1 y c2. Por ejemplo,

ghci> intersection (fromList [3,2,5]) (fromList [2,7,5])
fromList [2,5]

• (difference c1 c2) es la diferencia de los conjuntos c1 y c2. Por ejemplo,

ghci> difference (fromList [2,5,3]) (fromList [1,4,5])
fromList [2,3]

• (c1 \\ c2) es la diferencia de los conjuntos c1 y c2. Por ejemplo,

ghci> fromList [2,5,3] \\ fromList [1,4,5]
fromList [2,3]

• (size c) es el número de elementos del conjunto c. Por ejemplo,

ghci> size (fromList [3,2,5,3,2,1])
4

• (isSubsetOf c1 c2) se verifica si c1 es un subconjunto de c2. Por ejemplo,

ghci> isSubsetOf (fromList [3,5]) (fromList [3,2,5]) 
True
ghci> isSubsetOf (fromList [3,5,2]) (fromList [3,2,5]) 
True
ghci> isProperSubsetOf (fromList [3,7]) (fromList [3,2,5]) 
False

• (isProperSubsetOf c1 c2) se verifica si c1 es un subconjunto propio de c2. Por ejemplo,

ghci> isProperSubsetOf (fromList [3,5]) (fromList [3,2,5]) 
True
ghci> isProperSubsetOf (fromList [3,5,2]) (fromList [3,2,5]) 
False
ghci> isProperSubsetOf (fromList [3,7]) (fromList [3,2,5]) 
False

• (c1 == c2) se verifica si los conjuntos c1 y c2 son iguales. Por ejemplo,

ghci> fromList [3,2,5] == fromList [5,2,3,2]
True
ghci> fromList [3,2,5] == fromList [5,1,3,2]
False

• (map f c) es el conjunto obtenido aplicando a cada elemento de c la función f. Por ejemplo,

ghci> S.map (+2) (fromList [3,2,7])
fromList [4,5,9]

• (filter p c) es el conjunto de los elementos de c que cumplen p. Por ejemplo,

ghci> S.filter even (fromList [3,2,5,7,8,6,9])
fromList [2,6,8]

5 Funciones sobre conjuntos

• En Manual de la librería de conjuntos Data.Set se describen las funciones de la librería mediante ejemplos.

• En Data.Set se describen las funciones de la librería junto con sus órdenes de complejidad.

6 Referencia

• Apartado Data.Set del libro ¡Aprende Haskell por el bien de todos!.