{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
" Tema 27: Los diccionarios en Haskell (Data.Map)\n",
" \n",
"\n",
"----------\n",
"\n",
"[José A. Alonso](https://www.cs.us.es/~jalonso) \n",
"[Departamento de Ciencias de la Computación e I.A.](https://www.cs.us.es) \n",
"[Universidad de Sevilla](http://www.us.es) \n",
"Sevilla, 23 de agosto de 2019"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"> __Notas:__ \n",
"+ La versión interactiva de este tema se encuentra en [Binder](https://mybinder.org/v2/gh/jaalonso/Temas_interactivos_de_PF_con_Haskell/master?urlpath=lab/tree/temas/Tema-27.ipynb).\n",
"+ Se desactiva el [corrector estilo de Haskell](https://github.com/gibiansky/IHaskell/wiki#opt-no-lint)."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
":opt no-lint"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Introducción\n",
"\n",
"* Los *diccionarios* (también llamados *listas de asociación*) son listas\n",
"utilizadas para almacenar pares clave-valor donde el orden no importa.\n",
"\n",
"* Por ejemplo, podemos tener un diccionario para almacenar números de teléfono, donde\n",
"los números de telefono serían los valores y los nombres de la gente serían las\n",
"claves.\n",
"\n",
"* No nos importa el orden en el que estén almacenados, sólo queremos\n",
"obtener el número correspondiente cada persona.\n",
"\n",
"* En este manual se presentan ejemplos de las funciones de la librería de diccionarios\n",
"[Data.Map 0.5.5.1](http://bit.ly/1Hy0zoJ).\n",
"\n",
"* En los ejemplos se supone que se ha importado la siguiente librería "
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [],
"source": [
"import Data.Map as M"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"* Debido a que `Data.Map` exporta funciones que colisionan con las de `Prelude` y\n",
" `Data.List`, se suele importar de forma cualificada. \n",
"\n",
"~~~~haskell\n",
"import qualified Data.Map as Map\n",
"~~~~"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# El tipo de los diccionarios\n",
"\n",
"* `(Map c a)` es el tipo de los diccionarios con las claves de tipo `c` y los\n",
" valores de tipo `a`. Por ejemplo,"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"d1 :: forall a. Num a => Map [Char] a"
],
"text/plain": [
"d1 :: forall a. Num a => Map [Char] a"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"d1 = fromList [(\"Ana\",5),(\"Juan\",7),(\"Eva\",6)]\n",
":type d1"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"d2 = fromList [(\"Ana\",5),(\"Eva\",6),(\"Juan\",7)]\n",
"d1 == d2"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Resumen de funciones básicas\n",
"\n",
"+ `(fromList ps)` es el diccionario cuyos elementos es la lista de pares\n",
" `ps`. Si la lista tiene más de un valor para una clave, sólo se conserva el\n",
" último. Por ejemplo, "
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"fromList [(3,\"b\"),(5,\"c\")]"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"fromList [(5,\"a\"),(3,\"b\"),(5,\"c\")]"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"fromList [(3,\"a\"),(5,\"c\")]"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"fromList [(5,\"a\"),(3,\"b\"),(5,\"c\"),(3,\"a\")]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"+ `empty` es el diccionario vacío. Por ejemplo, "
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"fromList []"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"empty"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"+ `(insert k x d)` es el diccionario obtenido añadiéndole a `d` el par `(k,x)`\n",
" y eliminando el valor de `k` en `d` en el caso de que existiera. Por ejemplo,"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"fromList [(3,7)]"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"insert 3 7 empty"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"fromList [(3,'c'),(4,'a'),(6,'b'),(8,'e')]"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"insert 3 'c' (fromList [(4,'a'),(6,'b'),(8,'e')])"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"fromList [(4,'a'),(6,'c'),(8,'e')]"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"insert 6 'c' (fromList [(4,'a'),(6,'b'),(8,'e')])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"+ `null d` se verifica si el diccionario `d` es vacío. Por ejemplo, "
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"M.null (fromList [])"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"False"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"M.null (fromList [(3,2)])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"+ `(size d)` es el número de elementos del diccionario `d`. Por ejemplo, "
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"0"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"size empty"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"3"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"size (fromList [(4,'a'),(5,'b'),(2,'e')])"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"3"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"size (fromList [(4,'a'),(5,'b'),(2,'e'),(4,'a')])"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"3"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"size (fromList [(4,'a'),(5,'b'),(2,'e'),(4,'c')])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"3+ `(singleton k x)` es el diccionario cuya única clave es `k` u su valor es\n",
" `x`. Por ejemplo,"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"fromList [('d',4)]"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"singleton 'd' 4"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"+ `(lookup x d)` es justo el valor del elemento del diccionario `d` cuya\n",
" clave es `x`, si hay alguno y `Nothing`, en caso contrario. Por ejemplo,"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"Just 'b'"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"M.lookup 5 (fromList [(4,'a'),(5,'b'),(2,'e')])"
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"Nothing"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"M.lookup 7 (fromList [(4,'a'),(5,'b'),(2,'e')])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"+ `(member x d)` se verifica si `x` es una clave del diccionario `d`. Por ejemplo, "
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"member 5 (fromList [(4,'a'),(5,'b'),(2,'e')])"
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"False"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"member 7 (fromList [(4,'a'),(5,'b'),(2,'e')])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"+ `(map f d)` aplica `f` a todos los valores de `d`. Por ejemplo, "
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"fromList [(3,9),(6,8),(7,4),(8,5)]"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"M.map (+1) (fromList [(8,4),(3,8),(7,3),(6,7)])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"+ `(filter p d)` es el diccionario formado por los elementos de `d` cuyo valor\n",
" cumple el predicado `p`. Por ejemplo, "
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"fromList [(\"a\",7),(\"e\",8)]"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"M.filter (>5) (fromList [(\"b\",4),(\"e\",8),(\"d\",3),(\"a\",7)])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"+ `(toList d)` es la lista ordenada de los elementos del diccionario `d`. Por\n",
" ejemplo, "
]
},
{
"cell_type": "code",
"execution_count": 24,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[(1,7),(2,8),(3,5)]"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"toList (fromList [(1,7),(3,5),(2,8)])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"+ `(keys d)` es a lista ordenada de las claves del diccionario `d`. Por ejemplo, "
]
},
{
"cell_type": "code",
"execution_count": 25,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[1,2,3]"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"keys (fromList [(1,7),(3,5),(2,8)])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"+ `(elems d)` es a lista de los valores del diccionario `d` ordenados según sus\n",
" claves. Por ejemplo, "
]
},
{
"cell_type": "code",
"execution_count": 26,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[7,8,5]"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"elems (fromList [(1,7),(3,5),(2,8)])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"+ `(fromListWith f ps)` es el diccionario cuyos elementos es la lista de pares\n",
" `ps` combinados con la operación `f`. Por ejemplo, "
]
},
{
"cell_type": "code",
"execution_count": 27,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"fromList [(3,\"b\"),(5,\"ca\")]"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"fromListWith (++) [(5,\"a\"),(3,\"b\"),(5,\"c\")]"
]
},
{
"cell_type": "code",
"execution_count": 28,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"fromList [(3,\"ab\"),(5,\"ca\")]"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"fromListWith (++) [(5,\"a\"),(3,\"b\"),(5,\"c\"),(3,\"a\")]"
]
},
{
"cell_type": "code",
"execution_count": 29,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"fromList [(3,-5),(5,-2)]"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"fromListWith (-) [(5,4),(3,6),(5,2),(3,1)]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"+ `(insertWith f k x d)` es el diccionario obtenido añadiéndole a `d` el\n",
" par `(k,x)` si `k` no es una clave de `d` o el par `(k,f x y)` si el par\n",
" `(k,y)` pertenece a `d`. Por ejemplo, "
]
},
{
"cell_type": "code",
"execution_count": 30,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"fromList [(3,\"b\"),(5,\"a\"),(7,\"d\")]"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"insertWith (++) 7 \"d\" (fromList [(5,\"a\"), (3,\"b\")])"
]
},
{
"cell_type": "code",
"execution_count": 31,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"fromList [(3,\"db\"),(5,\"a\")]"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"insertWith (++) 3 \"d\" (fromList [(5,\"a\"), (3,\"b\")])"
]
},
{
"cell_type": "code",
"execution_count": 32,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"fromList [(3,8),(5,6)]"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"insertWith (*) 3 2 (fromList [(5,6), (3,4)])"
]
},
{
"cell_type": "code",
"execution_count": 33,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"fromList [(3,2)]"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"insertWith (*) 3 2 empty"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Funciones sobre diccionarios\n",
"\n",
"+ En [Manual de la librería de diccionarios Data.Map](http://bit.ly/1DsjKTs) se\n",
" describen las funciones de la librería mediante ejemplos.\n",
" \n",
"+ En [Data.Map.Lazy](http://bit.ly/1Hy0zoJ) se describen las funciones de la\n",
" librería junto con sus órdenes de complejidad."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Referencia\n",
"\n",
"+ Apartado [Data.Map](http://bit.ly/1IK30IJ) del libro\n",
" [¡Aprende Haskell por el bien de todos!](http://bit.ly/1IK2ZEB)."
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Haskell",
"language": "haskell",
"name": "haskell"
},
"language_info": {
"codemirror_mode": "ihaskell",
"file_extension": ".hs",
"name": "haskell",
"pygments_lexer": "Haskell",
"version": "8.6.5"
}
},
"nbformat": 4,
"nbformat_minor": 4
}