{"id":5228,"date":"2015-12-18T13:42:27","date_gmt":"2015-12-18T12:42:27","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=5228"},"modified":"2015-12-18T13:42:27","modified_gmt":"2015-12-18T12:42:27","slug":"i1m2015-aplicaciones-de-la-programacion-funcional-con-listas-infinitas","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2015-aplicaciones-de-la-programacion-funcional-con-listas-infinitas\/","title":{"rendered":"I1M2015: Aplicaciones de la programaci\u00f3n funcional con listas infinitas"},"content":{"rendered":"<p>En clase de hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-15\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> hemos comentando las soluciones de los 8 primeros ejercicios de evaluaci\u00f3n de la 14\u00aa relaci\u00f3n sobre aplicaciones de la programaci\u00f3n funcional con listas infinitas.<\/p>\n<p>Los ejercicios, y sus soluciones, se muestran a continuaci\u00f3n.<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\n-- ---------------------------------------------------------------------\n-- Introducci\u00f3n                                                       --\n-- ---------------------------------------------------------------------\n\n-- En esta relaci\u00f3n se estudia distintas aplicaciones de la programaci\u00f3n\n-- funcional que usan listas infinitas\n-- + la sucesi\u00f3n de Hamming,\n-- + problemas 10 y 12 del proyecto Euler,\n-- + enumeraci\u00f3n de los n\u00fameros enteros,\n-- + el problema de la bicicleta de Turing,\n-- + la sucesi\u00f3n de Golomb,\n-- + la codificaci\u00f3n por longitud,\n-- + la sucesi\u00f3n de Kolakoski y\n-- + el tri\u00e1ngulo de Floyd.\n\n-- ---------------------------------------------------------------------\n-- Importaci\u00f3n de librer\u00edas                                           --\n-- ---------------------------------------------------------------------\n\nimport Data.Char \nimport Data.List\nimport Data.Numbers.Primes\nimport Test.QuickCheck\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Sucesi\u00f3n de Hamming                                              --\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1.1. Definir la funci\u00f3n\n--    divisoresPrimosEn :: Integer -> [Integer] -> Bool\n-- tal que (divisoresPrimosEn x ys) se verifica si x puede expresarse\n-- como un producto de potencias de elementos de la lista de n\u00fameros\n-- primos ys. Por ejemplo, \n--    divisoresPrimosEn 12 [2,3,5]  ==  True\n--    divisoresPrimosEn 14 [2,3,5]  ==  False\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa definici\u00f3n (por recursi\u00f3n)\ndivisoresPrimosEn1 :: Integer -> [Integer] -> Bool\ndivisoresPrimosEn1 1 _  = True\ndivisoresPrimosEn1 x [] = False\ndivisoresPrimosEn1 x (y:ys) \n    | mod x y == 0 = divisoresPrimosEn1 (div x y) (y:ys)\n    | otherwise    = divisoresPrimosEn1 x ys   \n\n-- 2\u00aa definici\u00f3n (por comprensi\u00f3n)\ndivisoresPrimosEn2 :: Integer -> [Integer] -> Bool\ndivisoresPrimosEn2 x ys = and [elem y ys | y <- primeFactors x] \n\n-- 3\u00aa definici\u00f3n (por cuantificaci\u00f3n)\ndivisoresPrimosEn :: Integer -> [Integer] -> Bool\ndivisoresPrimosEn x ys = all (`elem` ys) (primeFactors x) \n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1.2. Los n\u00fameros de Hamming forman una sucesi\u00f3n \n-- estrictamente creciente de n\u00fameros que cumplen las siguientes \n-- condiciones: \n--    1. El n\u00famero 1 est\u00e1 en la sucesi\u00f3n.\n--    2. Si x est\u00e1 en la sucesi\u00f3n, entonces 2x, 3x y 5x tambi\u00e9n est\u00e1n.\n--    3. Ning\u00fan otro n\u00famero est\u00e1 en la sucesi\u00f3n.\n-- Definir, usando divisoresPrimosEn, la constante\n--    hamming :: [Integer]\n-- tal que hamming es la sucesi\u00f3n de Hamming. Por ejemplo,\n--    take 12 hamming  ==  [1,2,3,4,5,6,8,9,10,12,15,16]\n-- ---------------------------------------------------------------------\n\nhamming :: [Integer]\nhamming = [x | x <- [1..], divisoresPrimosEn x [2,3,5]]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1.3. Definir la funci\u00f3n\n--    cantidadHammingMenores :: Integer -> Int\n-- tal que (cantidadHammingMenores x) es la cantidad de n\u00fameros de\n-- Hamming menores que x. Por ejemplo,\n--    cantidadHammingMenores 6  ==  5\n--    cantidadHammingMenores 7  ==  6\n--    cantidadHammingMenores 8  ==  6\n-- ---------------------------------------------------------------------\n\ncantidadHammingMenores :: Integer -> Int\ncantidadHammingMenores x = length (takeWhile (<x) hamming)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1.4. Definir la funci\u00f3n\n--    siguienteHamming :: Integer -> Integer\n-- tal que (siguienteHamming x) es el menor n\u00famero de la sucesi\u00f3n de\n-- Hamming mayor que x. Por ejemplo,\n--    siguienteHamming 6  ==  8\n--    siguienteHamming 21  ==  24\n-- ---------------------------------------------------------------------\n\nsiguienteHamming :: Integer -> Integer\nsiguienteHamming x = head (dropWhile (<=x) hamming)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1.5. Definir la funci\u00f3n\n--    huecoHamming :: Integer -> [(Integer,Integer)]\n-- tal que (huecoHamming n) es la lista de pares de n\u00fameros consecutivos\n-- en la sucesi\u00f3n de Hamming cuya distancia es mayor que n. Por ejemplo,  \n--    take 4 (huecoHamming 2)   ==  [(12,15),(20,24),(27,30),(32,36)]\n--    take 3 (huecoHamming 2)   ==  [(12,15),(20,24),(27,30)]\n--    take 2 (huecoHamming 3)   ==  [(20,24),(32,36)]\n--    head (huecoHamming 10)    ==  (108,120)\n--    head (huecoHamming 1000)  ==  (34992,36000)\n-- ---------------------------------------------------------------------\n\nhuecoHamming :: Integer -> [(Integer,Integer)]\nhuecoHamming n = [(x,y) | x <- hamming, \n                          let y = siguienteHamming x,\n                          y-x > n]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1.6. Comprobar con QuickCheck que para todo n, existen\n-- pares de n\u00fameros consecutivos en la sucesi\u00f3n de Hamming cuya\n-- distancia es mayor que n.\n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_Hamming :: Integer -> Bool\nprop_Hamming n = huecoHamming n' \/= []\n    where n' = abs n\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_Hamming\n--    OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Problema 10 del Proyecto Euler                                   --\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2. Definir la funci\u00f3n \n--    sumaPrimoMenores :: Integer -> Integer\n-- tal que (sumaPrimoMenores n) es la suma de los primos menores que\n-- n. Por ejemplo,\n--    sumaPrimoMenores 10  ==  17\n--    sumaPrimoMenores 7   ==  10                       \n-- ---------------------------------------------------------------------\n\n-- 1\u00aa definici\u00f3n (por recursi\u00f3n y la criba de Erast\u00f3tenes)\n-- =======================================================\n\nsumaPrimoMenores1 :: Integer -> Integer\nsumaPrimoMenores1 n = sumaMenores n primos 0\n   where sumaMenores n (x:xs) a | n <= x    = a\n                                | otherwise = sumaMenores n xs (a+x)\n\n-- primos es la lista de los n\u00famero primos obtenida mediante la criba de \n-- Erast\u00f3tenes. Por ejemplo,\n--    primos  =>  [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,...\nprimos :: [Integer]\nprimos = criba [2..]\n         where criba (p:ps) = p : criba [n | n<-ps, mod n p \/= 0]\n\n-- 2\u00aa definici\u00f3n (por comprensi\u00f3n y la criba de Erast\u00f3tenes)\n-- =========================================================\n\nsumaPrimoMenores2 :: Integer -> Integer\nsumaPrimoMenores2 n = sum (takeWhile (<n) primos)\n\n-- 3\u00aa definici\u00f3n (por comprensi\u00f3n y la librer\u00eda de primos)\n-- =======================================================\n\nsumaPrimoMenores3 :: Integer -> Integer\nsumaPrimoMenores3 n = sum (takeWhile (<n) primes)\n\n-- Comparaci\u00f3n de eficiencia \n-- =========================\n\n--    \u03bb> sumaPrimoMenores1 20000\n--    21171191\n--    (5.11 secs, 922,508,496 bytes)\n--    \n--    \u03bb> sumaPrimoMenores2 20000\n--    21171191\n--    (5.05 secs, 898,081,952 bytes)\n--    \n--    \u03bb> sumaPrimoMenores3 20000\n--    21171191\n--    (0.02 secs, 0 bytes)\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Problema 12 del Proyecto Euler                                   --\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3.1. Los n\u00fameros triangulares se forman como sigue\n--    *     *      * \n--         * *    * *\n--               * * *\n--    1     3      6\n-- \n-- La sucesi\u00f3n de los n\u00fameros triangulares se obtiene sumando los\n-- n\u00fameros naturales. As\u00ed, los 5 primeros n\u00fameros triangulares son\n--     1 = 1\n--     3 = 1+2\n--     6 = 1+2+3\n--    10 = 1+2+3+4\n--    15 = 1+2+3+4+5\n-- \n-- Definir la funci\u00f3n\n--    triangulares :: [Integer]\n-- tal que triangulares es la lista de los n\u00fameros triangulares. Por\n-- ejemplo, \n--    take 10 triangulares     ==  [1,3,6,10,15,21,28,36,45,55]\n--    triangulares !! 2000000  ==  2000003000001\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa definici\u00f3n\ntriangulares1 :: [Integer]\ntriangulares1 = 1 : [x+y | (x,y) <- zip [2..] triangulares]\n\n-- 2\u00aa definici\u00f3n\ntriangulares2 :: [Integer]\ntriangulares2 = scanl (+) 1 [2..]\n\n-- 3\u00aa definici\u00f3n (usando la f\u00f3rmula de la suma de la progresi\u00f3n):\ntriangulares3 :: [Integer]\ntriangulares3 = [(n*(n+1)) `div` 2 | n <- [1..]]\n\n-- Comparaci\u00f3n de eficiencia\n--    \u03bb> triangulares1 !! 1000000\n--    500001500001\n--    (3.07 secs, 484,321,192 bytes)\n--    \u03bb> triangulares2 !! 1000000\n--    500001500001\n--    (0.04 secs, 0 bytes)\n--    \u03bb> triangulares3 !! 1000000\n--    500001500001\n--    (1.23 secs, 186,249,472 bytes)\n\n-- En lo sucesivo, usaremos como triangulares la segunda definici\u00f3n.\ntriangulares :: [Integer]\ntriangulares = triangulares2\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3.2. Definir la funci\u00f3n\n--    nDivisores :: Integer -> Integer\n-- tal que (nDivisores n) es el n\u00famero de los divisores de n. Por\n-- ejemplo, \n--    nDivisores 28                 ==  6\n--    nDivisores (product [1..200]) == 139503973313460993785856000000\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa definici\u00f3n\n-- =============\n\nnDivisores1 :: Integer -> Integer\nnDivisores1 = genericLength . divisores \n\n-- (divisores n) es la lista de los divisores de n. Por ejemplo,\n--    divisores 28  ==  [1,2,4,7,14,28]\ndivisores :: Integer -> [Integer]\ndivisores x = [y | y <- [1..x], mod x y == 0]\n\n-- 2\u00aa definici\u00f3n (con primeFactors y group)\n-- ========================================\n\nnDivisores2 :: Integer -> Integer\nnDivisores2 n = \n    product [1 + genericLength xs | xs <- group (primeFactors n)]\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n--    \u03bb> nDivisores1 (product [1..10])\n--    270\n--    (5.18 secs, 763,249,336 bytes)\n--    \u03bb> nDivisores2 (product [1..10])\n--    270\n--    (0.01 secs, 0 bytes)\n\n-- En lo sucesivo usaremos la 2\u00aa definici\u00f3n de nDivisores\nnDivisores :: Integer -> Integer\nnDivisores = nDivisores2\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3.3. Los divisores de los primeros 7 n\u00fameros triangulares\n-- son: \n--     1: 1\n--     3: 1,3\n--     6: 1,2,3,6\n--    10: 1,2,5,10\n--    15: 1,3,5,15\n--    21: 1,3,7,21\n--    28: 1,2,4,7,14,28\n-- Como se puede observar, 28 es el menor n\u00famero triangular con m\u00e1s de 5\n-- divisores. \n-- \n-- Definir la funci\u00f3n \n--    euler12 :: Int -> Integer\n-- tal que (euler12 n) es el menor n\u00famero triangular con m\u00e1s de n\n-- divisores. Por ejemplo,\n--    euler12 5    ==  28\n--    euler12 500  ==  76576500\n-- ---------------------------------------------------------------------\n\neuler12 :: Integer -> Integer\neuler12 n = head [x | x <- triangulares, nDivisores x > n]\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Enumeraci\u00f3n de los n\u00fameros enteros                               --\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4.1. Los n\u00fameros enteros se pueden ordenar como sigue \n--    0, -1, 1, -2, 2, -3, 3, -4, 4, -5, 5, -6, 6, -7, 7, ...\n-- Definir, por comprensi\u00f3n, la constante\n--    enteros :: [Int]\n-- tal que enteros es la lista de los enteros con la ordenaci\u00f3n\n-- anterior. Por ejemplo,\n--    take 10 enteros  ==  [0,-1,1,-2,2,-3,3,-4,4,-5]\n-- ---------------------------------------------------------------------\n\nenteros :: [Int]\nenteros = 0 : concat [[-x,x] | x <- [1..]]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4.2. Definir, por iteraci\u00f3n, la constante\n--    enteros' :: [Int]\n-- tal que enteros' es la lista de los enteros con la ordenaci\u00f3n\n-- anterior. Por ejemplo,\n--    take 10 enteros  ==  [0,-1,1,-2,2,-3,3,-4,4,-5]\n-- ---------------------------------------------------------------------\n\nenteros' :: [Int]\nenteros' = iterate siguiente 0\n    where siguiente x | x >= 0    = -x-1\n                      | otherwise = -x\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4.3. Definir, por selecci\u00f3n con takeWhile, la funci\u00f3n\n--    posicion :: Int -> Int\n-- tal que (posicion x) es la posici\u00f3n del entero x en la ordenaci\u00f3n\n-- anterior. Por ejemplo,\n--    posicion 2  ==  4\n-- ---------------------------------------------------------------------\n\nposicion :: Int -> Int\nposicion x = length (takeWhile (\/=x) enteros)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4.4. Definir, por recursi\u00f3n, la funci\u00f3n\n--    posicionR :: Int -> Int\n-- tal que (posicionR x) es la posici\u00f3n del entero x en la ordenaci\u00f3n\n-- anterior. Por ejemplo,\n--    posicionR 2  ==  4\n-- ---------------------------------------------------------------------\n\nposicionR :: Int -> Int\nposicionR x = aux enteros 0\n    where aux (y:ys) n | x == y    = n\n                       | otherwise = aux ys (n+1)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4.5. Definir, por comprensi\u00f3n, la funci\u00f3n\n--    posicionC :: Int -> Int\n-- tal que (posicionC x) es la posici\u00f3n del entero x en la ordenaci\u00f3n\n-- anterior. Por ejemplo,\n--    posicionC 2  ==  4\n-- ---------------------------------------------------------------------\n\nposicionC :: Int -> Int\nposicionC x = head [n | (n,y) <- zip [0..] enteros, y == x]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4.6. Definir, sin b\u00fasqueda, la funci\u00f3n\n--    posicion2 :: Int -> Int\n-- tal que (posicion2 x) es la posici\u00f3n del entero x en la ordenaci\u00f3n\n-- anterior. Por ejemplo,\n--    posicion2 2  ==  4\n-- ---------------------------------------------------------------------\n\n-- Definici\u00f3n directa\nposicion2 :: Int -> Int\nposicion2 x | x >= 0    = 2*x\n            | otherwise = 2*(-x)-1\n\n-- ---------------------------------------------------------------------\n-- \u00a7 El problema de la bicicleta de Turing                            --\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 5.1. Cuentan que Alan Turing ten\u00eda una bicicleta vieja,\n-- que ten\u00eda una cadena con un eslab\u00f3n d\u00e9bil y adem\u00e1s uno de los radios\n-- de la rueda estaba doblado. Cuando el radio doblado coincid\u00eda con el\n-- eslab\u00f3n d\u00e9bil, entonces la cadena se romp\u00eda.   \n--\n-- La bicicleta se identifica por los par\u00e1metros (i,d,n) donde \n-- - i es el n\u00famero del eslab\u00f3n que coincide con el radio doblado al\n--   empezar a andar,\n-- - d es el n\u00famero de eslabones que se desplaza la cadena en cada\n--   vuelta de la rueda y  \n-- - n es el n\u00famero de eslabones de la cadena (el n\u00famero n es el d\u00e9bil).\n-- Si i=2 y d=7 y n=25, entonces la lista con el n\u00famero de eslab\u00f3n que \n-- toca el radio doblado en cada vuelta es \n--    [2,9,16,23,5,12,19,1,8,15,22,4,11,18,0,7,14,21,3,10,17,24,6,...\n-- Con lo que la cadena se rompe en la vuelta n\u00famero 14.\n-- \n-- Definir la funci\u00f3n\n--    eslabones :: Int -> Int -> Int -> [Int]\n-- tal que (eslabones i d n) es la lista con los n\u00fameros de eslabones \n-- que tocan el radio doblado en cada vuelta en una bicicleta de tipo \n-- (i,d,n). Por ejemplo, \n--    take 10 (eslabones 2 7 25)  ==  [2,9,16,23,5,12,19,1,8,15]\n-- ---------------------------------------------------------------------\n\neslabones :: Int -> Int -> Int -> [Int]\neslabones i d n = [(i+d*j) `mod` n | j <- [0..]]\n\n-- 2\u00aa definici\u00f3n (con iterate):\neslabones2 :: Int -> Int -> Int -> [Int]\neslabones2 i d n = map (\\x-> mod x n) (iterate (+d) i)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 5.2. Definir la funci\u00f3n\n--    numeroVueltas :: Int -> Int -> Int -> Int \n-- tal que (numeroVueltas i d n) es el n\u00famero de vueltas que pasar\u00e1n \n-- hasta que la cadena se rompa en una bicicleta de tipo (i,d,n). Por \n-- ejemplo,\n--    numeroVueltas 2 7 25  ==  14\n-- ---------------------------------------------------------------------\n\nnumeroVueltas :: Int -> Int -> Int -> Int\nnumeroVueltas i d n = length (takeWhile (\/=0) (eslabones i d n)) \n\n-- ---------------------------------------------------------------------\n-- \u00a7 La sucesi\u00f3n de Golomb                                            --\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 6.1. [Basado en el problema 341 del proyecto Euler]. La\n-- sucesi\u00f3n de Golomb {G(n)} es una sucesi\u00f3n auto descriptiva: es la\n-- \u00fanica sucesi\u00f3n no decreciente de n\u00fameros naturales tal que el n\u00famero\n-- n aparece G(n) veces en la sucesi\u00f3n. Los valores de G(n) para los\n-- primeros n\u00fameros son los siguientes:\n--    n       1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ...\n--    G(n)    1 2 2 3 3 4 4 4 5  5  5  6  6  6  6 ...\n-- En los apartados de este ejercicio se definir\u00e1 una funci\u00f3n para\n-- calcular los t\u00e9rminos de la sucesi\u00f3n de Golomb. \n-- \n-- Definir la funci\u00f3n\n--    golomb :: Int -> Int\n-- tal que (golomb n) es el n-\u00e9simo t\u00e9rmino de la sucesi\u00f3n de Golomb. \n-- Por ejemplo,\n--    golomb 5  ==  3\n--    golomb 9  ==  5\n-- Indicaci\u00f3n: Se puede usar la funci\u00f3n sucGolomb del apartado 2.\n-- ---------------------------------------------------------------------\n\ngolomb :: Int -> Int\ngolomb n = sucGolomb !! (n-1)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 6.2. Definir la funci\u00f3n\n--    sucGolomb :: [Int]\n-- tal que sucGolomb es la lista de los t\u00e9rminos de la sucesi\u00f3n de\n-- Golomb. Por ejemplo,\n--    take 15 sucGolomb  ==  [1,2,2,3,3,4,4,4,5,5,5,6,6,6,6]\n-- Indicaci\u00f3n: Se puede usar la funci\u00f3n subSucGolomb del apartado 3.\n-- ---------------------------------------------------------------------\n\nsucGolomb :: [Int]\nsucGolomb = subSucGolomb 1\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 6.3. Definir la funci\u00f3n\n--    subSucGolomb :: Int -> [Int]\n-- tal que (subSucGolomb x) es la lista de los t\u00e9rminos de la sucesi\u00f3n\n-- de Golomb a partir de la primera ocurrencia de x. Por ejemplo,\n--    take 10 (subSucGolomb 4)  ==  [4,4,4,5,5,5,6,6,6,6]\n-- Indicaci\u00f3n: Se puede usar la funci\u00f3n golomb del apartado 1.\n-- ---------------------------------------------------------------------\n\nsubSucGolomb :: Int -> [Int]\nsubSucGolomb 1 = [1] ++ subSucGolomb 2\nsubSucGolomb 2 = [2,2] ++ subSucGolomb 3\nsubSucGolomb x = (replicate (golomb x) x) ++ subSucGolomb (x+1) \n\n-- Nota: La sucesi\u00f3n de Golomb puede definirse de forma m\u00e1s compacta\n-- como se muestra a continuaci\u00f3n.\nsucGolomb2 :: [Int]\nsucGolomb2 = 1 : 2 : 2 : g 3\n    where g x      = replicate (golomb x) x ++ g (x+1) \n          golomb n = sucGolomb !! (n-1)\n\n\nsucGolomb3 :: [Int]\nsucGolomb3 = 1 : 2 : 2 : \n              concat [replicate n k | (n,k) <-zip (drop 2 sucGolomb3) [3..]]\n\n-- ---------------------------------------------------------------------\n-- \u00a7 La codificaci\u00f3n por longitud                                     --\n-- ---------------------------------------------------------------------\n\n-- La codificaci\u00f3n por longitud, o comprensi\u00f3n RLE (del ingl\u00e9s,\n-- \"Run-length encoding\"), es una compresi\u00f3n de datos en la que\n-- secuencias de datos con el mismo valor consecutivas son almacenadas\n-- como un \u00fanico valor m\u00e1s su recuento. Por ejemplo, la cadena \n--    BBBBBBBBBBBBNBBBBBBBBBBBBNNNBBBBBBBBBBBBBBBBBBBBBBBBNBBBBBBBBBBBBBB\n-- se codifica por \n--    12B1N12B3N24B1N14B\n-- Interpretado esto como 12 letras B, 1 letra N , 12 letras B, 3 letras\n-- N, etc.\n-- \n-- En los siguientes ejercicios se definir\u00e1n funciones para codificar y\n-- descodificar por longitud.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 7.1. Una lista se puede comprimir indicando el n\u00famero de\n-- veces consecutivas que aparece cada elemento. Por ejemplo, la lista \n-- comprimida de [1,1,7,7,7,5,5,7,7,7,7] es [(2,1),(3,7),(2,5),(4,7)],\n-- indicando que comienza con dos 1, seguido de tres 7, dos 5 y cuatro\n-- 7. \n-- \n-- Definir la funci\u00f3n\n--    comprimida :: Eq a => [a] -> [(Int,a)]\n-- tal que (comprimida xs) es la lista obtenida al comprimir por\n-- longitud la lista xs. Por ejemplo, \n--    ghci> comprimida [1,1,7,7,7,5,5,7,7,7,7]\n--    [(2,1),(3,7),(2,5),(4,7)]\n--    ghci> comprimida \"BBBBBBBBBBBBNBBBBBBBBBBBBNNNBBBBBBBBBBBBBBBBBBB\"\n--    [(12,'B'),(1,'N'),(12,'B'),(3,'N'),(19,'B')]\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa definici\u00f3n (por recursi\u00f3n)\ncomprimida :: Eq a => [a] -> [(Int,a)]\ncomprimida xs = aux xs 1\n    where aux (x:y:zs) n | x == y    = aux (y:zs) (n+1)\n                         | otherwise = (n,x) : aux (y:zs) 1\n          aux [x]      n             = [(n,x)]\n\n-- 2\u00aa definici\u00f3n (por recursi\u00f3n usando takeWhile):\ncomprimida2 :: Eq a => [a] -> [(Int,a)]\ncomprimida2 [] = []\ncomprimida2 (x:xs) = \n    (1 + length (takeWhile (==x) xs),x) : comprimida2 (dropWhile (==x) xs)\n\n-- 3\u00aa definici\u00f3n (por comprensi\u00f3n usando group):\ncomprimida3 :: Eq a => [a] -> [(Int,a)]\ncomprimida3 xs = [(length ys, head ys) | ys <- group xs]\n\n-- 4\u00aa definici\u00f3n (usando map y group):\ncomprimida4 :: Eq a => [a] -> [(Int,a)]\ncomprimida4 = map (\\xs -> (length xs, head xs)) . group\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 7.2. Definir la funci\u00f3n\n--    expandida :: [(Int,a)] -> [a]\n-- tal que (expandida ps) es la lista expandida correspondiente a ps (es\n-- decir, es la lista xs tal que la comprimida de xs es ps). Por\n-- ejemplo, \n--    expandida [(2,1),(3,7),(2,5),(4,7)]  ==  [1,1,7,7,7,5,5,7,7,7,7]\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa definici\u00f3n (por comprensi\u00f3n)\nexpandida :: [(Int,a)] -> [a]\nexpandida ps = concat [replicate k x | (k,x) <- ps]\n\n-- 2\u00aa definici\u00f3n (por concatMap)\nexpandida2 :: [(Int,a)] -> [a]\nexpandida2 = concatMap (\\(k,x) -> replicate k x) \n\n-- 3\u00aa definici\u00f3n (por recursi\u00f3n)\nexpandida3 :: [(Int,a)] -> [a]\nexpandida3 [] = []\nexpandida3 ((n,x):ps) = replicate n x ++ expandida3 ps\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 7.3. Comprobar con QuickCheck que dada una lista de enteros,\n-- si se la comprime y despu\u00e9s se expande se obtiene la lista inicial. \n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_expandida_comprimida :: [Int] -> Bool \nprop_expandida_comprimida xs = expandida (comprimida xs) == xs\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_expandida_comprimida\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 7.4. Comprobar con QuickCheck que dada una lista de pares\n-- de enteros, si se la expande y despu\u00e9s se comprime se obtiene la\n-- lista inicial.  \n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_comprimida_expandida :: [(Int,Int)] -> Bool \nprop_comprimida_expandida xs = expandida (comprimida xs) == xs\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_comprimida_expandida\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 7.5. Definir la funci\u00f3n\n--    listaAcadena :: [(Int,Char)] -> String\n-- tal que (listaAcadena xs) es la cadena correspondiente a la lista de\n-- pares de xs. Por ejemplo,\n--    ghci> listaAcadena [(12,'B'),(1,'N'),(12,'B'),(3,'N'),(19,'B')]\n--    \"12B1N12B3N19B\"\n-- ---------------------------------------------------------------------\n\nlistaAcadena :: [(Int,Char)] -> String\nlistaAcadena xs = concat [show n ++ [c] | (n,c) <- xs]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 7.6. Definir la funci\u00f3n\n--    cadenaComprimida :: String -> String\n-- tal que (cadenaComprimida cs) es la cadena obtenida comprimiendo por\n-- longitud la cadena cs. Por ejemplo,\n--    ghci> cadenaComprimida \"BBBBBBBBBBBBNBBBBBBBBBBBBNNNBBBBBBBBBBNNN\"\n--    \"12B1N12B3N10B3N\"\n-- ---------------------------------------------------------------------\n\ncadenaComprimida :: String -> String\ncadenaComprimida = listaAcadena . comprimida\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 7.7. Definir la funci\u00f3n \n--    cadenaAlista :: String -> [(Int,Char)]\n-- tal que (cadenaAlista cs) es la lista de pares correspondientes a la\n-- cadena cs. Por ejemplo,\n--    ghci> cadenaAlista \"12B1N12B3N10B3N\"\n--    [(12,'B'),(1,'N'),(12,'B'),(3,'N'),(10,'B'),(3,'N')]\n-- ---------------------------------------------------------------------\n\ncadenaAlista :: String -> [(Int,Char)]\ncadenaAlista [] = []\ncadenaAlista cs = (read ns,x) : cadenaAlista xs\n    where (ns,(x:xs)) = span isNumber cs\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 7.8. Definir la funci\u00f3n\n--    cadenaExpandida :: String -> String\n-- tal que (cadenaExpandida cs) es la cadena expandida correspondiente a\n-- cs (es decir, es la cadena xs que al comprimirse por longitud da cs). \n-- Por ejemplo, \n--    ghci> cadenaExpandida \"12B1N12B3N10B3N\"\n--    \"BBBBBBBBBBBBNBBBBBBBBBBBBNNNBBBBBBBBBBNNN\"\n-- ---------------------------------------------------------------------\n\ncadenaExpandida :: String -> String\ncadenaExpandida = expandida . cadenaAlista\n\n-- ---------------------------------------------------------------------\n-- \u00a7 La sucesi\u00f3n de Kolakoski                                         --\n-- ---------------------------------------------------------------------\n\n-- Dada una sucesi\u00f3n, su contadora es la sucesi\u00f3n de las longitudes de\n-- de sus bloque de elementos consecutivos iguales. Por ejemplo, la\n-- sucesi\u00f3n contadora de abbaaabbba es 12331; es decir; 1 vez la a,\n-- 2 la b, 3 la a, 3 la b y 1 la a.\n-- \n-- La sucesi\u00f3n de Kolakoski es una sucesi\u00f3n infinita de los s\u00edmbolos 1 y\n-- 2 que es su propia contadora. Los primeros t\u00e9rminos de la sucesi\u00f3n\n-- de Kolakoski son 1221121221221... que coincide con su contadora (es\n-- decir, 1 vez el 1, 2 veces el 2, 2 veces el 1, ...). \n-- \n-- En esta secci\u00f3n se define la sucesi\u00f3n de Kolakoski.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 8.1. Dados los s\u00edmbolos a y b, la sucesi\u00f3n contadora de\n--    abbaaabbba... =  a bb aaa bbb a ...  \n-- es\n--    1233...       =  1 2  3   3...\n-- es decir; 1 vez la a, 2 la b, 3 la a, 3 la b, 1 la a, ...\n-- \n-- Definir la funci\u00f3n\n--    contadora :: Eq a => [a] -> [Int]\n-- tal que (contadora xs) es la sucesi\u00f3n contadora de xs. Por ejemplo,\n--    contadora \"abbaaabbb\"        ==  [1,2,3,3]\n--    contadora \"122112122121121\"  ==  [1,2,2,1,1,2,1,1,2,1,1]\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa definici\u00f3n (usando group definida en Data.List)\ncontadora :: Eq a => [a] -> [Int]\ncontadora xs = map length (group xs)\n\n-- 2\u00aa definici\u00f3n (por recursi\u00f3n sin group):\ncontadora2 :: Eq a => [a] -> [Int]\ncontadora2 [] = []\ncontadora2 ys@(x:xs) = \n    length (takeWhile (==x) ys) : contadora2 (dropWhile (==x) xs)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 8.2. Definir la funci\u00f3n\n--    contada :: [Int] -> [a] -> [a]\n-- tal que (contada ns xs) es la sucesi\u00f3n formada por los s\u00edmbolos de xs\n-- cuya contadora es ns. Por ejemplo,\n--    contada [1,2,3,3] \"ab\"                ==  \"abbaaabbb\"\n--    contada [1,2,3,3] \"abc\"               ==  \"abbcccaaa\"\n--    contada [1,2,2,1,1,2,1,1,2,1,1] \"12\"  ==  \"122112122121121\"\n-- ---------------------------------------------------------------------\n\ncontada :: [Int] -> [a] -> [a]\ncontada (n:ns) (x:xs) = replicate n x ++ contada ns (xs++[x])\ncontada []     _      = []\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 8.3. La sucesi\u00f3n autocontadora (o sucesi\u00f3n de  Kolakoski) es\n-- la sucesi\u00f3n xs formada por 1 y 2 tal que coincide con su contada; es\n-- decir (contadora xs) == xs. Los primeros t\u00e9rminos de la funci\u00f3n\n-- autocontadora son\n--    1221121221221... = 1 22 11 2 1 22 1 22 11 ...\n-- y su contadora es\n--    122112122...     = 1 2  2  1 1 2  1 2  2...\n-- que coincide con la inicial. \n-- \n-- Definir la funci\u00f3n\n--    autocontadora :: [Int]\n-- tal que autocontadora es la sucesi\u00f3n autocondadora con los n\u00fameros 1\n-- y 2. Por ejemplo,\n--    take 11 autocontadora  ==  [1,2,2,1,1,2,1,2,2,1,2]\n--    take 12 autocontadora  ==  [1,2,2,1,1,2,1,2,2,1,2,2]\n--    take 18 autocontadora  ==  [1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2]\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa soluci\u00f3n\nautocontadora :: [Int]\nautocontadora = [1,2] ++ siguiente [2] 2\n\n-- Los pasos lo da la funci\u00f3n siguiente. Por ejemplo,\n--    take 3 (siguiente [2] 2)            ==  [2,1,1]\n--    take 4 (siguiente [2,1,1] 1)        ==  [2,1,1,2]\n--    take 6 (siguiente [2,1,1,2] 2)      ==  [2,1,1,2,1,1]\n--    take 7 (siguiente [2,1,1,2,1,1] 1)  ==  [2,1,1,2,1,1,2]\nsiguiente (x:xs) y = x : siguiente (xs ++ (nuevos x)) y'\n    where contrario 1 = 2\n          contrario 2 = 1\n          y'          = contrario y              \n          nuevos 1    = [y']\n          nuevos 2    = [y',y'] \n\n-- 2\u00aa soluci\u00f3n (usando contada)\nautocontadora2 :: [Int]\nautocontadora2 = 1 : 2: xs \n    where xs = 2 : contada xs [1,2]\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas hemos comentando las soluciones de los 8 primeros ejercicios de evaluaci\u00f3n de la 14\u00aa relaci\u00f3n sobre aplicaciones de la programaci\u00f3n funcional con listas infinitas. Los ejercicios, y sus soluciones, se muestran a continuaci\u00f3n.<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[250],"tags":[270,310],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_likes_enabled":false,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5228"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/comments?post=5228"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5228\/revisions"}],"predecessor-version":[{"id":5229,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5228\/revisions\/5229"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=5228"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=5228"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=5228"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}