{ "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 }