{"id":1318,"date":"2011-03-31T05:35:22","date_gmt":"2011-03-31T05:35:22","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=1318"},"modified":"2011-04-28T05:36:12","modified_gmt":"2011-04-28T05:36:12","slug":"i1m2010-ejercicios-sobre-listas-infinitas-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2010-ejercicios-sobre-listas-infinitas-en-haskell\/","title":{"rendered":"I1M2010: Ejercicios sobre listas infinitas en Haskell"},"content":{"rendered":"<p>En la clase de hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-10\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> hemos comentado las soluciones a los ejercicios sobre listas infinitas en Haskell de la <a href=\"https:\/\/www.glc.us.es\/~jalonso\/ejerciciosI1M2010\/index.php5\/Relaci%C3%B3n_26\">26\u00aa relaci\u00f3n<\/a>.<\/p>\n<p>Los ejercicios y su soluci\u00f3n se muestran a continuaci\u00f3n<!--more--><\/p>\n<pre lang=\"haskell\">\r\n-- ---------------------------------------------------------------------\r\n-- Introducci\u00f3n                                                       --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- En esta relaci\u00f3n se estudia distintas aplicaciones de la programaci\u00f3n\r\n-- funcional que usan listas infinitas\r\n-- * definici\u00f3n alternativa de la sucesi\u00f3n de Hamming estudiada en el\r\n--   tema 11,\r\n-- * propiedades de la sucesi\u00f3n de Hamming,\r\n-- * problemas 10 y 12 del proyecto Euler y\r\n-- * numero de pares de naturales en un c\u00edrculo.\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Importaci\u00f3n de librer\u00edas                                           --\r\n-- ---------------------------------------------------------------------\r\n\r\nimport Test.QuickCheck\r\nimport Data.List\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1.1. Definir la funci\u00f3n\r\n--    divisoresEn :: Integer -> [Integer] -> Bool\r\n-- tal que (divisoresEn x ys) se verifica si x puede expresarse como un\r\n-- producto de potencias de elementos de ys. Por ejemplo,\r\n--    divisoresEn 12 [2,3,5]  ==  True\r\n--    divisoresEn 14 [2,3,5]  ==  False\r\n-- ---------------------------------------------------------------------\r\n\r\ndivisoresEn :: Integer -> [Integer] -> Bool\r\ndivisoresEn 1 _                     = True\r\ndivisoresEn x []                    = False\r\ndivisoresEn x (y:ys) | mod x y == 0 = divisoresEn (div x y) (y:ys)\r\n                     | otherwise    = divisoresEn x ys   \r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1.2. Los n\u00fameros de Hamming forman una sucesi\u00f3n \r\n-- estrictamente creciente de n\u00fameros que cumplen las siguientes \r\n-- condiciones: \r\n--    1. El n\u00famero 1 est\u00e1 en la sucesi\u00f3n.\r\n--    2. Si x est\u00e1 en la sucesi\u00f3n, entonces 2x, 3x y 5x tambi\u00e9n est\u00e1n.\r\n--    3. Ning\u00fan otro n\u00famero est\u00e1 en la sucesi\u00f3n.\r\n-- Definir, usando divisoresEn, la constante\r\n--    hamming :: [Integer]\r\n-- tal que hamming es la sucesi\u00f3n de Hamming. Por ejemplo,\r\n--    take 12 hamming  ==  [1,2,3,4,5,6,8,9,10,12,15,16]\r\n-- ---------------------------------------------------------------------\r\n\r\nhamming :: [Integer]\r\nhamming = [x | x <- [1..], divisoresEn x [2,3,5]]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1.3. Definir la funci\u00f3n\r\n--    cantidadHammingMenores :: Integer -> Int\r\n-- tal que (cantidadHammingMenores x) es la cantidad de n\u00fameros de\r\n-- Hamming menores que x. Por ejemplo,\r\n--    cantidadHammingMenores 6  ==  5\r\n--    cantidadHammingMenores 7  ==  6\r\n--    cantidadHammingMenores 8  ==  6\r\n-- ---------------------------------------------------------------------\r\n\r\ncantidadHammingMenores :: Integer -> Int\r\ncantidadHammingMenores x = length (takeWhile (<x) hamming)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1.4. Definir la funci\u00f3n\r\n--    siguienteHamming :: Integer -> Integer\r\n-- tal que (siguienteHamming x) es el menor n\u00famero de la sucesi\u00f3n de\r\n-- Hamming mayor que x. Por ejemplo,\r\n--    siguienteHamming 6  ==  8\r\n--    siguienteHamming 21  ==  24\r\n-- ---------------------------------------------------------------------\r\n\r\nsiguienteHamming :: Integer -> Integer\r\nsiguienteHamming x = head (dropWhile (<=x) hamming)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1.5. Definir la funci\u00f3n\r\n--    huecoHamming :: Integer -> [(Integer,Integer)]\r\n-- tal que (huecoHamming n) es la lista de pares de n\u00fameros consecutivos\r\n-- en la sucesi\u00f3n de Hamming cuya distancia es mayor o igual que n. Por\r\n-- ejemplo,  \r\n--    take 4 (huecoHamming 2)   ==  [(12,15),(20,24),(27,30),(32,36)]\r\n--    take 3 (huecoHamming 2)   ==  [(12,15),(20,24),(27,30)]\r\n--    take 2 (huecoHamming 3)   ==  [(20,24),(32,36)]\r\n--    head (huecoHamming 10)    ==  (108,120)\r\n--    head (huecoHamming 1000)  ==  (34992,36000)\r\n-- ---------------------------------------------------------------------\r\n\r\nhuecoHamming :: Integer -> [(Integer,Integer)]\r\nhuecoHamming n = [(x,y) | x <- hamming, \r\n                          let y = siguienteHamming x,\r\n                          y-x > n]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1.6. Comprobar con QuickCheck que para todo n, existen\r\n-- pares de n\u00fameros consecutivos en la sucesi\u00f3n de Hamming cuya\r\n-- distancia es mayor o igual que n.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La propiedad es\r\nprop_Hamming :: Integer -> Bool\r\nprop_Hamming n = huecoHamming n' \/= []\r\n                 where n' = abs n\r\n\r\n-- La comprobaci\u00f3n es\r\n--    *Main> quickCheck prop_Hamming\r\n--    OK, passed 100 tests.\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2. (Problema 10 del Proyecto Euler)\r\n-- Definir la funci\u00f3n \r\n--    sumaPrimoMenores :: Integer -> Integer\r\n-- tal que (sumaPrimoMenores n) es la suma de los primos menores que\r\n-- n. Por ejemplo,\r\n--    sumaPrimoMenores 10  ==  17\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La definici\u00f3n es\r\nsumaPrimoMenores :: Integer -> Integer\r\nsumaPrimoMenores n = sumaMenores n primos 0\r\n   where sumaMenores n (x:xs) a | n <= x    = a\r\n                                | otherwise = sumaMenores n xs (a+x)\r\n\r\n-- primos es la lista de los n\u00famero primos obtenida mediante la criba de \r\n-- Erast\u00f3tenes. Por ejemplo,\r\n--    primos  =>  [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,...\r\nprimos :: [Integer]\r\nprimos = criba [2..]\r\n         where criba (p:ps) = p : criba [n | n<-ps, mod n p \/= 0]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3. (Problema 12 del Proyecto Euler)\r\n-- La sucesi\u00f3n de los n\u00fameros triangulares se obtiene sumando los\r\n-- n\u00fameros naturales. As\u00ed, el 7\u00ba n\u00famero triangular es \r\n--    1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. \r\n-- Los primeros 10 n\u00fameros triangulares son\r\n--    1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...\r\n-- Los divisores de los primeros 7 n\u00fameros triangulares son:\r\n--     1: 1\r\n--     3: 1,3\r\n--     6: 1,2,3,6\r\n--    10: 1,2,5,10\r\n--    15: 1,3,5,15\r\n--    21: 1,3,7,21\r\n--    28: 1,2,4,7,14,28\r\n-- Como se puede observar, 28 es el menor n\u00famero triangular con m\u00e1s de 5\r\n-- divisores. \r\n-- \r\n-- Definir la funci\u00f3n \r\n--    euler12 :: Int -> Integer\r\n-- tal que (euler12 n) es el menor n\u00famero triangular con m\u00e1s de n\r\n-- divisores. Por ejemplo,\r\n--    euler12 5  ==  28\r\n-- ---------------------------------------------------------------------\r\n\r\neuler12 :: Int -> Integer\r\neuler12 n = head [x | x <- triangulares, nDivisores x > n]\r\n\r\n-- triangulares es la lista de los n\u00fameros triangulares\r\n--    take 10 triangulares  =>  [1,3,6,10,15,21,28,36,45,55]\r\ntriangulares :: [Integer]\r\ntriangulares = 1:[x+y | (x,y) <- zip [2..] triangulares]\r\n\r\n-- Otra definici\u00f3n de triangulares es\r\ntriangulares' :: [Integer]\r\ntriangulares' = scanl (+) 1 [2..]\r\n\r\n-- (divisores n) es la lista de los divisores de n. Por ejemplo,\r\n--    divisores 28  ==  [1,2,4,7,14,28]\r\ndivisores :: Integer -> [Integer]\r\ndivisores x = [y | y <- [1..x], mod x y == 0]\r\n\r\n-- (nDivisores n) es el n\u00famero de los divisores de n. Por ejemplo,\r\n--    nDivisores 28  ==  6\r\nnDivisores :: Integer -> Int\r\nnDivisores x = length (divisores x)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 4. Definir la funci\u00f3n \r\n--    circulo :: Int -> Int\r\n-- tal que (circulo n) es el la cantidad de pares de n\u00fameros naturales\r\n-- (x,y) que se encuentran dentro del c\u00edrculo de radio n. Por ejemplo,\r\n--    circulo 3  ==  9\r\n--    circulo 4  ==  15\r\n--    circulo 5  ==  22\r\n-- ---------------------------------------------------------------------\r\n\r\ncirculo :: Int -> Int\r\ncirculo n = length [(x,y) | x <- [0..n], y <- [0..n], x^2+y^2 < n^2]\r\n\r\n-- La eficiencia puede mejorarse con\r\ncirculo' :: Int -> Int\r\ncirculo' n = length [(x,y) | x <- [0..m], y <- [0..m], x^2+y^2 < n^2]\r\n    where m = raizCuadradaEntera n\r\n\r\n-- (raizCuadradaEntera n) es la parte entera de la ra\u00edz cuadrada de\r\n-- n. Por ejemplo,\r\n--    raizCuadradaEntera 17  ==  4 \r\nraizCuadradaEntera :: Int -> Int\r\nraizCuadradaEntera n = truncate (sqrt (fromIntegral n))\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas hemos comentado las soluciones a los ejercicios sobre listas infinitas en Haskell de la 26\u00aa relaci\u00f3n. Los ejercicios y su soluci\u00f3n se muestran a continuaci\u00f3n<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","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":[133],"tags":[287],"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\/1318"}],"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=1318"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1318\/revisions"}],"predecessor-version":[{"id":1319,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1318\/revisions\/1319"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=1318"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=1318"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=1318"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}