{"id":5660,"date":"2016-12-07T19:05:02","date_gmt":"2016-12-07T18:05:02","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=5660"},"modified":"2016-12-19T19:16:29","modified_gmt":"2016-12-19T18:16:29","slug":"i1m2016-ejercicios-de-evaluacion-perezosa-y-listas-infinitas-en-haskell-1","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2016-ejercicios-de-evaluacion-perezosa-y-listas-infinitas-en-haskell-1\/","title":{"rendered":"I1M2016: Ejercicios de evaluaci\u00f3n perezosa y listas infinitas en Haskell (1)"},"content":{"rendered":"<p>En clase de hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-16\">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 la 11\u00aa relaci\u00f3n.<\/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 presentan ejercicios con listas infinitas y\n-- evaluaci\u00f3n perezosa. Estos ejercicios corresponden al tema 10 que\n-- se encuentra en  \n--    http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-16\/temas\/tema-10.html\n\n-- ---------------------------------------------------------------------\n-- Importaci\u00f3n de librer\u00edas auxiliares                                  \n-- ---------------------------------------------------------------------\n\nimport Test.QuickCheck\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1.1. Definir, por recursi\u00f3n, la funci\u00f3n \n--    repite :: a -> [a]\n-- tal que (repite x) es la lista infinita cuyos elementos son x. Por\n-- ejemplo, \n--    repite 5           ==  [5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,...\n--    take 3 (repite 5)  ==  [5,5,5]\n-- \n-- Nota: La funci\u00f3n repite es equivalente a la funci\u00f3n repeat definida\n-- en el preludio de Haskell.\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa definici\u00f3n:\nrepite1 :: a -> [a]\nrepite1 x = x : repite1 x\n\n-- 2\u00aa definici\u00f3n:\nrepite2 :: a -> [a]\nrepite2 x = ys \n    where ys = x:ys\n\n-- La 2\u00aa definici\u00f3n es m\u00e1s eficiente:\n--    ghci> last (take 100000000 (repite1 5))\n--    5\n--    (46.56 secs, 16001567944 bytes)\n--    ghci> last (take 100000000 (repite2 5))\n--    5\n--    (2.34 secs, 5601589608 bytes)\n\n-- Usaremos como repite la 2\u00aa definici\u00f3n\nrepite :: a -> [a]\nrepite = repite2\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1.2. Definir, por comprensi\u00f3n, la funci\u00f3n \n--    repiteC :: a -> [a]\n-- tal que (repiteC x) es la lista infinita cuyos elementos son x. Por\n-- ejemplo, \n--    repiteC 5           ==  [5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,...\n--    take 3 (repiteC 5)  ==  [5,5,5]\n--\n-- Nota: La funci\u00f3n repiteC es equivalente a la funci\u00f3n repeat definida\n-- en el preludio de Haskell.\n-- ---------------------------------------------------------------------\n\nrepiteC :: a -> [a]\nrepiteC x = [x | _ <- [1..]]\n\n-- La funci\u00f3n repite2 es m\u00e1s eficiente que repiteC\n--    \u03bb> last (take 10000000 (repiteC 5))\n--    5\n--    (6.05 secs, 1,997,740,536 bytes)\n--    \u03bb> last (take 10000000 (repite2 5))\n--    5\n--    (0.31 secs, 541,471,280 bytes)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2.1. Definir, por recursi\u00f3n, la funci\u00f3n \n--    repiteFinitaR :: Int-> a -> [a]\n-- tal que (repiteFinitaR n x) es la lista con n elementos iguales a\n-- x. Por ejemplo, \n--    repiteFinitaR 3 5  ==  [5,5,5]\n--\n-- Nota: La funci\u00f3n repiteFinitaR es equivalente a la funci\u00f3n replicate\n-- definida en el preludio de Haskell.\n-- ---------------------------------------------------------------------\n\nrepiteFinitaR :: Int -> a -> [a]\nrepiteFinitaR n x | n <= 0    = []\n                  | otherwise = x : repiteFinitaR (n-1) x\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2.2. Definir, por comprensi\u00f3n, la funci\u00f3n \n--    repiteFinitaC :: Int-> a -> [a]\n-- tal que (repiteFinitaC n x) es la lista con n elementos iguales a\n-- x. Por ejemplo, \n--    repiteFinitaC 3 5  ==  [5,5,5]\n--\n-- Nota: La funci\u00f3n repiteFinitaC es equivalente a la funci\u00f3n replicate\n-- definida en el preludio de Haskell.\n-- ---------------------------------------------------------------------\n\nrepiteFinitaC :: Int -> a -> [a]\nrepiteFinitaC n x = [x | _ <- [1..n]]\n\n-- La funci\u00f3n repiteFinitaC es m\u00e1s eficiente que repiteFinitaR\n--    \u03bb> last (repiteFinitaR 10000000 5)\n--    5\n--    (17.04 secs, 2,475,222,448 bytes)\n--    \u03bb> last (repiteFinitaC 10000000 5)\n--    5\n--    (5.43 secs, 1,511,227,176 bytes)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2.3. Definir, usando repite, la funci\u00f3n \n--    repiteFinita :: Int-> a -> [a]\n-- tal que (repiteFinita n x) es la lista con n elementos iguales a\n-- x. Por ejemplo, \n--    repiteFinita 3 5  ==  [5,5,5]\n--\n-- Nota: La funci\u00f3n repiteFinita es equivalente a la funci\u00f3n replicate\n-- definida en el preludio de Haskell.\n-- ---------------------------------------------------------------------\n\nrepiteFinita :: Int -> a -> [a]\nrepiteFinita n x = take n (repite x)\n\n-- La funci\u00f3n repiteFinita es m\u00e1s eficiente que repiteFinitaC\n--    \u03bb> last (repiteFinitaC 10000000 5)\n--    5\n--    (5.43 secs, 1,511,227,176 bytes)\n--    \u03bb> last (repiteFinita 10000000 5)\n--    5\n--    (0.29 secs, 541,809,248 bytes)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2.4. Comprobar con QuickCheck que las funciones\n-- repiteFinitaR, repiteFinitaC y repiteFinita son equivalentes a\n-- replicate. \n--\n-- Nota. Al hacer la comprobaci\u00f3n limitar el tama\u00f1o de las pruebas como\n-- se indica a continuaci\u00f3n\n--    quickCheckWith (stdArgs {maxSize=7}) prop_repiteFinitaEquiv\n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_repiteFinitaEquiv :: Int -> Int -> Bool\nprop_repiteFinitaEquiv n x =\n    repiteFinitaR n x == y &&\n    repiteFinitaC n x == y &&\n    repiteFinita  n x == y\n    where y = replicate n x\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheckWith (stdArgs {maxSize=20}) prop_repiteFinitaEquiv\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2.5. Comprobar con QuickCheck que la longitud de\n-- (repiteFinita n x) es n, si n es positivo y 0 si no lo es.\n--\n-- Nota. Al hacer la comprobaci\u00f3n limitar el tama\u00f1o de las pruebas como\n-- se indica a continuaci\u00f3n\n--    quickCheckWith (stdArgs {maxSize=30}) prop_repiteFinitaLongitud\n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_repiteFinitaLongitud :: Int -> Int -> Bool\nprop_repiteFinitaLongitud n x \n    | n > 0     = length (repiteFinita n x) == n\n    | otherwise = length (repiteFinita n x) == 0\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheckWith (stdArgs {maxSize=30}) prop_repiteFinitaLongitud\n--    +++ OK, passed 100 tests.\n\n-- La expresi\u00f3n de la propiedad se puede simplificar\nprop_repiteFinitaLongitud2 :: Int -> Int -> Bool\nprop_repiteFinitaLongitud2 n x =\n    length (repiteFinita n x) == (if n > 0 then n else 0)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2.6. Comprobar con QuickCheck que todos los elementos de \n-- (repiteFinita n x) son iguales a x.\n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_repiteFinitaIguales :: Int -> Int -> Bool\nprop_repiteFinitaIguales n x =\n    all (==x) (repiteFinita n x)\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheckWith (stdArgs {maxSize=30}) prop_repiteFinitaIguales\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3.1. Definir, por comprensi\u00f3n, la funci\u00f3n\n--    ecoC :: String -> String\n-- tal que (ecoC xs) es la cadena obtenida a partir de la cadena xs\n-- repitiendo cada elemento tantas veces como indica su posici\u00f3n: el\n-- primer elemento se repite 1 vez, el segundo 2 veces y as\u00ed\n-- sucesivamente. Por ejemplo, \n--    ecoC \"abcd\"  ==  \"abbcccdddd\"\n-- ---------------------------------------------------------------------\n\necoC :: String -> String\necoC xs = concat [replicate i x | (i,x) <- zip [1..] xs]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3.2. Definir, por recursi\u00f3n, la funci\u00f3n\n--    ecoR :: String -> String\n-- tal que (ecoR xs) es la cadena obtenida a partir de la cadena xs\n-- repitiendo cada elemento tantas veces como indica su posici\u00f3n: el\n-- primer elemento se repite 1 vez, el segundo 2 veces y as\u00ed\n-- sucesivamente. Por ejemplo, \n--    ecoR \"abcd\"  ==  \"abbcccdddd\"\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa definici\u00f3n \necoR :: String -> String\necoR = aux 1\n    where aux n []     = []\n          aux n (x:xs) = replicate n x ++ aux (n+1) xs\n\n-- 2\u00aa definici\u00f3n\necoR2 :: String -> String\necoR2 [x] = [x]\necoR2 xs  = (ecoR2 . init) xs ++ repiteFinita (length xs) (last xs)\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 ejercicios de evaluaci\u00f3n perezosa y listas infinitas de la 11\u00aa relaci\u00f3n. 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":[260],"tags":[270,313],"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\/5660"}],"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=5660"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5660\/revisions"}],"predecessor-version":[{"id":5661,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5660\/revisions\/5661"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=5660"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=5660"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=5660"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}