I1M2014: El cifrado César en Haskell

En la primera parte de la clase de hoy de Informática de 1º del Grado en Matemáticas hemos estudiado cómo definir en Haskell la codificación de mensajes usando el cifrado César.

El programa es el siguiente

import Data.Char

-- ---------------------------------------------------------------------
-- Codificación y descodificación                                     --
-- ---------------------------------------------------------------------

-- (let2int c) es el entero correspondiente a la letra minúscula c. Por
-- ejemplo, 
--    let2int 'a'  ==>  0
--    let2int 'd'  ==>  3
--    let2int 'z'  ==>  25
let2int :: Char -> Int
let2int c = ord c - ord 'a'

-- (int2let n) es la letra minúscula correspondiente al entero n. Por
-- ejemplo, 
--    int2let 0   ==>  'a'
--    int2let 3   ==>  'd'
--    int2let 25  ==>  'z'
int2let :: Int -> Char
int2let n = chr (ord 'a' + n)

-- (desplaza n c) es el carácter obtenido desplazando n caracteres el
-- carácter c. Por ejemplo,
--    desplaza   3  'a'  ==>  'd'
--    desplaza   3  'y'  ==>  'b'
--    desplaza (-3) 'd'  ==>  'a'
--    desplaza (-3) 'b'  ==>  'y'
desplaza :: Int -> Char -> Char
desplaza n c | isLower c = int2let ((let2int c + n) `mod` 26)
             | otherwise =  c

-- (codifica n xs) es el resultado de codificar el texto xs con un
-- desplazamiento n. Por ejemplo,
--    codifica   3  "En todo la medida"   ==>  "Eq wrgr od phglgd"
--    codifica (-3) "Eq wrgr od phglgd"   ==>  "En todo la medida"
codifica :: Int -> String -> String
codifica n xs = [desplaza n x | x <- xs]

-- ---------------------------------------------------------------------
-- Análisis de frecuencia                                             --
-- ---------------------------------------------------------------------

-- tabla es la lista de la frecuencias de las letras en castellano, Por
-- ejemplo, la frecuencia de la 'a' es del 12.53%, la de la 'b' es 1.42%.
tabla :: [Float]
tabla = [12.53, 1.42, 4.68, 5.86, 13.68, 0.69, 1.01, 0.70, 6.25, 
          0.44, 0.01, 4.97, 3.15,  6.71, 8.68, 2.51, 0.88, 6.87, 
          7.98, 4.63, 3.93, 0.90,  0.02, 0.22, 0.90, 0.52]

-- (minusculas xs) es la lista de minúsculas en la cadena xs. Por
-- ejemplo,
--    minusculas "EstoEsUnaPrueba"  ==>  "stosnarueba"  
minusculas :: String -> String
minusculas xs = [x | x <- xs, isLower x]

-- (ocurrencias x xs) es el número de veces que ocurre el carácter x en
-- la cadena xs. Por ejemplo, 
--    ocurrencias 'a' "Salamanca"  ==>  4  
ocurrencias :: Char -> String -> Int
ocurrencias x xs = length [x1 | x1 <- xs, x == x1]

-- (porcentaje n m) es el porcentaje de n sobre m. Por ejemplo,
--    porcentaje 2 5  ==>  40.0
porcentaje :: Int -> Int -> Float
porcentaje n m = (fromIntegral n / fromIntegral m) * 100

-- (frecuencias xs) es la frecuencia de cada una de las minúsculas de la
-- cadena xs. Por ejemplo, 
--    > frecuencias "en todo la medida"
--    [14.3,0,0,21.4,14.3,0,0,0,7.1,0,0,7.1,
--     7.1,7.1,14.3,0,0,0,0,7.1,0,0,0,0,0,0]
frecuencias :: String -> [Float]
frecuencias xs = 
    [porcentaje (ocurrencias x xs) n | x <- ['a'..'z']]
    where n = length (minusculas xs)

-- (chiCuadrado os es) es la medida chi cuadrado de la discrepancia
-- entre la distribución observada os y la esperada es. Por ejemplo,
--    chiCuadrado [3,5,6] [3,5,6]  ==>  0.0
--    chiCuadrado [3,5,6] [5,6,3]  ==>  3.9666667
chiCuadrado :: [Float] -> [Float] -> Float
chiCuadrado os es = sum [((o - e) ^ 2) / e | (o,e) <- zip os es]

-- (rota n xs) es la lista obtenida rotando n posiciones los elementos
-- de la lista xs. Por ejemplo,
--    rota 2 "ramo"  ==>  "mora"
rota :: Int -> [a] -> [a]
rota n xs = drop n xs ++ take n xs

-- (posiciones x xs) es la lista de las posiciones de x en la lista
-- xs. Por ejemplo, 
--    posiciones 'a' "Salamanca"  ==>  [1,3,5,8]
posiciones :: Eq a => a -> [a] -> [Int]
posiciones x xs = [i | (x1,i) <- zip xs [0..], x == x1]

-- (descifra xs) es la cadena obtenida descodificando la cadena xs por
-- el desplazamiento que produce una distribución de minúsculas con
-- la menor deviación chi cuadrado respecto de la tabla de distribución
-- de las vocales en castellano. Por ejemplo, 
--   > descifra "Lt htruqnhfit ij qf anif jx ijxhzgwnw qt xnruqj vzj jx"
--   "Lo complicado de la vida es descubrir lo simple que es"
descifra :: String -> String
descifra xs =  codifica (-factor) xs
    where
      factor = head (posiciones (minimum tabChi) tabChi)
      tabChi = [chiCuadrado (rota n tabla1) tabla | n <- [0..25]]
      tabla1 = frecuencias xs

100

101

102

103

104

105

106

107

108

import Data.Char

-- ---------------------------------------------------------------------

-- Codificación y descodificación --

-- ---------------------------------------------------------------------

-- (let2int c) es el entero correspondiente a la letra minúscula c. Por

-- ejemplo,

-- let2int 'a' ==> 0

-- let2int 'd' ==> 3

-- let2int 'z' ==> 25

let2int :: Char -> Int

let2int c = ord c - ord 'a'

-- (int2let n) es la letra minúscula correspondiente al entero n. Por

-- ejemplo,

-- int2let 0 ==> 'a'

-- int2let 3 ==> 'd'

-- int2let 25 ==> 'z'

int2let :: Int -> Char

int2let n = chr (ord 'a' + n)

-- (desplaza n c) es el carácter obtenido desplazando n caracteres el

-- carácter c. Por ejemplo,

-- desplaza 3 'a' ==> 'd'

-- desplaza 3 'y' ==> 'b'

-- desplaza (-3) 'd' ==> 'a'

-- desplaza (-3) 'b' ==> 'y'

desplaza :: Int -> Char -> Char

desplaza n c | isLower c = int2let ((let2int c + n) `mod` 26)

| otherwise = c

-- (codifica n xs) es el resultado de codificar el texto xs con un

-- desplazamiento n. Por ejemplo,

-- codifica 3 "En todo la medida" ==> "Eq wrgr od phglgd"

-- codifica (-3) "Eq wrgr od phglgd" ==> "En todo la medida"

codifica :: Int -> String -> String

codifica n xs = [desplaza n x | x <- xs]

-- ---------------------------------------------------------------------

-- Análisis de frecuencia --

-- ---------------------------------------------------------------------

-- tabla es la lista de la frecuencias de las letras en castellano, Por

-- ejemplo, la frecuencia de la 'a' es del 12.53%, la de la 'b' es 1.42%.

tabla :: [Float]

tabla = [12.53, 1.42, 4.68, 5.86, 13.68, 0.69, 1.01, 0.70, 6.25,

0.44, 0.01, 4.97, 3.15, 6.71, 8.68, 2.51, 0.88, 6.87,

7.98, 4.63, 3.93, 0.90, 0.02, 0.22, 0.90, 0.52]

-- (minusculas xs) es la lista de minúsculas en la cadena xs. Por

-- ejemplo,

-- minusculas "EstoEsUnaPrueba" ==> "stosnarueba"

minusculas :: String -> String

minusculas xs = [x | x <- xs, isLower x]

-- (ocurrencias x xs) es el número de veces que ocurre el carácter x en

-- la cadena xs. Por ejemplo,

-- ocurrencias 'a' "Salamanca" ==> 4

ocurrencias :: Char -> String -> Int

ocurrencias x xs = length [x1 | x1 <- xs, x == x1]

-- (porcentaje n m) es el porcentaje de n sobre m. Por ejemplo,

-- porcentaje 2 5 ==> 40.0

porcentaje :: Int -> Int -> Float

porcentaje n m = (fromIntegral n / fromIntegral m) * 100

-- (frecuencias xs) es la frecuencia de cada una de las minúsculas de la

-- cadena xs. Por ejemplo,

-- > frecuencias "en todo la medida"

-- [14.3,0,0,21.4,14.3,0,0,0,7.1,0,0,7.1,

-- 7.1,7.1,14.3,0,0,0,0,7.1,0,0,0,0,0,0]

frecuencias :: String -> [Float]

frecuencias xs =

[porcentaje (ocurrencias x xs) n | x <- ['a'..'z']]

where n = length (minusculas xs)

-- (chiCuadrado os es) es la medida chi cuadrado de la discrepancia

-- entre la distribución observada os y la esperada es. Por ejemplo,

-- chiCuadrado [3,5,6] [3,5,6] ==> 0.0

-- chiCuadrado [3,5,6] [5,6,3] ==> 3.9666667

chiCuadrado :: [Float] -> [Float] -> Float

chiCuadrado os es = sum [((o - e) ^ 2) / e | (o,e) <- zip os es]

-- (rota n xs) es la lista obtenida rotando n posiciones los elementos

-- de la lista xs. Por ejemplo,

-- rota 2 "ramo" ==> "mora"

rota :: Int -> [a] -> [a]

rota n xs = drop n xs ++ take n xs

-- (posiciones x xs) es la lista de las posiciones de x en la lista

-- xs. Por ejemplo,

-- posiciones 'a' "Salamanca" ==> [1,3,5,8]

posiciones :: Eq a => a -> [a] -> [Int]

posiciones x xs = [i | (x1,i) <- zip xs [0..], x == x1]

-- (descifra xs) es la cadena obtenida descodificando la cadena xs por

-- el desplazamiento que produce una distribución de minúsculas con

-- la menor deviación chi cuadrado respecto de la tabla de distribución

-- de las vocales en castellano. Por ejemplo,

-- > descifra "Lt htruqnhfit ij qf anif jx ijxhzgwnw qt xnruqj vzj jx"

-- "Lo complicado de la vida es descubrir lo simple que es"

descifra :: String -> String

descifra xs = codifica (-factor) xs

where

factor = head (posiciones (minimum tabChi) tabChi)

tabChi = [chiCuadrado (rota n tabla1) tabla | n <- [0..25]]

tabla1 = frecuencias xs

Las transparencias usadas en la clase son las comprendidas entre las páginas 14 y 29 del tema 5

Se puede imprimir o compartir con