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
Data.Set
exporta funciones que colisionan con las de Prelude
y Data.List
, se suele importar de forma cualificada.(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
empty
es el conjunto vacío. Por ejemplo,(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,(null c)
se verifica si c
es el conjunto vacío. Por ejemplo,TAD | LNOCD | LNOSD | LOSD | Data.Set | |
---|---|---|---|---|---|
vacio | O(1) | O(1) | O(1) | empty | O(1) |
inserta | O(1) | O(n) | O(n) | insert | O(log(n)) |
elimina | O(n) | O(n) | O(n) | delete | O(log(n)) |
pertenece | O(n) | O(n) | O(n) | member | O(log(n)) |
esVacio | O(1) | O(1) | O(1) | null | O(1) |
(fromList xs)
es el conjunto cuyos elementos son los de la lista xs
. Por ejemplo,(toList c)
es la lista de los elementos del conjunto c
ordenados crecientemente. Por ejemplo,(elems c)
es la lista de los elementos del conjunto c
ordenados crecientemente. Por ejemplo,(union cs c2)
es la unión de los conjuntos c1
y c2
. Por ejemplo,(intersection cs c2)
es la intersecciṕn de los conjuntos c1
y c2
. Por ejemplo,(difference c1 c2)
es la diferencia de los conjuntos c1
y c2
. Por ejemplo,(c1 \\ c2)
es la diferencia de los conjuntos c1
y c2
. Por ejemplo,(size c)
es el número de elementos del conjunto c
. Por ejemplo,(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,(filter p c)
es el conjunto de los elementos de c
que cumplen p
. Por ejemplo,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.
Los diccionarios (también llamados listas de asociación) son listas utilizadas para almacenar pares clave-valor donde el orden no importa.
Por ejemplo, podemos tener un diccionario para almacenar números de teléfono, donde los números de telefono serían los valores y los nombres de la gente serían las claves.
No nos importa el orden en el que estén almacenados, sólo queremos obtener el número correspondiente cada persona.
En este manual se presentan ejemplos de las funciones de la librería de diccionarios Data.Map 0.5.5.1.
En los ejemplos se supone que se ha importado la siguiente librería
ghci> import Data.Map as M
Data.Map
exporta funciones que colisionan con las de Prelude
y Data.List
, se suele importar de forma cualificada.(Map c a)
es el tipo de los diccionarios con las claves de tipo c
y los valores de tipo a
. Por ejemplo,ghci> let d1 = fromList [("Ana",5),("Juan",7),("Eva",6)]
ghci> :t d1
d1 :: Map [Char] Integer
ghci> let d2 = fromList [("Ana",5),("Eva",6),("Juan",7)]
ghci> d1 == d2
True
empty
es el diccionario vacío. Por ejemplo,ghci> empty
fromList []
(insert k x d)
es el diccionario obtenido añadiéndole a d
el par (k,x)
y eliminando el valor de k
en d
en el caso de que existiera. Por ejemplo,ghci> insert 3 7 empty
fromList [(3,7)]
ghci> insert 3 'c' (fromList [(4,'a'),(6,'b'),(8,'e')])
fromList [(3,'c'),(4,'a'),(6,'b'),(8,'e')]
ghci> insert 6 'c' (fromList [(4,'a'),(6,'b'),(8,'e')])
fromList [(4,'a'),(6,'c'),(8,'e')]
(delete k d)
es el diccionario obtenido eliminando en d
la clave k
y su valor. Por ejemplo,ghci> delete 3 (fromList [(5,"a"),(3,"b"),(7,"d")])
fromList [(5,"a"),(7,"d")]
ghci> delete 4 (fromList [(5,"a"),(3,"b"),(7,"d")])
fromList [(3,"b"),(5,"a"),(7,"d")]
(member x d)
se verifica si x
es una clave del diccionario d
. Por ejemplo,ghci> member 5 (fromList [(4,'a'),(5,'b'),(2,'e')])
True
ghci> member 7 (fromList [(4,'a'),(5,'b'),(2,'e')])
False
null d
se verifica si el diccionario d
es vacío. Por ejemplo,(fromList ps)
es el diccionario cuyos elementos es la lista de pares ps
. Si la lista tiene más de un valor para una clave, sólo se conserva el último. Por ejemplo,ghci> fromList [(5,"a"),(3,"b"),(5,"c")]
fromList [(3,"b"),(5,"c")]
ghci> fromList [(5,"a"),(3,"b"),(5,"c"),(3,"a")]
fromList [(3,"a"),(5,"c")]
(toList d)
es la lista ordenada de los elementos del diccionario d
. Por ejemplo,(keys d)
es a lista ordenada de las claves del diccionario d
. Por ejemplo,ghci> keys (fromList [(1,7),(3,5),(2,8)])
[1,2,3]
(elems d)
es a lista de los valores del diccionario d
ordenados según sus claves. Por ejemplo,(size d)
es el número de elementos del diccionario d
. Por ejemplo,ghci> size empty
0
ghci> size (fromList [(4,'a'),(5,'b'),(2,'e')])
3
ghci> size (fromList [(4,'a'),(5,'b'),(2,'e'),(4,'a')])
3
ghci> size (fromList [(4,'a'),(5,'b'),(2,'e'),(4,'c')])
3
(singleton k x)
es el diccionario cuya única clave es k
u su valor es x
. Por ejemplo,ghci> singleton 'd' 4
fromList [('d',4)]
(lookup x d)
es justo el valor del elemento del diccionario d
cuya clave es x
, si hay alguno y Nothing
, en caso contrario. Por ejemplo,ghci> M.lookup 5 (fromList [(4,'a'),(5,'b'),(2,'e')])
Just 'b'
ghci> M.lookup 7 (fromList [(4,'a'),(5,'b'),(2,'e')])
Nothing
(map f d)
aplica f
a todos los valores de d
. Por ejemplo,ghci> M.map (+1) (fromList [(8,4),(3,8),(7,3),(6,7)])
fromList [(3,9),(6,8),(7,4),(8,5)]
(filter p d)
es el diccionario formado por los elementos de d
cuyo valor cumple el predicado p
. Por ejemplo,ghci> M.filter (>5) (fromList [("b",4),("e",8),("d",3),("a",7)])
fromList [("a",7),("e",8)]
(fromListWith f ps)
es el diccionario cuyos elementos es la lista de pares ps
combinados con la operación f
. Por ejemplo,ghci> fromListWith (++) [(5,"a"),(3,"b"),(5,"c")]
fromList [(3,"b"),(5,"ca")]
ghci> fromListWith (++) [(5,"a"),(3,"b"),(5,"c"),(3,"a")]
fromList [(3,"ab"),(5,"ca")]
ghci> fromListWith (-) [(5,4),(3,6),(5,2),(3,1)]
fromList [(3,-5),(5,-2)]
(insertWith f k x d)
es el diccionario obtenido añadiéndole a d
el par (k,x)
si k
no es una clave de d
o el par (k,f x y)
si el par (k,y)
pertenece a d
. Por ejemplo,ghci> insertWith (++) 7 "d" (fromList [(5,"a"), (3,"b")])
fromList [(3,"b"),(5,"a"),(7,"d")]
ghci> insertWith (++) 3 "d" (fromList [(5,"a"), (3,"b")])
fromList [(3,"db"),(5,"a")]
ghci> insertWith (*) 3 2 (fromList [(5,6), (3,4)])
fromList [(3,8),(5,6)]
ghci> insertWith (*) 3 2 empty
fromList [(3,2)]
En Manual de la librería de diccionarios Data.Map se describen las funciones de la librería mediante ejemplos.
En Data.Map.Lazy se describen las funciones de la librería junto con sus órdenes de complejidad.