Tema 29: Las librerías de conjuntos y diccionarios en Haskell

Índice

1. Introducción de los conjuntos
2. El tipo de los conjuntos
3. Funciones sobre conjuntos
4. Introducción de los diccionarios
5. El tipo de los diccionarios
6. Funciones sobre diccionarios
7. Referencia

1. Introducción de los conjuntos

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.5.1
En los ejemplos se supone que se ha importado la siguiente librería
```
λ> 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,

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

3. Funciones sobre conjuntos

3.1. Funciones básicas

empty es el conjunto vacío. Por ejemplo,
```
λ> empty
fromList []
```

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

λ> insert 7 (fromList [3,2,5])
fromList [2,3,5,7]
λ> 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,

λ> delete 3 (fromList [3,2,5,3,4])
fromList [2,4,5]
λ> 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,

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

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

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

3.2. Complejidades

Comparación de las complejidades de las operaciones de los conjuntos definidas en el Tema 17 con las de la librería de conjuntos Data.Set.

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)

donde las representaciones de conjuntos son

LNOCD: listas no ordenadas con duplicados
LNOSD: listas no ordenadas sin duplicados
LOSD: listas ordenadas sin duplicados

3.3. De listas a conjuntos y viceversa

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

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

(toList c) es la lista de los elementos del conjunto c ordenados crecientemente. Por ejemplo,
```
λ> toList (fromList [3,2,5,2,1,5])
[1,2,3,5]
```
(elems c) es la lista de los elementos del conjunto c ordenados crecientemente. Por ejemplo,
```
λ> elems (fromList [3,2,5,2,1,5])
[1,2,3,5]
```

3.4. Operaciones y relaciones usuales

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

λ> 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,
```
λ> 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,
```
λ> 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,
```
λ> fromList [2,5,3] \\ fromList [1,4,5]
fromList [2,3]
```
(size c) es el número de elementos del conjunto c. Por ejemplo,
```
λ> size (fromList [3,2,5,3,2,1])
4
```

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

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

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

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

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

λ> fromList [3,2,5] == fromList [5,2,3,2]
True
λ> 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,
```
λ> 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,
```
λ> S.filter even (fromList [3,2,5,7,8,6,9])
fromList [2,6,8]
```

3.5. Más 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.

4. Introducción de los diccionarios

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
```
λ> import Data.Map as M
```
Debido a que Data.Map exporta funciones que colisionan con las de Prelude y Data.List, se suele importar de forma cualificada.
```
import qualified Data.Map as Map
```

5. El tipo de los diccionarios

(Map c a) es el tipo de los diccionarios con las claves de tipo c y los valores de tipo a. Por ejemplo,

λ> let d1 = fromList [("Ana",5),("Juan",7),("Eva",6)]
λ> :t d1
d1 :: Map [Char] Integer
λ> let d2 = fromList [("Ana",5),("Eva",6),("Juan",7)]
λ> d1 == d2
True

6. Funciones sobre diccionarios

6.1. Funciones básicas

empty es el diccionario vacío. Por ejemplo,
```
λ> 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,

λ> insert 3 7 empty
fromList [(3,7)]
λ> insert 3 'c' (fromList [(4,'a'),(6,'b'),(8,'e')])
fromList [(3,'c'),(4,'a'),(6,'b'),(8,'e')]
λ> 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,

λ> delete 3 (fromList [(5,"a"),(3,"b"),(7,"d")])
fromList [(5,"a"),(7,"d")]
λ> 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,

λ> member 5 (fromList [(4,'a'),(5,'b'),(2,'e')])
True
λ> member 7 (fromList [(4,'a'),(5,'b'),(2,'e')])
False

#+end_src

null d se verifica si el diccionario d es vacío. Por ejemplo,

λ> M.null (fromList [])
True
λ> M.null (fromList [(3,2)])
False

6.2. De listas a diccionarios y viceversa

(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,
```
λ> fromList [(5,"a"),(3,"b"),(5,"c")]
fromList [(3,"b"),(5,"c")]
λ> 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,
```
λ> toList (fromList [(1,7),(3,5),(2,8)])
[(1,7),(2,8),(3,5)]
```
(keys d) es a lista ordenada de las claves del diccionario d. Por ejemplo,
```
λ> 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,
```
λ> elems (fromList [(1,7),(3,5),(2,8)])
[7,8,5]
```

6.3. Operaciones y relaciones usuales

(size d) es el número de elementos del diccionario d. Por ejemplo,

λ> size empty
0
λ> size (fromList [(4,'a'),(5,'b'),(2,'e')])
3
λ> size (fromList [(4,'a'),(5,'b'),(2,'e'),(4,'a')])
3
λ> 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,
```
λ> 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,
```
λ> M.lookup 5 (fromList [(4,'a'),(5,'b'),(2,'e')])
Just 'b'
λ> M.lookup 7 (fromList [(4,'a'),(5,'b'),(2,'e')])
Nothing
```

(map f d) aplica f a todos los valores de d. Por ejemplo,

λ> 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,
```
λ> 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,

λ> fromListWith (++) [(5,"a"),(3,"b"),(5,"c")]
fromList [(3,"b"),(5,"ca")]
λ> fromListWith (++) [(5,"a"),(3,"b"),(5,"c"),(3,"a")]
fromList [(3,"ab"),(5,"ca")]
λ> 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,

λ> insertWith (++) 7 "d" (fromList [(5,"a"), (3,"b")])
fromList [(3,"b"),(5,"a"),(7,"d")]
λ> insertWith (++) 3 "d" (fromList [(5,"a"), (3,"b")])
fromList [(3,"db"),(5,"a")]
λ> insertWith (*) 3 2 (fromList [(5,6), (3,4)])
fromList [(3,8),(5,6)]
λ> insertWith (*) 3 2 empty
fromList [(3,2)]

6.4. Más funciones sobre diccionarios

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.

7. Referencia

M. Lipovača ¡Aprende Haskell por el bien de todos!:
- Apartado Data.Set.
- Apartado Data.Map.