{"id":4013,"date":"2014-01-17T17:40:48","date_gmt":"2014-01-17T16:40:48","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=4013"},"modified":"2016-01-09T18:30:53","modified_gmt":"2016-01-09T17:30:53","slug":"i1m2013-ejercicios-de-evaluacion-perezosa-y-listas-infinitas-en-haskell-2","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2013-ejercicios-de-evaluacion-perezosa-y-listas-infinitas-en-haskell-2\/","title":{"rendered":"I1M2013: Ejercicios de evaluaci\u00f3n perezosa y listas infinitas en Haskell (2)"},"content":{"rendered":"<p>En la clase de hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-13\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> hemos comentando las soluciones de ejercicios de evaluaci\u00f3n perezosa y listas infinitas de las relaciones 15 y 16.<\/p>\n<p>Los ejercicios de la relaci\u00f3n 15, y sus soluciones, se muestran a continuaci\u00f3n.<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\n-- ---------------------------------------------------------------------\n-- Importaci\u00f3n de librer\u00edas auxiliares                                  \n-- ---------------------------------------------------------------------\n\nimport Test.QuickCheck\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4. Definir, usando takeWhile y map, la funci\u00f3n\n--    potenciasMenores :: Int -> Int -> [Int]\n-- tal que (potenciasMenores x y) es la lista de las potencias de x\n-- menores que y. Por ejemplo,\n--    potenciasMenores 2 1000  ==  [2,4,8,16,32,64,128,256,512]\n-- ---------------------------------------------------------------------\n\npotenciasMenores :: Int -> Int -> [Int]\npotenciasMenores x y = takeWhile (<y) (map (x^) [1..])\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 5a. (Problema 303 del proyecto Euler) Definir la funci\u00f3n\n--    multiplosRestringidos :: Int -> (Int -> Bool) -> [Int]\n-- tal que (multiplosRestringidos n x) es la lista de los m\u00faltiplos de n\n-- tales que todas sus d\u00edgitos verifican la propiedad p. Por ejemplo, \n--    take 4 (multiplosRestringidos 5 (<=3))  ==  [10,20,30,100]\n--    take 5 (multiplosRestringidos 3 (<=4))  ==  [3,12,21,24,30]\n--    take 5 (multiplosRestringidos 3 even)   ==  [6,24,42,48,60]\n-- ---------------------------------------------------------------------\n\nmultiplosRestringidos :: Int -> (Int -> Bool) -> [Int]\nmultiplosRestringidos n p = \n    [y | y <- [n,2*n..], all p (digitos y)]\n\n-- (digitos n) es la lista de las d\u00edgitos de n, Por ejemplo, \n--    digitos 327  ==  [3,2,7]\ndigitos :: Int -> [Int]\ndigitos n = [read [x] | x <- show n]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 5b. Definir, por recursi\u00f3n, la funci\u00f3n\n--    itera :: (a -> a) -> a -> [a]\n-- tal que (itera f x) es la lista cuyo primer elemento es x y los\n-- siguientes elementos se calculan aplicando la funci\u00f3n f al elemento\n-- anterior. Por ejemplo, \n--    ghci> itera (+1) 3\n--    [3,4,5,6,7,8,9,10,11,12,{Interrupted!}\n--    ghci> itera (*2) 1\n--    [1,2,4,8,16,32,64,{Interrupted!}\n--    ghci> itera (`div` 10) 1972\n--    [1972,197,19,1,0,0,0,0,0,0,{Interrupted!}\n-- Nota: La funci\u00f3n repite es equivalente a la funci\u00f3n iterate definida\n-- en el preludio de Haskell.\n-- ---------------------------------------------------------------------\n\nitera :: (a -> a) -> a -> [a]\nitera f x = x : itera f (f x)\n\n-- ----------------------------------------------------------------------------\n-- Ejercicio 6.1. Definir, por recursi\u00f3n, la funci\u00f3n\n--    agrupa :: Int -> [a] -> [[a]]\n-- tal que (agrupa n xs) es la lista formada por listas de n elementos\n-- consecutivos de la lista xs (salvo posiblemente la \u00faltima que puede\n-- tener menos de n elementos). Por ejemplo, \n--    ghci> agrupa 2 [3,1,5,8,2,7]\n--    [[3,1],[5,8],[2,7]]\n--    ghci> agrupa 2 [3,1,5,8,2,7,9] \n--    [[3,1],[5,8],[2,7],[9]]\n--    ghci> agrupa 5 \"todo necio confunde valor y precio\"\n--    [\"todo \",\"necio\",\" conf\",\"unde \",\"valor\",\" y pr\",\"ecio\"]\n-- ---------------------------------------------------------------------------- \n\nagrupa :: Int -> [a] -> [[a]]\nagrupa n [] = []\nagrupa n xs = take n xs : agrupa n (drop n xs)\n\n-- ----------------------------------------------------------------------------\n-- Ejercicio 6.2. Definir, de manera no recursiva, la funci\u00f3n\n--    agrupa' :: Int -> [a] -> [[a]]\n-- tal que (agrupa' n xs) es la lista formada por listas de n elementos\n-- consecutivos de la lista xs (salvo posiblemente la \u00faltima que puede\n-- tener menos de n elementos). Por ejemplo, \n--    ghci> agrupa' 2 [3,1,5,8,2,7]\n--    [[3,1],[5,8],[2,7]]\n--    ghci> agrupa' 2 [3,1,5,8,2,7,9] \n--    [[3,1],[5,8],[2,7],[9]]\n--    ghci> agrupa' 5 \"todo necio confunde valor y precio\"\n--    [\"todo \",\"necio\",\" conf\",\"unde \",\"valor\",\" y pr\",\"ecio\"]\n-- ---------------------------------------------------------------------------- \n\nagrupa' :: Int -> [a] -> [[a]]\nagrupa' n = takeWhile (not . null)\n          . map (take n)\n          . iterate (drop n)\n\n-- Puede verse su funcionamiento en el siguiente ejemplo,\n--    iterate (drop 2) [5..10]  \n--    ==> [[5,6,7,8,9,10],[7,8,9,10],[9,10],[],[],...\n--    map (take 2) (iterate (drop 2) [5..10])\n--    ==> [[5,6],[7,8],[9,10],[],[],[],[],...\n--    takeWhile (not . null) (map (take 2) (iterate (drop 2) [5..10]))\n--    ==> [[5,6],[7,8],[9,10]]\n\n-- ----------------------------------------------------------------------------\n-- Ejercicio 6.3. Definir, y comprobar, con QuickCheck las dos propiedades\n-- que caracterizan a la funci\u00f3n agrupa:\n-- * todos los grupos tienen que tener la longitud determinada (salvo el\n--   \u00faltimo que puede tener una longitud menor) y\n-- * combinando todos los grupos se obtiene la lista inicial.\n-- ---------------------------------------------------------------------------- \n\n-- La primera propiedad es\nprop_AgrupaLongitud :: Int -> [Int] -> Property\nprop_AgrupaLongitud n xs =\n    n > 0 && not (null gs) ==>\n      and [length g == n | g <- init gs] &#038;&#038;\n      0 < length (last gs) &#038;&#038; length (last gs) <= n\n    where gs = agrupa n xs\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_AgrupaLongitud\n--    OK, passed 100 tests.\n\n-- La segunda propiedad es\nprop_AgrupaCombina :: Int -> [Int] -> Property\nprop_AgrupaCombina n xs =\n    n > 0 ==> concat (agrupa n xs) == xs \n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_AgrupaCombina\n--    OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 7.1. Sea la siguiente operaci\u00f3n, aplicable a cualquier\n-- n\u00famero entero positivo:  \n--    * Si el n\u00famero es par, se divide entre 2.\n--    * Si el n\u00famero es impar, se multiplica por 3 y se suma 1.\n-- Dado un n\u00famero cualquiera, podemos considerar su \u00f3rbita, es decir,\n-- las im\u00e1genes sucesivas al iterar la funci\u00f3n. Por ejemplo, la \u00f3rbita\n-- de 13 es\n--    13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1,...\n-- Si observamos este ejemplo, la \u00f3rbita de 13 es peri\u00f3dica, es decir,\n-- se repite indefinidamente a partir de un momento dado). La conjetura\n-- de Collatz dice que siempre alcanzaremos el 1 para cualquier n\u00famero\n-- con el que comencemos. Ejemplos:  \n--    * Empezando en n = 6 se obtiene 6, 3, 10, 5, 16, 8, 4, 2, 1.\n--    * Empezando en n = 11 se obtiene: 11, 34, 17, 52, 26, 13, 40, 20,\n--      10, 5, 16, 8, 4, 2, 1. \n--    * Empezando en n = 27, la sucesi\u00f3n tiene 112 pasos, llegando hasta\n--      9232 antes de descender a 1:  27, 82, 41, 124, 62, 31, 94, 47,\n--      142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274,\n--      137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263,\n--      790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502,\n--      251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958,\n--      479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644,\n--      1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308,\n--      1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122,\n--      61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5,\n--      16, 8, 4, 2, 1. \n-- \n-- Definir la funci\u00f3n\n--    siguiente :: Integer -> Integer\n-- tal que (siguiente n) es el siguiente de n en la sucesi\u00f3n de\n-- Collatz. Por ejemplo,\n--    siguiente 13  ==  40\n--    siguiente 40  ==  20\n-- ---------------------------------------------------------------------\n\nsiguiente n | even n    = n `div` 2\n            | otherwise = 3*n+1\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 7.2. Definir, por recursi\u00f3n, la funci\u00f3n \n--    collatz :: Integer -> [Integer]\n-- tal que (collatz n) es la \u00f3rbita de Collatz de n hasta alcanzar el\n-- 1. Por ejemplo,\n--    collatz 13  ==  [13,40,20,10,5,16,8,4,2,1]\n-- ---------------------------------------------------------------------\n\ncollatz :: Integer -> [Integer]\ncollatz 1 = [1]\ncollatz n = n : collatz (siguiente n)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 7.3. Definir, sin recursi\u00f3n, la funci\u00f3n \n--    collatz' :: Integer -> [Integer]\n-- tal que (collatz' n) es la \u00f3rbita de Collatz d n hasta alcanzar el\n-- 1. Por ejemplo,\n--    collatz' 13  ==  [13,40,20,10,5,16,8,4,2,1]\n-- Indicaci\u00f3n: Usar takeWhile e iterate.\n-- ---------------------------------------------------------------------\n\ncollatz' :: Integer -> [Integer]\ncollatz' n = takeWhile (\/=1) (iterate siguiente n) ++ [1]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 7.4. Definir la funci\u00f3n\n--    menorCollatzMayor :: Int -> Integer\n-- tal que (menorCollatzMayor x) es el menor n\u00famero cuya \u00f3rbita de\n-- Collatz tiene m\u00e1s de x elementos. Por ejemplo,\n--    menorCollatzMayor 100  ==  27\n-- ---------------------------------------------------------------------\n\nmenorCollatzMayor :: Int -> Integer\nmenorCollatzMayor x = head [y | y <- [1..], length (collatz y) > x]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 7.5. Definir la funci\u00f3n\n--    menorCollatzSupera :: Integer -> Integer\n-- tal que (menorCollatzSupera x) es el menor n\u00famero cuya \u00f3rbita de\n-- Collatz tiene alg\u00fan elemento mayor que x. Por ejemplo,\n--    menorCollatzSupera 100  ==  15\n-- ---------------------------------------------------------------------\n\nmenorCollatzSupera :: Integer -> Integer\nmenorCollatzSupera x = \n    head [y | y <- [1..], maximum (collatz y) > x]\n\n-- Otra definici\u00f3n alternativa es\nmenorCollatzSupera' :: Integer -> Integer\nmenorCollatzSupera' x = head [n | n <- [1..], t <- collatz' n, t > x]\n<\/pre>\n<p>Los ejercicios de la relaci\u00f3n 16, y sus soluciones, se muestran a continuaci\u00f3n.<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\n-- ---------------------------------------------------------------------\n-- Ejercicio 1.1. Definir, usando la criba de Erat\u00f3stenes, la constante\n--    primos :: Integral a => [a]\n-- cuyo valor es la lista de los n\u00fameros primos. Por ejemplo,\n--    take 10 primos  ==  [2,3,5,7,11,13,17,19,23,29]\n-- ---------------------------------------------------------------------\n\nprimos :: Integral a => [a]\nprimos = criba [2..]\n    where criba []     = []\n          criba (n:ns) = n : criba (elimina n ns)\n          elimina n xs = [x | x <- xs, x `mod` n \/= 0]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1.2. Definir la funci\u00f3n\n--    primo :: Integral a => a -> Bool\n-- tal que (primo n) se verifica si n es primo. Por ejemplo,\n--    primo 7  ==  True\n--    primo 9  ==  False\n-- ---------------------------------------------------------------------\n\nprimo :: Int -> Bool\nprimo n = head (dropWhile (<n) primos) == n\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 6. Definir la funci\u00f3n\n--    sumaDeDosPrimos :: Int -> [(Int,Int)]\n-- tal que (sumaDeDosPrimos n) es la lista de las distintas\n-- descomposiciones de n como suma de dos n\u00fameros primos. Por ejemplo, \n--    sumaDeDosPrimos 30  ==  [(7,23),(11,19),(13,17)]\n--    sumaDeDosPrimos 10  ==  [(3,7),(5,5)]\n-- Calcular, usando la funci\u00f3n sumaDeDosPrimos, el menor n\u00famero que\n-- puede escribirse de 10 formas distintas como suma de dos primos.\n-- ---------------------------------------------------------------------\n\nsumaDeDosPrimos :: Int -> [(Int,Int)]\nsumaDeDosPrimos n = \n    [(x,n-x) | x <- primosN, x <= n-x, elem (n-x) primosN]\n    where primosN = takeWhile (<=n) primos\n\n-- El c\u00e1lculo es\n--    ghci> head [x | x <- [1..], length (sumaDeDosPrimos x) == 10]\n--    114\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3. Definir la funci\u00f3n\n--    esProductoDeDosPrimos :: Int -> Bool\n-- tal que (esProductoDeDosPrimos n) se verifica si n es el producto de\n-- dos primos distintos. Por ejemplo,\n--    esProductoDeDosPrimos 6  ==  True\n--    esProductoDeDosPrimos 9  ==  False\n-- ---------------------------------------------------------------------\n\nesProductoDeDosPrimos :: Int -> Bool\nesProductoDeDosPrimos n =\n    [x | x <- primosN, \n         mod n x == 0, \n         div n x \/= x, \n         elem (div n x) primosN] \/= []\n    where primosN = takeWhile (<=n) primos\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4.1. [Problema 37 del proyecto Euler] Un n\u00famero primo es\n-- truncable si los n\u00fameros que se obtienen eliminado cifras, de derecha\n-- a izquierda, son primos. Por ejemplo, 599 es un primo truncable\n-- porque 599, 59 y 5 son primos; en cambio, 577 es un primo no\n-- truncable porque 57 no es primo.   \n-- \n-- Definir la funci\u00f3n \n--    primoTruncable :: Int -> Bool\n-- tal que (primoTruncable x) se verifica si x es un primo truncable. \n-- Por ejemplo,\n--    primoTruncable 599  ==  True\n--    primoTruncable 577  ==  False\n-- ---------------------------------------------------------------------\n\nprimoTruncable :: Int -> Bool\nprimoTruncable x \n    | x < 10    = primo x\n    | otherwise = primo x &#038;&#038; primoTruncable (x `div` 10)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4.2. Definir la funci\u00f3n\n--    sumaPrimosTruncables :: Int -> Int\n-- tal que (sumaPrimosTruncables n) es la suma de los n primeros primos\n-- truncables. Por ejemplo,\n--    sumaPrimosTruncables 10  ==  249\n-- Calcular la suma de los 20 primos truncables.\n-- ---------------------------------------------------------------------\n\nsumaPrimosTruncables :: Int -> Int\nsumaPrimosTruncables n = \n    sum (take n [x | x <- primos, primoTruncable x])\n\n-- El c\u00e1lculo es\n--    ghci> sumaPrimosTruncables 20\n--    2551\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 comentando las soluciones de ejercicios de evaluaci\u00f3n perezosa y listas infinitas de las relaciones 15 y 16. Los ejercicios de la relaci\u00f3n 15, y sus soluciones, 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":[222],"tags":[270,300],"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\/4013"}],"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=4013"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4013\/revisions"}],"predecessor-version":[{"id":5271,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4013\/revisions\/5271"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=4013"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=4013"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=4013"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}