Las librerías de conjuntos y diccionarios en Haskell

1 Introducción de los conjuntos

ghci> import Data.Set as S
import qualified Data.Set as S

2 El tipo de los conjuntos

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 Funciones sobre conjuntos

3.1 Funciones básicas

ghci> empty
fromList []
ghci> insert 7 (fromList [3,2,5])
fromList [2,3,5,7]
ghci> insert 2 (fromList [3,2,5])
fromList [2,3,5]
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]
ghci> member 5 (fromList [3,2,5])
True
ghci> member 7 (fromList [3,2,5])
False
ghci> S.null (fromList [])
True
ghci> S.null (fromList [5,2])
False

3.2 Complejidades

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)

3.3 De listas a conjuntos y viceversa

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

3.4 Operaciones y relaciones usuales

ghci> union (fromList [3,2,5]) (fromList [2,7,5])
fromList [2,3,5,7]
ghci> intersection (fromList [3,2,5]) (fromList [2,7,5])
fromList [2,5]
ghci> difference (fromList [2,5,3]) (fromList [1,4,5])
fromList [2,3]
ghci> fromList [2,5,3] \\ fromList [1,4,5]
fromList [2,3]
ghci> size (fromList [3,2,5,3,2,1])
4
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
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
ghci> fromList [3,2,5] == fromList [5,2,3,2]
True
ghci> fromList [3,2,5] == fromList [5,1,3,2]
False
ghci> S.map (+2) (fromList [3,2,7])
fromList [4,5,9]
ghci> S.filter even (fromList [3,2,5,7,8,6,9])
fromList [2,6,8]

3.5 Más funciones sobre conjuntos

4 Introducción de los diccionarios

ghci> import Data.Map as M
import qualified Data.Map as Map

5 El tipo de los diccionarios

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

6 Funciones sobre diccionarios

6.1 Funciones básicas

ghci> empty
fromList []
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')]
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")]
ghci> member 5 (fromList [(4,'a'),(5,'b'),(2,'e')])
True
ghci> member 7 (fromList [(4,'a'),(5,'b'),(2,'e')])
False
ghci> M.null (fromList [])
True
ghci> M.null (fromList [(3,2)])
False

6.2 De listas a diccionarios y viceversa

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")]
ghci> toList (fromList [(1,7),(3,5),(2,8)])
[(1,7),(2,8),(3,5)]
ghci> keys (fromList [(1,7),(3,5),(2,8)])
[1,2,3]
ghci> elems (fromList [(1,7),(3,5),(2,8)])
[7,8,5]

6.3 Operaciones y relaciones usuales

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
ghci> singleton 'd' 4
fromList [('d',4)]
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
ghci> M.map (+1) (fromList [(8,4),(3,8),(7,3),(6,7)])
fromList [(3,9),(6,8),(7,4),(8,5)]
ghci> M.filter (>5) (fromList [("b",4),("e",8),("d",3),("a",7)])
fromList [("a",7),("e",8)]
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)]
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)]

6.4 Más funciones sobre diccionarios

7 Referencia



Universidad de Sevilla

José A. Alonso Jiménez
Grupo de Lógica Computacional
Dpto. de Ciencias de la Computación e I.A.
Universidad de Sevilla