{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n",
" Tema 5: Definiciones de listas por comprensión\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, 1 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-05.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": [
"Nota: En este tema se usarán las siguientes librerías"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [],
"source": [
"import Data.Char \n",
"import Test.QuickCheck"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Generadores\n",
"\n",
"**Definiciones por comprensión**\n",
"\n",
"+ Definiciones por comprensión en Matemáticas:
\n",
" $\\{x^2 : x \\in \\{2,3,4,5\\}\\} = \\{4,9,16,25\\}$\n",
"\n",
"+ Definiciones por comprensión en Haskell:"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[4,9,16,25]"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"[x^2 | x <- [2..5]]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"+ La expresión `x <- [2..5]` se llama un *generador*.\n",
"\n",
"+ Ejemplos con más de un generador:"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)]"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"[(x,y) | x <- [1,2,3], y <- [4,5]]"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[(1,4),(2,4),(3,4),(1,5),(2,5),(3,5)]"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"[(x,y) | y <- [4,5], x <- [1,2,3]]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Generadores dependientes**\n",
"\n",
"+ Ejemplo con generadores dependientes:"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)]"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"[(x,y) | x <- [1..3], y <- [x..3]]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"+ `(concat xss)` es la concatenación de la lista de listas `xss`. Por ejemplo,\n",
"\n",
"```\n",
"concat [[1,3],[2,5,6],[4,7]] == [1,3,2,5,6,4,7]\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [],
"source": [
"concat' :: [[a]] -> [a]\n",
"concat' xss = [x | xs <- xss, x <- xs]"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[1,3,2,5,6,4,7]"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"concat' [[1,3],[2,5,6],[4,7]]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Generadores con variables anónimas**\n",
"\n",
"+ Ejemplo de generador con variable anónima: `(primeros ps)` es la lista de los\n",
" primeros elementos de la lista de pares `ps`. Por ejemplo,\n",
"\n",
"```sesion\n",
"primeros [(1,3),(2,5),(6,3)] == [1,2,6]`\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [],
"source": [
"primeros :: [(a, b)] -> [a]\n",
"primeros ps = [x | (x,_) <- ps]"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[1,2,6]"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"primeros [(1,3),(2,5),(6,3)]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"+ Definición de la longitud por comprensión"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [],
"source": [
"longitud :: [a] -> Int\n",
"longitud xs = sum [1 | _ <- xs]"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"3"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"longitud [4,2,7]"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"7"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"longitud \"Sevilla\""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Guardas\n",
"\n",
"+ Las listas por comprensión pueden tener *guardas* para restringir los valores.\n",
"\n",
"+ Ejemplo de guarda:"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[2,4,6,8,10]"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"[x | x <- [1..10], even x]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"+ `(factores n)` es la lista de los factores del número `n`. Por ejemplo,\n",
"\n",
"```sesion\n",
"factores 30 == [1,2,3,5,6,10,15,30]`\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {},
"outputs": [],
"source": [
"factores :: Int -> [Int]\n",
"factores n = [x | x <- [1..n], n `mod` x == 0]"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[1,2,3,5,6,10,15,30]"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"factores 30"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"+ `(primo n)` se verifica si `n` es primo. Por ejemplo,\n",
"\n",
"```sesion\n",
"primo 30 == False\n",
"primo 31 == True\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {},
"outputs": [],
"source": [
"primo :: Int -> Bool\n",
"primo n = factores n == [1, n]"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"False"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"primo 30"
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"primo 31"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"+ `(primos n)` es la lista de los primos menores o iguales que `n`. Por\n",
" ejemplo,\n",
"\n",
"```sesion\n",
"primos 31 == [2,3,5,7,11,13,17,19,23,29,31]\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {},
"outputs": [],
"source": [
"primos :: Int -> [Int]\n",
"primos n = [x | x <- [2..n], primo x]"
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[2,3,5,7,11,13,17,19,23,29,31]"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"primos 31"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Guarda con igualdad**\n",
"\n",
"+ Una *lista de asociación* es una lista de pares formado por una clave y un\n",
" valor. Por ejemplo,\n",
"\n",
"```sesion\n",
"[(\"Juan\",7),(\"Ana\",9),(\"Eva\",3)]\n",
"```\n",
"\n",
"+ `(busca c t)` es la lista de los valores de la lista de asociación `t` cuyas\n",
" claves valen `c`. Por ejemplo\n",
"\n",
"```sesion\n",
"busca 'b' [('a',1),('b',3),('c',5),('b',2)] == [3,2]\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {},
"outputs": [],
"source": [
"busca :: Eq a => a -> [(a, b)] -> [b]\n",
"busca c t = [v | (c', v) <- t, c' == c]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# La función `zip`\n",
"\n",
"**La función `zip` y elementos adyacentes**\n",
"\n",
"+ `(zip xs ys)` es la lista obtenida emparejando los elementos de las listas\n",
" `xs` e `ys`. Por ejemplo,\n",
"\n",
"```sesion\n",
"ghci> zip ['a','b','c'] [2,5,4,7]\n",
"[('a',2),('b',5),('c',4)] \n",
"```\n",
"\n",
"+ `(adyacentes xs)` es la lista de los pares de elementos adyacentes de la\n",
" lista xs. Por ejemplo,\n",
"\n",
"```sesion\n",
"adyacentes [2,5,3,7] == [(2,5),(5,3),(3,7)]\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {},
"outputs": [],
"source": [
"adyacentes :: [a] -> [(a, a)]\n",
"adyacentes xs = zip xs (tail xs)"
]
},
{
"cell_type": "code",
"execution_count": 24,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[(2,5),(5,3),(3,7)]"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"adyacentes [2,5,3,7]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Las funciones `zip`, `and` y listas ordenadas**\n",
"\n",
"+ `(and xs)` se verifica si todos los elementos de `xs` son\n",
" verdaderos. Por ejemplo, "
]
},
{
"cell_type": "code",
"execution_count": 25,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"and [2 < 3, 2+3 == 5] "
]
},
{
"cell_type": "code",
"execution_count": 26,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"False"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"and [2 < 3, 2+3 == 5, 7 < 7] "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"+ `(ordenada xs)` se verifica si la lista `xs` está ordenada. Por ejemplo,\n",
"\n",
"```sesion\n",
"ordenada [1,3,5,6,7] == True\n",
"ordenada [1,3,6,5,7] == False\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": 27,
"metadata": {},
"outputs": [],
"source": [
"ordenada :: Ord a => [a] -> Bool\n",
"ordenada xs = and [x <= y | (x,y) <- adyacentes xs]"
]
},
{
"cell_type": "code",
"execution_count": 28,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"ordenada [1,3,5,6,7]"
]
},
{
"cell_type": "code",
"execution_count": 29,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"False"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"ordenada [1,3,6,5,7]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**La función `zip` y lista de posiciones**\n",
"\n",
"+ `(posiciones x xs)` es la lista de las posiciones ocupadas por el elemento\n",
" `x` en la lista `xs`. Por ejemplo,\n",
"\n",
"```sesion\n",
"posiciones 5 [1,5,3,5,5,7] == [1,3,4]\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": 30,
"metadata": {},
"outputs": [],
"source": [
"posiciones :: Eq a => a -> [a] -> [Int]\n",
"posiciones x xs = \n",
" [i | (x',i) <- zip xs [0..n], x == x']\n",
" where n = length xs - 1"
]
},
{
"cell_type": "code",
"execution_count": 31,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[1,3,4]"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"posiciones 5 [1,5,3,5,5,7]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Comprensión de cadenas\n",
"\n",
"**Cadenas y listas**\n",
"\n",
"+ Las cadenas son listas de caracteres. Por ejemplo,"
]
},
{
"cell_type": "code",
"execution_count": 32,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"\"abc\" == ['a','b','c']"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"+ La expresión
\n",
" `\"abc\" :: String`
\n",
" es equivalente a
\n",
" `['a','b','c'] :: [Char]`\n",
"\n",
"+ Las funciones sobre listas se aplican a las cadenas:"
]
},
{
"cell_type": "code",
"execution_count": 33,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"5"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"length \"abcde\" "
]
},
{
"cell_type": "code",
"execution_count": 34,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"\"edcba\""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"reverse \"abcde\" "
]
},
{
"cell_type": "code",
"execution_count": 35,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"\"abcdefg\""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"\"abcde\" ++ \"fg\" "
]
},
{
"cell_type": "code",
"execution_count": 36,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[1,3,5,8]"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"posiciones 'a' \"Salamanca\" "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Definiciones sobre cadenas con comprensión**\n",
"\n",
"+ `(minusculas c)` es la cadena formada por las letras minúsculas de\n",
" la cadena `c`. Por ejemplo,\n",
"\n",
"```sesion\n",
"minusculas \"EstoEsUnaPrueba\" == \"stosnarueba\"\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": 37,
"metadata": {},
"outputs": [],
"source": [
"minusculas :: String -> String\n",
"minusculas xs = [x | x <- xs, elem x ['a'..'z']]"
]
},
{
"cell_type": "code",
"execution_count": 38,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"\"stosnarueba\""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"minusculas \"EstoEsUnaPrueba\""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"+ `(ocurrencias x xs)` es el número de veces que ocurre el carácter\n",
" `x` en la cadena `xs`. Por ejemplo,\n",
"\n",
"```sesion\n",
"ocurrencias 'a' \"Salamanca\" == 4\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": 39,
"metadata": {},
"outputs": [],
"source": [
"ocurrencias :: Char -> String -> Int\n",
"ocurrencias x xs = length [x' | x' <- xs, x == x'] "
]
},
{
"cell_type": "code",
"execution_count": 40,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"4"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"ocurrencias 'a' \"Salamanca\""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Cifrado César\n",
"\n",
"+ En el [cifrado César](http://es.wikipedia.org/wiki/Cifrado_César) cada letra\n",
" en el texto original es reemplazada por otra letra que se encuentra 3\n",
" posiciones más adelante en el alfabeto.\n",
"\n",
"+ La codificación de
\n",
" `\"en todo la medida\"`
\n",
" es
\n",
" `\"hq wrgr od phglgd\"`\n",
" \n",
"+ Se puede generalizar desplazando cada letra n posiciones.\n",
"\n",
"+ La codificación con un desplazamiento 5 de
\n",
" `\"en todo la medida\"`
\n",
" es
\n",
" `\"js ytit qf rjinif\"`
\n",
"\n",
"+ La descodificación de un texto codificado con un desplazamiento n se\n",
" obtiene codificándolo con un desplazamiento -n."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Codificación y descodificación\n",
"\n",
"**Las funciones `ord` y `char`**\n",
"\n",
"+ `(ord c)` es el código del carácter `c`. Por ejemplo,"
]
},
{
"cell_type": "code",
"execution_count": 41,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"97"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"ord 'a' "
]
},
{
"cell_type": "code",
"execution_count": 42,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"98"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"ord 'b' "
]
},
{
"cell_type": "code",
"execution_count": 43,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"65"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"ord 'A' "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"+ `(char n)` es el carácter de código `n`. Por ejemplo,"
]
},
{
"cell_type": "code",
"execution_count": 44,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'a'"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"chr 97 "
]
},
{
"cell_type": "code",
"execution_count": 45,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'b'"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"chr 98 "
]
},
{
"cell_type": "code",
"execution_count": 46,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'A'"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"chr 65 "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Codificación y descodificación: Código de letra**\n",
"\n",
"+ Simplificación: Sólo se codificarán las letras minúsculas dejando los\n",
" restantes caracteres sin modificar.\n",
"\n",
"+ `(let2int c)` es el entero correspondiente a la letra minúscula\n",
" `c`. Por ejemplo,\n",
"\n",
"```sesion\n",
"let2int 'a' == 0\n",
"let2int 'd' == 3\n",
"let2int 'z' == 25\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": 47,
"metadata": {},
"outputs": [],
"source": [
"let2int :: Char -> Int\n",
"let2int c = ord c - ord 'a'"
]
},
{
"cell_type": "code",
"execution_count": 48,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"0"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"let2int 'a'"
]
},
{
"cell_type": "code",
"execution_count": 49,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"3"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"let2int 'd'"
]
},
{
"cell_type": "code",
"execution_count": 50,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"25"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"let2int 'z'"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Codificación y descodificación: Letra de código**\n",
"\n",
"+ `(int2let n)` es la letra minúscula correspondiente al entero `n`. Por\n",
" ejemplo,\n",
"\n",
"```sesion\n",
"int2let 0 == 'a'\n",
"int2let 3 == 'd'\n",
"int2let 25 == 'z'\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": 51,
"metadata": {},
"outputs": [],
"source": [
"int2let :: Int -> Char\n",
"int2let n = chr (ord 'a' + n)"
]
},
{
"cell_type": "code",
"execution_count": 52,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'a'"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"int2let 0 "
]
},
{
"cell_type": "code",
"execution_count": 53,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'d'"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"int2let 3 "
]
},
{
"cell_type": "code",
"execution_count": 54,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'z'"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"int2let 25 "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Codificación y descodificación: Desplazamiento**\n",
"\n",
"+ `(desplaza n c)` es el carácter obtenido desplazando `n` caracteres el\n",
" carácter `c`. Por ejemplo,\n",
"\n",
"```sesion\n",
"desplaza 3 'a' == 'd'\n",
"desplaza 3 'y' == 'b'\n",
"desplaza (-3) 'd' == 'a'\n",
"desplaza (-3) 'b' == 'y'\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": 55,
"metadata": {},
"outputs": [],
"source": [
"desplaza :: Int -> Char -> Char\n",
"desplaza n c \n",
" | elem c ['a'..'z'] = int2let ((let2int c+n) `mod` 26)\n",
" | otherwise = c"
]
},
{
"cell_type": "code",
"execution_count": 56,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'d'"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"desplaza 3 'a' "
]
},
{
"cell_type": "code",
"execution_count": 57,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'b'"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"desplaza 3 'y' "
]
},
{
"cell_type": "code",
"execution_count": 58,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'a'"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"desplaza (-3) 'd' "
]
},
{
"cell_type": "code",
"execution_count": 59,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'y'"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"desplaza (-3) 'b' "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Codificación y descodificación**\n",
"\n",
"+ `(codifica n xs)` es el resultado de codificar el texto `xs` con un\n",
" desplazamiento `n`. "
]
},
{
"cell_type": "code",
"execution_count": 60,
"metadata": {},
"outputs": [],
"source": [
"codifica :: Int -> String -> String\n",
"codifica n xs = [desplaza n x | x <- xs]"
]
},
{
"cell_type": "code",
"execution_count": 61,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"\"Eq wrgr od phglgd\""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"codifica 3 \"En todo la medida\" "
]
},
{
"cell_type": "code",
"execution_count": 62,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"\"En todo la medida\""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"codifica (-3) \"Eq wrgr od phglgd\" "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Propiedades de la codificación con QuickCheck**\n",
"\n",
"+ Propiedad: Al desplazar n un carácter desplazado n, se obtiene el carácter\n",
" inicial."
]
},
{
"cell_type": "code",
"execution_count": 63,
"metadata": {},
"outputs": [],
"source": [
"prop_desplaza n xs = \n",
" desplaza (-n) (desplaza n xs) == xs"
]
},
{
"cell_type": "code",
"execution_count": 64,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"+++ OK, passed 100 tests."
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"quickCheck prop_desplaza"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"+ Propiedad: Al codificar con -n una cadena codificada con n, se obtiene la\n",
" cadena inicial."
]
},
{
"cell_type": "code",
"execution_count": 65,
"metadata": {},
"outputs": [],
"source": [
"prop_codifica n xs = \n",
" codifica (-n) (codifica n xs) == xs"
]
},
{
"cell_type": "code",
"execution_count": 66,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"+++ OK, passed 100 tests."
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"quickCheck prop_codifica"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Análisis de frecuencias\n",
"\n",
"**Tabla de frecuencias**\n",
"\n",
"+ Para descifrar mensajes se parte de la\n",
" [frecuencia de aparición de letras](http://es.wikipedia.org/wiki/Frecuencia_de_aparición_de_letras).\n",
"\n",
"+ `tabla` es la lista de la frecuencias de las letras en castellano, Por\n",
" ejemplo, la frecuencia de la `'a'` es del 12.53%, la de la `'b'` es 1.42%."
]
},
{
"cell_type": "code",
"execution_count": 67,
"metadata": {},
"outputs": [],
"source": [
"tabla :: [Float]\n",
"tabla = [12.53, 1.42, 4.68, 5.86, 13.68, 0.69, 1.01, \n",
" 0.70, 6.25, 0.44, 0.01, 4.97, 3.15, 6.71, \n",
" 8.68, 2.51, 0.88, 6.87, 7.98, 4.63, 3.93, \n",
" 0.90, 0.02, 0.22, 0.90, 0.52]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Frecuencias**\n",
"\n",
"+ `(porcentaje n m)` es el porcentaje de `n` sobre `m`. Por ejemplo,\n",
"\n",
"```sesion\n",
"porcentaje 2 5 == 40.0 \n",
"```"
]
},
{
"cell_type": "code",
"execution_count": 68,
"metadata": {},
"outputs": [],
"source": [
"porcentaje :: Int -> Int -> Float\n",
"porcentaje n m = (fromIntegral n / fromIntegral m) * 100"
]
},
{
"cell_type": "code",
"execution_count": 69,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"40.0"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"porcentaje 2 5"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"+ `(frecuencias xs)` es la frecuencia de cada una de las minúsculas\n",
" de la cadena `xs`. Por ejemplo,\n",
"\n",
"```sesion\n",
"ghci> frecuencias \"en todo la medida\"\n",
"[14.3,0,0,21.4,14.3,0,0,0,7.1,0,0,7.1,\n",
" 7.1,7.1,14.3,0,0,0,0,7.1,0,0,0,0,0,0]\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": 70,
"metadata": {},
"outputs": [],
"source": [
"frecuencias :: String -> [Float]\n",
"frecuencias xs = \n",
" [porcentaje (ocurrencias x xs) n | x <- ['a'..'z']]\n",
" where n = length (minusculas xs)"
]
},
{
"cell_type": "code",
"execution_count": 71,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[14.285715,0.0,0.0,21.428572,14.285715,0.0,0.0,0.0,7.1428576,0.0,0.0,7.1428576,7.1428576,7.1428576,14.285715,0.0,0.0,0.0,0.0,7.1428576,0.0,0.0,0.0,0.0,0.0,0.0]"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"frecuencias \"en todo la medida\""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Descifrado\n",
"\n",
"**Descifrado: Ajuste chi cuadrado**\n",
"\n",
"+ Una medida de la discrepancia entre la distribución observada $os_i$ y\n",
" la esperada $es_i$ es
\n",
" $\\chi^2 = \\displaystyle \\sum_{i=0}^{n-1}\\frac{(os_i-es_i)^2}{es_i}$
\n",
" Los menores valores corresponden a menores discrepancias.\n",
"\n",
"+ `(chiCuad os es)` es la medida chi cuadrado de las distribuciones `os` y\n",
" `es`. Por ejemplo,\n",
"\n",
"```sesion\n",
"chiCuad [3,5,6] [3,5,6] == 0.0\n",
"chiCuad [3,5,6] [5,6,3] == 3.9666667\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": 72,
"metadata": {},
"outputs": [],
"source": [
"chiCuad :: [Float] -> [Float] -> Float\n",
"chiCuad os es = \n",
" sum [((o-e)^2)/e | (o,e) <- zip os es]"
]
},
{
"cell_type": "code",
"execution_count": 73,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"0.0"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"chiCuad [3,5,6] [3,5,6] "
]
},
{
"cell_type": "code",
"execution_count": 74,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"3.9666667"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"chiCuad [3,5,6] [5,6,3] "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Descifrado: Rotación**\n",
"\n",
"+ `(rota n xs)` es la lista obtenida rotando `n` posiciones los elementos de la\n",
" lista `xs`. Por ejemplo,\n",
"\n",
"```sesion\n",
"rota 2 \"manolo\" == \"noloma\" \n",
"```"
]
},
{
"cell_type": "code",
"execution_count": 75,
"metadata": {},
"outputs": [],
"source": [
"rota :: Int -> [a] -> [a]\n",
"rota n xs = drop n xs ++ take n xs"
]
},
{
"cell_type": "code",
"execution_count": 76,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"\"noloma\""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"rota 2 \"manolo\""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Descifrado**\n",
"\n",
"+ `(descifra xs)` es la cadena obtenida descodificando la cadena `xs` por el\n",
" antidesplazamiento que produce una distribución de minúsculas con la\n",
" menor desviación chi cuadrado respecto de la tabla de distribución de las\n",
" letras en castellano. Por ejemplo,\n",
"\n",
"```sesion\n",
"codifica 5 \"Todo para nada\" == \"Ttit ufwf sfif\"\n",
"descifra \"Ttit ufwf sfif\" == \"Todo para nada\"\n",
"```"
]
},
{
"cell_type": "code",
"execution_count": 77,
"metadata": {},
"outputs": [],
"source": [
"descifra :: String -> String\n",
"descifra xs = codifica (-factor) xs\n",
" where\n",
" factor = head (posiciones (minimum tabChi) tabChi)\n",
" tabChi = [chiCuad (rota n tabla') tabla | n <- [0..25]]\n",
" tabla' = frecuencias xs"
]
},
{
"cell_type": "code",
"execution_count": 78,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"\"Ttit ufwf sfif\""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"codifica 5 \"Todo para nada\" "
]
},
{
"cell_type": "code",
"execution_count": 79,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"\"Todo para nada\""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"descifra \"Ttit ufwf sfif\" "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Bibliografía\n",
"\n",
"+ R. Bird. *Introducción a la programación funcional con Haskell*. Prentice Hall, 2000.\n",
" + Cap. 4: Listas.\n",
"\n",
"+ G. Hutton. *Programming in Haskell*. Cambridge University Press.\n",
" + Cap. 5: List comprehensions. \n",
"\n",
"+ B. O'Sullivan, D. Stewart y J. Goerzen. *Real World Haskell*. O'Reilly, 2008.\n",
" + Cap. 12: Barcode Recognition.\n",
"\n",
"+ B.C. Ruiz, F. Gutiérrez, P. Guerrero y J.E. Gallardo. *Razonando con\n",
" Haskell*. Thompson, 2004.\n",
" + Cap. 6: Programación con listas.\n",
"\n",
"+ S. Thompson. *Haskell: The Craft of Functional Programming*, Second\n",
" Edition. Addison-Wesley, 1999. \n",
" + Cap. 5: Data types: tuples and lists."
]
}
],
"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
}