{"id":1855,"date":"2012-01-24T16:07:31","date_gmt":"2012-01-24T16:07:31","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=1855"},"modified":"2013-03-08T05:48:56","modified_gmt":"2013-03-08T05:48:56","slug":"i1m2011-ejercicios-con-listas-infinitas-2","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2011-ejercicios-con-listas-infinitas-2\/","title":{"rendered":"I1M2011: Ejercicios con listas infinitas (2)"},"content":{"rendered":"<p>En la clase de hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-11\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> se han explicado las soluciones de los ejercicios de la  <a href=\"https:\/\/www.glc.us.es\/~jalonso\/ejerciciosI1M2011G1\/images\/0\/0a\/Rel_15.hs\">15\u00aa relaci\u00f3n<\/a> sobre listas infinitas y evaluaci\u00f3n perezosa. En concreto, se estudian funciones para calcular<\/p>\n<ul>\n<li> la lista de las potencias de un n\u00famero menores que otro dado,\n<li> la lista obtenida repitiendo un elemento infinitas veces,\n<li> la lista obtenida repitiendo un elemento un n\u00famero finito de veces,\n<li> la cadena obtenida cada elemento tantas veces como indica su posici\u00f3n,\n<li> la aplicaci\u00f3n iterada de una funci\u00f3n a un elemento,\n<li> la lista de las sublistas de longitud dada y\n<li> la sucesi\u00f3n de Collatz.\n<\/ul>\n<p>Estos ejercicios corresponden al <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-10\/temas\/tema-10.pdf\">tema 10<\/a>.<\/p>\n<p>Los ejercicios, y sus soluciones, se muestran a continuaci\u00f3n.<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\r\n-- ---------------------------------------------------------------------\r\n-- Importaci\u00f3n de librer\u00edas auxiliares                                  \r\n-- ---------------------------------------------------------------------\r\n\r\nimport Test.QuickCheck\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1. Definir, usando takeWhile y map, la funci\u00f3n\r\n--    potenciasMenores :: Int -> Int -> [Int]\r\n-- tal que (potenciasMenores x y) es la lista de las potencias de x\r\n-- menores que y. Por ejemplo,\r\n--    potenciasMenores 2 1000  ==  [2,4,8,16,32,64,128,256,512]\r\n-- ---------------------------------------------------------------------\r\n\r\npotenciasMenores :: Int -> Int -> [Int]\r\npotenciasMenores x y = takeWhile (<y) (map (x^) [1..])\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2. Definir, por recursi\u00f3n y comprensi\u00f3n, la funci\u00f3n \r\n--    repite :: a -> [a]\r\n-- tal que (repite x) es la lista infinita cuyos elementos son x. Por\r\n-- ejemplo, \r\n--    repite 5           == [5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,...\r\n--    take 3 (repite 5)  ==  [5,5,5]\r\n-- Nota: La funci\u00f3n repite es equivalente a la funci\u00f3n repeat definida\r\n-- en el preludio de Haskell.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- Por recursi\u00f3n:\r\nrepite :: a -> [a]\r\nrepite x = x : repite x\r\n\r\n-- Por comprensi\u00f3n:\r\nrepite' x = [x | _ <- [1..]]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3. Definir, por recursi\u00f3n y por comprensi\u00f3n, la funci\u00f3n \r\n--    repiteFinita :: Int-> a -> [a]\r\n-- tal que (repite n x) es la lista con n elementos iguales a x. Por\r\n-- ejemplo, \r\n--    repiteFinita 3 5  ==  [5,5,5]\r\n-- Nota: La funci\u00f3n repite es equivalente a la funci\u00f3n replicate definida\r\n-- en el preludio de Haskell.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- Por recursi\u00f3n:\r\nrepiteFinita :: Int -> a -> [a]\r\nrepiteFinita 0 x = []\r\nrepiteFinita n x = x : repiteFinita (n-1) x\r\n\r\n-- Por comprensi\u00f3n:\r\nrepiteFinita' :: Int -> a -> [a]\r\nrepiteFinita' n x = [x | _ <- [1..n]]\r\n\r\n-- Tambi\u00e9n se puede definir usando repite\r\nrepiteFinita2 :: Int -> a -> [a]\r\nrepiteFinita2 n x = take n (repite x)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 4. Se considera la funci\u00f3n\r\n--    eco :: String -> String\r\n-- tal que (eco xs) es la cadena obtenida a partir de la cadena xs\r\n-- repitiendo cada elemento tantas veces como indica su posici\u00f3n: el\r\n-- primer elemento se repite 1 vez, el segundo 2 veces y as\u00ed\r\n-- sucesivamente. Por ejemplo, \r\n--    eco \"abcd\"  ==  \"abbcccdddd\"\r\n-- 1. Escribir una definici\u00f3n 'no recursiva' de la funci\u00f3n eco.\r\n-- 2. Escribir una definici\u00f3n 'recursiva' de la funci\u00f3n eco.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- Una definici\u00f3n no recursiva es\r\necoNR :: String -> String\r\necoNR xs = concat [replicate i x | (i,x) <- zip [1..] xs]\r\n\r\n-- Una definici\u00f3n recursiva es\r\necoR :: String -> String\r\necoR xs = aux 1 xs\r\n    where aux n [] = []\r\n          aux n (x:xs) = replicate n x ++ aux (n+1) xs\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 5. Definir, por recursi\u00f3n, la funci\u00f3n\r\n--    itera :: (a -> a) -> a -> [a]\r\n-- tal que (itera f x) es la lista cuyo primer elemento es x y los\r\n-- siguientes elementos se calculan aplicando la funci\u00f3n f al elemento\r\n-- anterior. Por ejemplo, \r\n--    Main> itera (+1) 3\r\n--    [3,4,5,6,7,8,9,10,11,12,{Interrupted!}\r\n--    Main> itera (*2) 1\r\n--    [1,2,4,8,16,32,64,{Interrupted!}\r\n--    Main> itera (`div` 10) 1972\r\n--    [1972,197,19,1,0,0,0,0,0,0,{Interrupted!}\r\n-- Nota: La funci\u00f3n repite es equivalente a la funci\u00f3n iterate definida\r\n-- en el preludio de Haskell.\r\n-- ---------------------------------------------------------------------\r\n\r\nitera :: (a -> a) -> a -> [a]\r\nitera f x = x : itera f (f x)\r\n\r\n-- ----------------------------------------------------------------------------\r\n-- Ejercicio 6, Definir la funci\u00f3n\r\n--    agrupa :: Int -> [a] -> [[a]]\r\n-- tal que (agrupa n xs) es la lista formada por listas de n elementos\r\n-- conscutivos de la lista xs (salvo posiblemente la \u00faltima que puede\r\n-- tener menos de n elementos). Por ejemplo, \r\n--    Main> agrupa 2 [3,1,5,8,2,7]\r\n--    [[3,1],[5,8],[2,7]]\r\n--    Main> agrupa 2 [3,1,5,8,2,7,9] \r\n--    [[3,1],[5,8],[2,7],[9]]\r\n--    Main> agrupa 5 \"todo necio confunde valor y precio\"\r\n--    [\"todo \",\"necio\",\" conf\",\"unde \",\"valor\",\" y pr\",\"ecio\"]\r\n-- ---------------------------------------------------------------------------- \r\n\r\n-- Una definici\u00f3n recursiva de agrupa es\r\nagrupa :: Int -> [a] -> [[a]]\r\nagrupa n [] = []\r\nagrupa n xs = take n xs : agrupa n (drop n xs)\r\n\r\n-- Una definici\u00f3n no recursiva es\r\nagrupa' :: Int -> [a] -> [[a]]\r\nagrupa' n = takeWhile (not . null)\r\n          . map (take n)\r\n          . iterate (drop n)\r\n\r\n-- Puede verse su funcionamiento en el siguiente ejemplo,\r\n--    iterate (drop 2) [5..10]  \r\n--    ==> [[5,6,7,8,9,10],[7,8,9,10],[9,10],[],[],...\r\n--    map (take 2) (iterate (drop 2) [5..10])\r\n--    ==> [[5,6],[7,8],[9,10],[],[],[],[],...\r\n--    takeWhile (not . null) (map (take 2) (iterate (drop 2) [5..10]))\r\n--    ==> [[5,6],[7,8],[9,10]]\r\n\r\n-- ----------------------------------------------------------------------------\r\n-- Ejercicio 7. Definir, y comprobar, con QuickCheck las dos propiedades\r\n-- que caracterizan a la funci\u00f3n agrupa:\r\n-- * todos los grupos tienen que tener la longitud determinada (salvo el\r\n--   \u00faltimo que puede tener una longitud menor) y\r\n-- * combinando todos los grupos se obtiene la lista inicial.\r\n-- ---------------------------------------------------------------------------- \r\n\r\n-- La primera propiedad es\r\nprop_AgrupaLongitud :: Int -> [Int] -> Property\r\nprop_AgrupaLongitud n xs =\r\n    n > 0 && not (null gs) ==>\r\n      and [length g == n | g <- init gs] &#038;&#038;\r\n      0 < length (last gs) &#038;&#038; length (last gs) <= n\r\n    where gs = agrupa n xs\r\n\r\n-- La comprobaci\u00f3n es\r\n--    Main> quickCheck prop_AgrupaLongitud\r\n--    OK, passed 100 tests.\r\n\r\n-- La segunda propiedad es\r\nprop_AgrupaCombina :: Int -> [Int] -> Property\r\nprop_AgrupaCombina n xs =\r\n    n > 0 ==> concat (agrupa n xs) == xs \r\n\r\n-- La comprobaci\u00f3n es\r\n--    Main> quickCheck prop_AgrupaCombina\r\n--    OK, passed 100 tests.\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Sea la siguiente operaci\u00f3n, aplicable a cualquier n\u00famero entero\r\n-- positivo:  \r\n--    * Si el n\u00famero es par, se divide entre 2.\r\n--    * Si el n\u00famero es impar, se multiplica por 3 y se suma 1.\r\n-- Dado un n\u00famero cualquiera, podemos considerar su \u00f3rbita, es decir,\r\n-- las im\u00e1genes sucesivas al iterar la funci\u00f3n. Por ejemplo, la \u00f3rbita\r\n-- de 13 es\r\n--    13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1,...\r\n-- Si observamos este ejemplo, la \u00f3rbita de 13 es peri\u00f3dica, es decir,\r\n-- se repite indefinidamente a partir de un momento dado). La conjetura\r\n-- de Collatz dice que siempre alcanzaremos el 1 para cualquier n\u00famero\r\n-- con el que comencemos. Ejemplos:  \r\n--    * Empezando en n = 6 se obtiene 6, 3, 10, 5, 16, 8, 4, 2, 1.\r\n--    * Empezando en n = 11 se obtiene: 11, 34, 17, 52, 26, 13, 40, 20,\r\n--      10, 5, 16, 8, 4, 2, 1. \r\n--    * Empezando en n = 27, la sucesi\u00f3n tiene 112 pasos, llegando hasta\r\n--      9232 antes de descender a 1:  27, 82, 41, 124, 62, 31, 94, 47,\r\n--      142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274,\r\n--      137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263,\r\n--      790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502,\r\n--      251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958,\r\n--      479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644,\r\n--      1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308,\r\n--      1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122,\r\n--      61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5,\r\n--      16, 8, 4, 2, 1. \r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 8. Definir la funci\u00f3n\r\n--    siguiente :: Integer -> Integer\r\n-- tal que (siguiente n) es el siguiente de n en la sucesi\u00f3n de\r\n-- Collatz. Por ejemplo,\r\n--    siguiente 13  ==  40\r\n--    siguiente 40  ==  20\r\n-- ---------------------------------------------------------------------\r\n\r\nsiguiente n | even n    = n `div` 2\r\n            | otherwise = 3*n+1\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 9. Definir, por recursi\u00f3n, la funci\u00f3n \r\n--    collatz :: Integer -> [Integer]\r\n-- tal que (collatz n) es la \u00f3rbita de Collatz d n hasta alcanzar el\r\n-- 1. Por ejemplo,\r\n--    collatz 13  ==  [13,40,20,10,5,16,8,4,2,1]\r\n-- ---------------------------------------------------------------------\r\n\r\ncollatz :: Integer -> [Integer]\r\ncollatz 1 = [1]\r\ncollatz n = n : collatz (siguiente n)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 10. Definir, sin recursi\u00f3n, la funci\u00f3n \r\n--    collatz' :: Integer -> [Integer]\r\n-- tal que (collatz' n) es la \u00f3rbita de Collatz d n hasta alcanzar el\r\n-- 1. Por ejemplo,\r\n--    collatz' 13  ==  [13,40,20,10,5,16,8,4,2,1]\r\n-- Indicaci\u00f3n: Usar takeWhile e iterate.\r\n-- ---------------------------------------------------------------------\r\n\r\ncollatz' :: Integer -> [Integer]\r\ncollatz' n = (takeWhile (\/=1) (iterate siguiente n)) ++ [1]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 11. Definir la funci\u00f3n\r\n--    menorCollatzMayor :: Int -> Integer\r\n-- tal que (menorCollatzMayor x) es el menor n\u00famero cuya \u00f3rbita de\r\n-- Collatz tiene m\u00e1s de x elementos. Por ejemplo,\r\n--    menorCollatzMayor 100  ==  27\r\n-- ---------------------------------------------------------------------\r\n\r\nmenorCollatzMayor :: Int -> Integer\r\nmenorCollatzMayor x = head [y | y <- [1..], length (collatz y) > x]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 12. Definir la funci\u00f3n\r\n--    menorCollatzSupera :: Integer -> Integer\r\n-- tal que (menorCollatzSupera x) es el menor n\u00famero cuya \u00f3rbita de\r\n-- Collatz tiene alg\u00fan elemento mayor que x. Por ejemplo,\r\n--    menorCollatzSupera 100  ==  15\r\n-- ---------------------------------------------------------------------\r\n\r\nmenorCollatzSupera :: Integer -> Integer\r\nmenorCollatzSupera x = \r\n    head [y | y <- [1..], maximum (collatz y) > x]\r\n\r\n-- Otra definici\u00f3n alternativa es\r\nmenorCollatzSupera' :: Integer -> Integer\r\nmenorCollatzSupera' x = head [n | n <- [1..], t <- collatz' n, t > x]\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 se han explicado las soluciones de los ejercicios de la 15\u00aa relaci\u00f3n sobre listas infinitas y evaluaci\u00f3n perezosa. En concreto, se estudian funciones para calcular la lista de las potencias de un n\u00famero menores que otro dado, la lista obtenida repitiendo un&#8230;<\/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":[186],"tags":[295],"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\/1855"}],"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=1855"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1855\/revisions"}],"predecessor-version":[{"id":2864,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1855\/revisions\/2864"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=1855"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=1855"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=1855"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}