En este manual se presentan ejemplos de las funciones de la librería de conjuntos Data.Set 0.5.5.1. En los ejemplos se supone que se han importado la siguiente librería

ghci> import Data.Set as S

1 El tipo de los conjuntos

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

ghci> let c1 = fromList [3,2,5,3]
ghci> :t c1
c1 :: Set Integer
ghci> c1
fromList [2,3,5]
ghci> let c2 = fromList [2,5,2,3]
ghci> c1 == c2
True

2 Construcción de conjuntos

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

ghci> empty
fromList []

• (singleton x) es el conjunto cuyo único elemento es x. Por ejemplo,

ghci> singleton 5
fromList [5]

3 Inserción y eliminación de elementos

• (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]

4 Información sobre conjuntos

• (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

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

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

• (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

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

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

• (lookupLT x c) es justo el mayor elemento de c menor que x, si hay alguno y Nothing, en caso contrario. Por ejemplo,

ghci> lookupLT 5 (fromList [2,4,3,5,7])
Just 4
ghci> lookupLT 2 (fromList [2,4,3,5,7])
Nothing

• (lookupGT x c) es justo el menor elemento de c mayor que x, si hay alguno y Nothing, en caso contrario. Por ejemplo,

ghci> lookupGT 2 (fromList [2,4,3,5,7])
Just 3
ghci> lookupGT 7 (fromList [2,4,3,5,7])
Nothing

• (lookupLE x c) es justo el mayor elemento de c menor o igual que x, si hay alguno y Nothing, en caso contrario. Por ejemplo,

ghci> lookupLE 5 (fromList [2,4,3,5,7])
Just 5
ghci> lookupLE 6 (fromList [2,4,3,5,7])
Just 5
ghci> lookupLE 1 (fromList [2,4,3,5,7])
Nothing

• (lookupGE x c) es justo el menor elemento de c mayor o igual que x, si hay alguno y Nothing, en caso contrario. Por ejemplo,

ghci> lookupGE 5 (fromList [2,4,3,5,7])
Just 5
ghci> lookupGE 6 (fromList [2,4,3,5,7])
Just 7
ghci> lookupGE 9 (fromList [2,4,3,5,7])
Nothing

5 Subconjuntos

• (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

• (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

6 Elementos mínimos y máximos

• (findMin c) es el menor elemento del conjunto c. Por ejemplo,

ghci> findMin (fromList [3,2,5])
2
ghci> findMin empty
*** Exception: Set.findMin: empty set has no minimal element

• (findMax c) es el mayor elemento del conjunto c. Por ejemplo,

ghci> findMax (fromList [3,2,5,4])
5
ghci> findMax empty
*** Exception: Set.findMax: empty set has no maximal element

• (deleteMin c) es el conjunto obtenido eliminando el menor elemento de c. Por ejemplo,

ghci> deleteMin (fromList [3,2,5])
fromList [3,5]
ghci> deleteMin empty
fromList []

• (deleteMax c) es el conjunto obtenido eliminando el mayor elemento de c. Por ejemplo,

ghci> deleteMax (fromList [3,2,5,4])
fromList [2,3,4]
ghci> deleteMax empty
fromList []

• (deleteFindMin c) es el par formado por el menor elemento de c y el conjunto obtenido elimnando dicho elemento de c. Por ejemplo,

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

• (deleteFindMax c) es el par formado por el mayor elemento de c y el conjunto obtenido eliminando dicho elemento de c. Por ejemplo,

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

• (minView c) es el par formado por el menor elemento de c y el conjunto obtenido eliminando dicho elemento de c o Nothing si no tiene elementos. Por ejemplo,

ghci> minView (fromList [3,2,7,4])
Just (2,fromList [3,4,7])
ghci> minView empty
Nothing

• (maxView c) es el par formado por el mayor elemento de c y el conjunto obtenido eliminando dicho elemento de c o Nothing si no tiene elementos. Por ejemplo,

ghci> maxView (fromList [3,2,7,4])
Just (7,fromList [2,3,4])
ghci> maxView empty
Nothing

7 Operaciones con conjuntos

7.1 Unión

• (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]

• (unions cs) es la unión de la lista de conjuntos cs. Por ejemplo,

ghci> unions [fromList [3,2], fromList [2,5], fromList [3,5,7]]
fromList [2,3,5,7]

7.2 Intersección

• (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]

7.3 Diferencia

• (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]

8 Funciones de orden superior

8.1 Filtrados y particiones

• (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]

• (partition p c) es el par cuya primera componente es el conjunto de los elementos de c que cumplen p y la segunda, por los que no lo cumplen. Por ejemplo,

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

8.2 Aplicaciones ("map")

• (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]

8.3 Plegados ("fold")

• (foldr f e c) es el conjunto obtenido plegando por la derecha los elementos del conjunto c a partir de e. Por ejemplo,

ghci> S.foldr (-) 0 (fromList [3,2,5,2])
4
ghci> 2-(3-(5-0))
4

• (foldl f e c) es el conjunto obtenido plegando por la izquierda los elementos del conjunto c a partir de e. Por ejemplo,

ghci> S.foldl (-) 0 (fromList [3,2,5,2])
-10
ghci> ((0-2)-3)-5
-10

• (foldr' f e c) es la versión estricta de foldr. Por ejemplo,

ghci> let c = fromList [1..2000000]
ghci> S.foldr (+) 0 c
2000001000000
(1.85 secs, 282641652 bytes)
ghci> S.foldr' (+) 0 c
2000001000000
(0.42 secs, 176228860 bytes)

• (foldl' f e c) es la versión estricta de foldl. Por ejemplo,

ghci> let c = fromList [1..2000000]
ghci> S.foldl (+) 0 c
2000001000000
(1.80 secs, 277983108 bytes)
ghci> S.foldl' (+) 0 c
2000001000000
(0.39 secs, 172569700 bytes)

9 Conversiones

9.1 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]

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

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

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

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

9.2 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 :: Set Integer

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

ghci> size (fromAscList [1..1000000])
1000000
(0.48 secs, 141113268 bytes)
ghci> size (fromList [1..1000000])
1000000
(1.49 secs, 607884408 bytes)

• (fromDistinctAscList xs) es el conjunto cuyos elementos son los de la lista creciente xs de elementos no repetidos. Por ejemplo,

ghci> size (fromAscList [1..4000000])
4000000
(3.15 secs, 561334996 bytes)
ghci> size (fromDistinctAscList [1..4000000])
4000000
(2.98 secs, 432857796 bytes)

10 Igualdad

• (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

11 División según un elemento

• (split x c) es el par cuya primera componente es el conjunto de elementos de c menores que x y la segunda, los mayores. Por ejemplo,

ghci> split 5 (fromList [3,2,5,1,7])
(fromList [1,2,3],fromList [7])
ghci> split 9 (fromList [3,2,5,1,7])
(fromList [1,2,3,5,7],fromList [])
ghci> split 0 (fromList [3,2,5,1,7])
(fromList [],fromList [1,2,3,5,7])

• (splitMember x c) es la terna cuya primera componente es el conjunto de elementos de c menores que x, la segunda indica si x pertenece a c y la tercera, son elementos de c mayores que x. Por ejemplo,

ghci> splitMember 5 (fromList [3,2,5,1,7])
(fromList [1,2,3],True,fromList [7])
ghci> splitMember 6 (fromList [3,2,5,1,7])
(fromList [1,2,3,5],False,fromList [7])

12 Índices

• (findIndex x c) es la posición de x en c, contando a partir de 0. Por ejemplo,

ghci> findIndex 5 (fromList [3,7,5,3])
1
ghci> findIndex 4 (fromList [3,7,5,3])
*** Exception: Set.findIndex: element is not in the set

• (lookupIndex x c) es justo la posición de x en c, contando a partir de 0. Por ejemplo,

ghci> lookupIndex 5 (fromList [3,7,5,3])
Just 1
ghci> lookupIndex 4 (fromList [3,7,5,3])
Nothing

• (elemAt n c) es el elemento de c en la posición n, contando a partir de 0. Por ejemplo,

ghci> elemAt 1 (fromList [3,7,5,3])
5
ghci> elemAt 9 (fromList [3,7,5,3])
*** Exception: Set.elemAt: index out of range

• (deleteAt n c) es el conjunto obtenido eliminando el elemento de c en la posición n, contando a partir de 0. Por ejemplo,

ghci> deleteAt 1 (fromList [3,7,5])
fromList [3,7]
ghci> deleteAt 4 (fromList [3,7,5])
fromList *** Exception: Set.deleteAt: index out of range

13 Conjuntos y árboles

• (showTree c) es la cadena correspondient al árbol del conjunto c. Por ejemplo,

ghci> putStrLn (showTree (fromList [1..5]))
4
+--2
|  +--1
|  +--3
+--5

ghci> putStrLn (showTree (fromList [1..7]))
4
+--2
|  +--1
|  +--3
+--6
   +--5
   +--7

• (showTreeWith x y c) es la cadena correspondient al árbol del conjunto c donde se puede elegir el aspecto según los valores de x e y. Por ejemplo,

ghci> putStrLn (showTreeWith True False (fromList [1..5]))
4
+--2
|  +--1
|  +--3
+--5

ghci> putStrLn (showTreeWith True True (fromList [1..5]))
4
|
+--2
|  |
|  +--1
|  |
|  +--3
|
+--5

ghci> putStrLn (showTreeWith False True (fromList [1..5]))
+--5
|
4
|
|  +--3
|  |
+--2
   |
   +--1

ghci> putStrLn (showTreeWith False False (fromList [1..5]))
+--5
4
|  +--3
+--2
   +--1