PeH: Codificación por longitud en Haskell
La codificación por longitud, o comprensión RLE (del inglés, “Run-length encoding”), es una compresión de datos en la que secuencias de datos con el mismo valor consecutivas son almacenadas como un único valor más su recuento. Por ejemplo, la cadena
1 |
BBBBBBBBBBBBNBBBBBBBBBBBBNNNBBBBBBBBBBBBBBBBBBBBBBBBNBBBBBBBBBBBBBB |
se codifica por
1 |
12B1N12B3N24B1N14B |
Interpretado esto como 12 letras B, 1 letra N , 12 letras B, 3 letras N, etc.
En los siguientes ejercicios se definirán funciones para codificar y descodificar por longitud y comprobar que son operaciones inversas.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 |
-- --------------------------------------------------------------------- -- § Librerías auxiliares -- -- --------------------------------------------------------------------- import Data.Char (isNumber) import Data.List (group) import Test.QuickCheck -- --------------------------------------------------------------------- -- § Ejercicios -- -- --------------------------------------------------------------------- -- --------------------------------------------------------------------- -- Ejercicio 1. Una lista se puede comprimir indicando el número de -- veces consecutivas que aparece cada elemento. Por ejemplo, la lista -- comprimida de [1,1,7,7,7,5,5,7,7,7,7] es [(2,1),(3,7),(2,5),(4,7)], -- indicando que comienza con dos 1, seguido de tres 7, dos 5 y cuatro -- 7. -- -- Definir la función -- comprimida :: Eq a => [a] -> [(Int,a)] -- tal que (comprimida xs) es la lista obtenida al comprimir por -- longitud la lista xs. Por ejemplo, -- ghci> comprimida [1,1,7,7,7,5,5,7,7,7,7] -- [(2,1),(3,7),(2,5),(4,7)] -- ghci> comprimida "BBBBBBBBBBBBNBBBBBBBBBBBBNNNBBBBBBBBBBBBBBBBBBB" -- [(12,'B'),(1,'N'),(12,'B'),(3,'N'),(19,'B')] -- --------------------------------------------------------------------- -- 1ª definición (por recursión) comprimida :: Eq a => [a] -> [(Int,a)] comprimida xs = aux xs 1 where aux (x:y:zs) n | x == y = aux (y:zs) (n+1) | otherwise = (n,x) : aux (y:zs) 1 aux [x] n = [(n,x)] -- 2ª definición (por recursión usando takeWhile): comprimida2 :: Eq a => [a] -> [(Int,a)] comprimida2 [] = [] comprimida2 (x:xs) = (1 + length (takeWhile (==x) xs),x) : comprimida2 (dropWhile (==x) xs) -- 3ª definición (por comprensión usando group): comprimida3 :: Eq a => [a] -> [(Int,a)] comprimida3 xs = [(length ys, head ys) | ys <- group xs] -- 4ª definición (usando map y group): comprimida4 :: Eq a => [a] -> [(Int,a)] comprimida4 = map (\xs -> (length xs, head xs)) . group -- --------------------------------------------------------------------- -- Ejercicio 2. Definir la función -- expandida :: [(Int,a)] -> [a] -- tal que (expandida ps) es la lista expandida correspondiente a ps (es -- decir, es la lista xs tal que la comprimida de xs es ps). Por -- ejemplo, -- expandida [(2,1),(3,7),(2,5),(4,7)] == [1,1,7,7,7,5,5,7,7,7,7] -- --------------------------------------------------------------------- -- 1ª definición (por comprensión) expandida :: [(Int,a)] -> [a] expandida ps = concat [replicate k x | (k,x) <- ps] -- 2ª definición (por concatMap) expandida2 :: [(Int,a)] -> [a] expandida2 = concatMap (\(k,x) -> replicate k x) -- 3ª definición (por recursión) expandida3 :: [(Int,a)] -> [a] expandida3 [] = [] expandida3 ((n,x):ps) = replicate n x ++ expandida3 ps -- --------------------------------------------------------------------- -- Ejercicio 3. Comprobar con QuickCheck que dada una lista de enteros, -- si se la comprime y después se expande se obtiene la lista inicial. -- --------------------------------------------------------------------- -- La propiedad es prop_expandida_comprimida :: [Int] -> Bool prop_expandida_comprimida xs = expandida (comprimida xs) == xs -- La propiedad es -- ghci> quickCheck prop_expandida_comprimida -- +++ OK, passed 100 tests. -- --------------------------------------------------------------------- -- Ejercicio 4. Comprobar con QuickCheck que dada una lista de pares -- de enteros, si se la expande y después se comprime se obtiene la -- lista inicial. -- --------------------------------------------------------------------- -- La propiedad es prop_comprimida_expandida :: [(Int,Int)] -> Bool prop_comprimida_expandida xs = expandida (comprimida xs) == xs -- La propiedad es -- ghci> quickCheck prop_comprimida_expandida -- +++ OK, passed 100 tests. -- --------------------------------------------------------------------- -- Ejercicio 5. Definir la función -- listaAcadena :: [(Int,Char)] -> String -- tal que (listaAcadena xs) es la cadena correspondiente a la lista de -- pares de xs. Por ejemplo, -- ghci> listaAcadena [(12,'B'),(1,'N'),(12,'B'),(3,'N'),(19,'B')] -- "12B1N12B3N19B" -- --------------------------------------------------------------------- listaAcadena :: [(Int,Char)] -> String listaAcadena xs = concat [show n ++ [c] | (n,c) <- xs] -- --------------------------------------------------------------------- -- Ejercicio 6. Definir la función -- cadenaComprimida :: String -> String -- tal que (cadenaComprimida cs) es la cadena obtenida comprimiendo por -- longitud la cadena cs. Por ejemplo, -- ghci> cadenaComprimida "BBBBBBBBBBBBNBBBBBBBBBBBBNNNBBBBBBBBBBNNN" -- "12B1N12B3N10B3N" -- --------------------------------------------------------------------- cadenaComprimida :: String -> String cadenaComprimida = listaAcadena . comprimida -- --------------------------------------------------------------------- -- Ejercicio 7. Definir la función -- cadenaAlista :: String -> [(Int,Char)] -- tal que (cadenaAlista cs) es la lista de pares correspondientes a la -- cadena cs. Por ejemplo, -- ghci> cadenaAlista "12B1N12B3N10B3N" -- [(12,'B'),(1,'N'),(12,'B'),(3,'N'),(10,'B'),(3,'N')] -- --------------------------------------------------------------------- cadenaAlista :: String -> [(Int,Char)] cadenaAlista [] = [] cadenaAlista cs = (read ns,x) : cadenaAlista xs where (ns,(x:xs)) = span isNumber cs -- --------------------------------------------------------------------- -- Ejercicio 8. Definir la función -- cadenaExpandida :: String -> String -- tal que (cadenaExpandida cs) es la cadena expandida correspondiente a -- cs (es decir, es la cadena xs que al comprimirse por longitud da cs). -- Por ejemplo, -- ghci> cadenaExpandida "12B1N12B3N10B3N" -- "BBBBBBBBBBBBNBBBBBBBBBBBBNNNBBBBBBBBBBNNN" -- --------------------------------------------------------------------- cadenaExpandida :: String -> String cadenaExpandida = expandida . cadenaAlista |
Destino
La anterior relación de ejercicios se ha elaborado para
- la asignatura de Informática de 1º del Grado en Matemáticas y
- la ampliación del libro Piensa en Haskell.
Fuentes
- Wikipedia. Run-length encoding.