La codificaci\u00f3n por longitud, o comprensi\u00f3n RLE (del ingl\u00e9s, “Run-length encoding”), es una compresi\u00f3n de datos en la que secuencias de datos con el mismo valor consecutivas son almacenadas como un \u00fanico valor m\u00e1s su recuento. Por ejemplo, la cadena<\/p>\n
\r\nBBBBBBBBBBBBNBBBBBBBBBBBBNNNBBBBBBBBBBBBBBBBBBBBBBBBNBBBBBBBBBBBBBB\r\n<\/pre>\nse codifica por <\/p>\n
\r\n12B1N12B3N24B1N14B\r\n<\/pre>\nInterpretado esto como 12 letras B, 1 letra N , 12 letras B, 3 letras N, etc.<\/p>\n
En los siguientes ejercicios se definir\u00e1n funciones para codificar y descodificar por longitud y comprobar que son operaciones inversas.
\n<\/p>\n
\r\n-- ---------------------------------------------------------------------\r\n-- \u00a7 Librer\u00edas auxiliares --\r\n-- ---------------------------------------------------------------------\r\n\r\nimport Data.Char (isNumber)\r\nimport Data.List (group)\r\nimport Test.QuickCheck\r\n\r\n-- ---------------------------------------------------------------------\r\n-- \u00a7 Ejercicios --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1. Una lista se puede comprimir indicando el n\u00famero de\r\n-- veces consecutivas que aparece cada elemento. Por ejemplo, la lista \r\n-- comprimida de [1,1,7,7,7,5,5,7,7,7,7] es [(2,1),(3,7),(2,5),(4,7)],\r\n-- indicando que comienza con dos 1, seguido de tres 7, dos 5 y cuatro\r\n-- 7. \r\n-- \r\n-- Definir la funci\u00f3n\r\n-- comprimida :: Eq a => [a] -> [(Int,a)]\r\n-- tal que (comprimida xs) es la lista obtenida al comprimir por\r\n-- longitud la lista xs. Por ejemplo, \r\n-- ghci> comprimida [1,1,7,7,7,5,5,7,7,7,7]\r\n-- [(2,1),(3,7),(2,5),(4,7)]\r\n-- ghci> comprimida \"BBBBBBBBBBBBNBBBBBBBBBBBBNNNBBBBBBBBBBBBBBBBBBB\"\r\n-- [(12,'B'),(1,'N'),(12,'B'),(3,'N'),(19,'B')]\r\n-- ---------------------------------------------------------------------\r\n\r\n-- 1\u00aa definici\u00f3n (por recursi\u00f3n)\r\ncomprimida :: Eq a => [a] -> [(Int,a)]\r\ncomprimida xs = aux xs 1\r\n where aux (x:y:zs) n | x == y = aux (y:zs) (n+1)\r\n | otherwise = (n,x) : aux (y:zs) 1\r\n aux [x] n = [(n,x)]\r\n\r\n-- 2\u00aa definici\u00f3n (por recursi\u00f3n usando takeWhile):\r\ncomprimida2 :: Eq a => [a] -> [(Int,a)]\r\ncomprimida2 [] = []\r\ncomprimida2 (x:xs) = \r\n (1 + length (takeWhile (==x) xs),x) : comprimida2 (dropWhile (==x) xs)\r\n\r\n-- 3\u00aa definici\u00f3n (por comprensi\u00f3n usando group):\r\ncomprimida3 :: Eq a => [a] -> [(Int,a)]\r\ncomprimida3 xs = [(length ys, head ys) | ys <- group xs]\r\n\r\n-- 4\u00aa definici\u00f3n (usando map y group):\r\ncomprimida4 :: Eq a => [a] -> [(Int,a)]\r\ncomprimida4 = map (\\xs -> (length xs, head xs)) . group\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2. Definir la funci\u00f3n\r\n-- expandida :: [(Int,a)] -> [a]\r\n-- tal que (expandida ps) es la lista expandida correspondiente a ps (es\r\n-- decir, es la lista xs tal que la comprimida de xs es ps). Por\r\n-- ejemplo, \r\n-- expandida [(2,1),(3,7),(2,5),(4,7)] == [1,1,7,7,7,5,5,7,7,7,7]\r\n-- ---------------------------------------------------------------------\r\n\r\n-- 1\u00aa definici\u00f3n (por comprensi\u00f3n)\r\nexpandida :: [(Int,a)] -> [a]\r\nexpandida ps = concat [replicate k x | (k,x) <- ps]\r\n\r\n-- 2\u00aa definici\u00f3n (por concatMap)\r\nexpandida2 :: [(Int,a)] -> [a]\r\nexpandida2 = concatMap (\\(k,x) -> replicate k x) \r\n\r\n-- 3\u00aa definici\u00f3n (por recursi\u00f3n)\r\nexpandida3 :: [(Int,a)] -> [a]\r\nexpandida3 [] = []\r\nexpandida3 ((n,x):ps) = replicate n x ++ expandida3 ps\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3. Comprobar con QuickCheck que dada una lista de enteros,\r\n-- si se la comprime y despu\u00e9s se expande se obtiene la lista inicial. \r\n-- ---------------------------------------------------------------------\r\n\r\n-- La propiedad es\r\nprop_expandida_comprimida :: [Int] -> Bool \r\nprop_expandida_comprimida xs = expandida (comprimida xs) == xs\r\n\r\n-- La propiedad es\r\n-- ghci> quickCheck prop_expandida_comprimida\r\n-- +++ OK, passed 100 tests.\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 4. Comprobar con QuickCheck que dada una lista de pares\r\n-- de enteros, si se la expande y despu\u00e9s se comprime se obtiene la\r\n-- lista inicial. \r\n-- ---------------------------------------------------------------------\r\n\r\n-- La propiedad es\r\nprop_comprimida_expandida :: [(Int,Int)] -> Bool \r\nprop_comprimida_expandida xs = expandida (comprimida xs) == xs\r\n\r\n-- La propiedad es\r\n-- ghci> quickCheck prop_comprimida_expandida\r\n-- +++ OK, passed 100 tests.\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 5. Definir la funci\u00f3n\r\n-- listaAcadena :: [(Int,Char)] -> String\r\n-- tal que (listaAcadena xs) es la cadena correspondiente a la lista de\r\n-- pares de xs. Por ejemplo,\r\n-- ghci> listaAcadena [(12,'B'),(1,'N'),(12,'B'),(3,'N'),(19,'B')]\r\n-- \"12B1N12B3N19B\"\r\n-- ---------------------------------------------------------------------\r\n\r\nlistaAcadena :: [(Int,Char)] -> String\r\nlistaAcadena xs = concat [show n ++ [c] | (n,c) <- xs]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 6. Definir la funci\u00f3n\r\n-- cadenaComprimida :: String -> String\r\n-- tal que (cadenaComprimida cs) es la cadena obtenida comprimiendo por\r\n-- longitud la cadena cs. Por ejemplo,\r\n-- ghci> cadenaComprimida \"BBBBBBBBBBBBNBBBBBBBBBBBBNNNBBBBBBBBBBNNN\"\r\n-- \"12B1N12B3N10B3N\"\r\n-- ---------------------------------------------------------------------\r\n\r\ncadenaComprimida :: String -> String\r\ncadenaComprimida = listaAcadena . comprimida\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 7. Definir la funci\u00f3n \r\n-- cadenaAlista :: String -> [(Int,Char)]\r\n-- tal que (cadenaAlista cs) es la lista de pares correspondientes a la\r\n-- cadena cs. Por ejemplo,\r\n-- ghci> cadenaAlista \"12B1N12B3N10B3N\"\r\n-- [(12,'B'),(1,'N'),(12,'B'),(3,'N'),(10,'B'),(3,'N')]\r\n-- ---------------------------------------------------------------------\r\n\r\ncadenaAlista :: String -> [(Int,Char)]\r\ncadenaAlista [] = []\r\ncadenaAlista cs = (read ns,x) : cadenaAlista xs\r\n where (ns,(x:xs)) = span isNumber cs\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 8. Definir la funci\u00f3n\r\n-- cadenaExpandida :: String -> String\r\n-- tal que (cadenaExpandida cs) es la cadena expandida correspondiente a\r\n-- cs (es decir, es la cadena xs que al comprimirse por longitud da cs). \r\n-- Por ejemplo, \r\n-- ghci> cadenaExpandida \"12B1N12B3N10B3N\"\r\n-- \"BBBBBBBBBBBBNBBBBBBBBBBBBNNNBBBBBBBBBBNNN\"\r\n-- ---------------------------------------------------------------------\r\n\r\ncadenaExpandida :: String -> String\r\ncadenaExpandida = expandida . cadenaAlista\r\n<\/pre>\nDestino<\/b>
\nLa anterior relaci\u00f3n de ejercicios se ha elaborado para <\/p>\n