{"id":4615,"date":"2014-11-24T17:09:34","date_gmt":"2014-11-24T16:09:34","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=4615"},"modified":"2014-11-24T17:09:34","modified_gmt":"2014-11-24T16:09:34","slug":"i1m2014-ejercicios-de-evaluacion-perezosa-y-listas-infinitas-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2014-ejercicios-de-evaluacion-perezosa-y-listas-infinitas-en-haskell\/","title":{"rendered":"I1M2014: Ejercicios de evaluaci\u00f3n perezosa y listas infinitas en Haskell"},"content":{"rendered":"<p>En clase de hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-14\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> hemos comentando las soluciones de los ejercicios de evaluaci\u00f3n perezosa y listas infinitas de la 9\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 cuyas\n-- transparencias se encuentran en  \n--    http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-14\/temas\/tema-10.pdf\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\nrepite :: a -> [a]\nrepite x = x : repite x\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-- ---------------------------------------------------------------------\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-- ---------------------------------------------------------------------\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-- ---------------------------------------------------------------------\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 xs = aux 1 xs\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\n-- ---------------------------------------------------------------------\n-- Ejercicio 4. 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-- \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 5.1. Definir, por recursi\u00f3n, la funci\u00f3n\n--    agrupaR :: Int -> [a] -> [[a]]\n-- tal que (agrupaR 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> agrupaR 2 [3,1,5,8,2,7]\n--    [[3,1],[5,8],[2,7]]\n--    ghci> agrupaR 2 [3,1,5,8,2,7,9] \n--    [[3,1],[5,8],[2,7],[9]]\n--    ghci> agrupaR 5 \"todo necio confunde valor y precio\"\n--    [\"todo \",\"necio\",\" conf\",\"unde \",\"valor\",\" y pr\",\"ecio\"]\n-- ---------------------------------------------------------------------------- \n\nagrupaR :: Int -> [a] -> [[a]]\nagrupaR n [] = []\nagrupaR n xs = take n xs : agrupaR n (drop n xs)\n\n-- ----------------------------------------------------------------------------\n-- Ejercicio 5.2. Definir, de manera no recursiva con iterate, 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 5.3. Comprobar con QuickCheck que todos los grupos de\n-- (agrupa n xs) tienen longitud n (salvo el \u00faltimo que puede tener una\n-- longitud menor). \n-- ---------------------------------------------------------------------------- \n\n-- La 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-- ----------------------------------------------------------------------------\n-- Ejercicio 5.4. Comprobar con QuickCheck que combinando todos los\n-- grupos de ((agrupa n xs)) se obtiene la lista xs. \n-- ---------------------------------------------------------------------------- \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 6.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 6.2. Definir, por recursi\u00f3n, la funci\u00f3n \n--    collatzR :: Integer -> [Integer]\n-- tal que (collatzR n) es la \u00f3rbita de CollatzR de n hasta alcanzar el\n-- 1. Por ejemplo,\n--    collatzR 13  ==  [13,40,20,10,5,16,8,4,2,1]\n-- ---------------------------------------------------------------------\n\ncollatzR :: Integer -> [Integer]\ncollatzR 1 = [1]\ncollatzR n = n : collatzR (siguiente n)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 6.3. Definir, sin recursi\u00f3n y con iterate, 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 6.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 6.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\nmenorCollatzSupera2 :: Integer -> Integer\nmenorCollatzSupera2 x = head [n | n <- [1..], t <- collatz n, t > x]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 7. 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 8.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 8.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 8.3. 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-- \u00a7 La lista infinita de factoriales,                                --\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 9.1. Definir, por comprensi\u00f3n, la funci\u00f3n\n--    factoriales1 :: [Integer]\n-- tal que factoriales1 es la lista de los factoriales. Por ejemplo,\n--    take 10 factoriales1  ==  [1,1,2,6,24,120,720,5040,40320,362880]\n-- ---------------------------------------------------------------------\n\nfactoriales1 :: [Integer]\nfactoriales1 = [factorial n | n <- [0..]]\n\n-- (factorial n) es el factorial de n. Por ejemplo,\n--    factorial 4  ==  24\nfactorial :: Integer -> Integer\nfactorial n = product [1..n]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 9.2. Definir, usando zipWith, la funci\u00f3n\n--    factoriales2 :: [Integer]\n-- tal que factoriales2 es la lista de los factoriales. Por ejemplo,\n--    take 10 factoriales2  ==  [1,1,2,6,24,120,720,5040,40320,362880]\n-- ---------------------------------------------------------------------\n\nfactoriales2 :: [Integer]\nfactoriales2 = 1 : zipWith (*) [1..] factoriales2\n\n-- El c\u00e1lculo es\n--    take 4 factoriales2\n--    = take 4 (1 : zipWith (*) [1..] factoriales2)\n--    = 1 : take 3 (zipWith (*) [1..] factoriales2)\n--    = 1 : take 3 (zipWith (*) [1..] [1|R1])           {R1 es tail factoriales2}\n--    = 1 : take 3 (1 : zipWith (*) [2..] [R1])      \n--    = 1 : 1 : take 2 (zipWith (*) [2..] [1|R2])       {R2 es drop 2 factoriales2}  \n--    = 1 : 1 : take 2 (2 : zipWith (*) [3..] [R2])\n--    = 1 : 1 : 2 : take 1 (zipWith (*) [3..] [2|R3])    {R3 es drop 3 factoriales2}  \n--    = 1 : 1 : 2 : take 1 (6 : zipWith (*) [4..] [R3])  \n--    = 1 : 1 : 2 : 6 : take 0 (zipWith (*) [4..] [R3])  \n--    = 1 : 1 : 2 : 6 : []\n--    = [1, 1, 2, 6]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 9.3. Comparar el tiempo y espacio necesarios para calcular\n-- las siguientes expresiones\n--    let xs = take 3000 factoriales1 in (sum xs - sum xs)\n--    let xs = take 3000 factoriales2 in (sum xs - sum xs)\n-- ---------------------------------------------------------------------\n\n-- El c\u00e1lculo es\n--    ghci> let xs = take 3000 factoriales1 in (sum xs - sum xs)\n--    0\n--    (17.51 secs, 5631214332 bytes)\n--    ghci> let xs = take 3000 factoriales2 in (sum xs - sum xs)\n--    0\n--    (0.04 secs, 17382284 bytes)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 9.4. Definir, por recursi\u00f3n, la funci\u00f3n\n--    factoriales3 :: [Integer]\n-- tal que factoriales3 es la lista de los factoriales. Por ejemplo,\n--    take 10 factoriales3  ==  [1,1,2,6,24,120,720,5040,40320,362880]\n-- ---------------------------------------------------------------------\n\nfactoriales3 :: [Integer]\nfactoriales3 = 1 : aux 1 [1..]\n    where aux x (y:ys) = z : aux z ys where z = x*y\n\n-- El c\u00e1lculo es\n--    take 4 factoriales3\n--    = take 4 (1 : aux 1 [1..])\n--    = 1 : take 3 (aux 1 [1..])\n--    = 1 : take 3 (1 : aux 1 [2..])\n--    = 1 : 1 : take 2 (aux 1 [2..])\n--    = 1 : 1 : take 2 (2 : aux 2 [3..])\n--    = 1 : 1 : 2 : take 1 (aux 2 [3..])\n--    = 1 : 1 : 2 : take 1 (6 : aux 6 [4..])\n--    = 1 : 1 : 2 : 6 : take 0 (aux 6 [4..])\n--    = 1 : 1 : 2 : 6 : []\n--    = [1,1,2,6]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 9.5. Comparar el tiempo y espacio necesarios para calcular\n-- las siguientes expresiones\n--    let xs = take 3000 factoriales2 in (sum xs - sum xs)\n--    let xs = take 3000 factoriales3 in (sum xs - sum xs)\n-- ---------------------------------------------------------------------\n\n-- El c\u00e1lculo es\n--    ghci> let xs = take 3000 factoriales2 in (sum xs - sum xs)\n--    0\n--    (0.04 secs, 17382284 bytes)\n--    ghci> let xs = take 3000 factoriales3 in (sum xs - sum xs)\n--    0\n--    (0.04 secs, 18110224 bytes)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 9.6. Definir, usando scanl1, la funci\u00f3n\n--    factoriales4 :: [Integer]\n-- tal que factoriales4 es la lista de los factoriales. Por ejemplo,\n--    take 10 factoriales4  ==  [1,1,2,6,24,120,720,5040,40320,362880]\n-- ---------------------------------------------------------------------\n\nfactoriales4 :: [Integer]\nfactoriales4 = 1 : scanl1 (*) [1..]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 9.7. Comparar el tiempo y espacio necesarios para calcular\n-- las siguientes expresiones\n--    let xs = take 3000 factoriales3 in (sum xs - sum xs)\n--    let xs = take 3000 factoriales4 in (sum xs - sum xs)\n-- ---------------------------------------------------------------------\n\n-- El c\u00e1lculo es\n--    ghci> let xs = take 3000 factoriales3 in (sum xs - sum xs)\n--    0\n--    (0.04 secs, 18110224 bytes)\n--    ghci> let xs = take 3000 factoriales4 in (sum xs - sum xs)\n--    0\n--    (0.03 secs, 11965328 bytes)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 9.8. Definir, usando iterate, la funci\u00f3n\n--    factoriales5 :: [Integer]\n-- tal que factoriales5 es la lista de los factoriales. Por ejemplo,\n--    take 10 factoriales5  ==  [1,1,2,6,24,120,720,5040,40320,362880]\n-- ---------------------------------------------------------------------\n\nfactoriales5 :: [Integer]\nfactoriales5 = map snd aux\n    where aux = iterate f (1,1) where f (x,y) = (x+1,x*y)\n\n-- El c\u00e1lculo es\n--    take 4 factoriales5\n--    = take 4 (map snd aux)\n--    = take 4 (map snd (iterate f (1,1)))\n--    = take 4 (map snd [(1,1),(2,1),(3,2),(4,6),...])\n--    = take 4 [1,1,2,6,...]\n--    = [1,1,2,6]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 9.9. Comparar el tiempo y espacio necesarios para calcular\n-- las siguientes expresiones\n--    let xs = take 3000 factoriales4 in (sum xs - sum xs)\n--    let xs = take 3000 factoriales5 in (sum xs - sum xs)\n-- ---------------------------------------------------------------------\n\n-- El c\u00e1lculo es\n--    ghci> let xs = take 3000 factoriales4 in (sum xs - sum xs)\n--    0\n--    (0.04 secs, 18110224 bytes)\n--    ghci> let xs = take 3000 factoriales5 in (sum xs - sum xs)\n--    0\n--    (0.03 secs, 11965760 bytes)\n\n-- ---------------------------------------------------------------------\n-- \u00a7 La sucesi\u00f3n de Fibonacci                                         --\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 10.1. La sucesi\u00f3n de Fibonacci est\u00e1 definida por\n--    f(0) = 0\n--    f(1) = 1\n--    f(n) = f(n-1)+f(n-2), si n > 1.\n-- \n-- Definir la funci\u00f3n\n--    fib :: Integer -> Integer\n-- tal que (fib n) es el n-\u00e9simo t\u00e9rmino de la sucesi\u00f3n de Fibonacci. \n-- Por ejemplo,\n--    fib 8  ==  21\n-- ---------------------------------------------------------------------\n\nfib :: Integer -> Integer\nfib 0 = 0\nfib 1 = 1\nfib n = fib (n-1) + fib (n-2)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 10.2. Definir, por comprensi\u00f3n, la funci\u00f3n\n--    fibs1 :: [Integer]\n-- tal que fibs1 es la sucesi\u00f3n de Fibonacci. Por ejemplo,\n--    take 10 fibs1  ==  [0,1,1,2,3,5,8,13,21,34]\n-- ---------------------------------------------------------------------\n\nfibs1 :: [Integer]\nfibs1 = [fib n | n <- [0..]]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 10.3. Definir, por recursi\u00f3n, la funci\u00f3n\n--    fibs2 :: [Integer]\n-- tal que fibs2 es la sucesi\u00f3n de Fibonacci. Por ejemplo,\n--    take 10 fibs2  ==  [0,1,1,2,3,5,8,13,21,34]\n-- ---------------------------------------------------------------------\n\nfibs2 :: [Integer]\nfibs2 = aux 0 1\n    where aux x y = x : aux y (x+y)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 10.4. Comparar el tiempo y espacio necesarios para calcular\n-- las siguientes expresiones\n--    let xs = take 30 fibs1 in (sum xs - sum xs)\n--    let xs = take 30 fibs2 in (sum xs - sum xs)\n-- ---------------------------------------------------------------------\n\n-- El c\u00e1lculo es\n--    ghci> let xs = take 30 fibs1 in (sum xs - sum xs)\n--    0\n--    (6.02 secs, 421589672 bytes)\n--    ghci> let xs = take 30 fibs2 in (sum xs - sum xs)\n--    0\n--    (0.01 secs, 515856 bytes)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 10.5. Definir, por recursi\u00f3n con zipWith, la funci\u00f3n\n--    fibs3 :: [Integer]\n-- tal que fibs3 es la sucesi\u00f3n de Fibonacci. Por ejemplo,\n--    take 10 fibs3  ==  [0,1,1,2,3,5,8,13,21,34]\n-- ---------------------------------------------------------------------\n\nfibs3 :: [Integer]\nfibs3 = 0 : 1: zipWith (+) fibs3 (tail fibs3)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 10.6. Comparar el tiempo y espacio necesarios para calcular\n-- las siguientes expresiones\n--    let xs = take 40000 fibs2 in (sum xs - sum xs)\n--    let xs = take 40000 fibs3 in (sum xs - sum xs)\n-- ---------------------------------------------------------------------\n\n-- El c\u00e1lculo es\n--    ghci> let xs = take 40000 fibs2 in (sum xs - sum xs)\n--    0\n--    (0.90 secs, 221634544 bytes)\n--    ghci> let xs = take 40000 fibs3 in (sum xs - sum xs)\n--    0\n--    (1.14 secs, 219448176 bytes)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 10.7. Definir, por recursi\u00f3n con acumuladores, la funci\u00f3n \n--    fibs4 :: [Integer]\n-- tal que fibs4 es la sucesi\u00f3n de Fibonacci. Por ejemplo,\n--    take 10 fibs4  ==  [0,1,1,2,3,5,8,13,21,34]\n-- ---------------------------------------------------------------------\n\nfibs4 :: [Integer]\nfibs4 = fs where (xs,ys,fs) = (zipWith (+) ys fs, 1:xs, 0:ys)\n\n-- El c\u00e1lculo de fibs4 es \n--   +------------------------+-----------------+-------------------+\n--   | xs = zipWith (+) ys fs | ys = 1:xs       | fs = 0:ys         |\n--   +------------------------+-----------------+-------------------+\n--   |                        | 1:...           | 0:...             |\n--   |                        | ^               | ^                 |\n--   | 1:...                  | 1:1:...         | 0:1:1:...         |\n--   |                        |   ^             |   ^               |\n--   | 1:2:...                | 1:1:2:...       | 0:1:1:2:...       |\n--   |                        |     ^           |     ^             |\n--   | 1:2:3:...              | 1:1:2:3:...     | 0:1:1:2:3:...     |\n--   |                        |       ^         |       ^           |\n--   | 1:2:3:5:...            | 1:1:2:3:5:...   | 0:1:1:2:3:5:...   |\n--   |                        |         ^       |         ^         |\n--   | 1:2:3:5:8:...          | 1:1:2:3:5:8:... | 0:1:1:2:3:5:8:... |\n--   +------------------------+-----------------+-------------------+\n-- En la tercera columna se va construyendo la sucesi\u00f3n.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 10.8. Comparar el tiempo y espacio necesarios para calcular\n-- las siguientes expresiones\n--    let xs = take 40000 fibs3 in (sum xs - sum xs)\n--    let xs = take 40000 fibs4 in (sum xs - sum xs)\n-- ---------------------------------------------------------------------\n\n-- El c\u00e1lculo es\n--    ghci> let xs = take 40000 fibs2 in (sum xs - sum xs)\n--    0\n--    (0.90 secs, 221634544 bytes)\n--    ghci> let xs = take 40000 fibs4 in (sum xs - sum xs)\n--    0\n--    (0.84 secs, 219587064 bytes)\n\n-- ---------------------------------------------------------------------\n-- \u00a7 El tri\u00e1ngulo de Pascal                                           --\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 11.1. El tri\u00e1ngulo de Pascal es un tri\u00e1ngulo de n\u00fameros\n--          1\n--         1 1\n--        1 2 1\n--      1  3 3  1\n--     1 4  6  4 1\n--    1 5 10 10 5 1\n--   ...............\n-- construido de la siguiente forma\n-- * la primera fila est\u00e1 formada por el n\u00famero 1;\n-- * las filas siguientes se construyen sumando los n\u00fameros adyacentes\n--   de la fila superior y a\u00f1adiendo un 1 al principio y al final de la\n--   fila. \n-- \n-- Definir la funci\u00f3n\n--    pascal1 :: [[Integer]]\n-- tal que pascal es la lista de las l\u00edneas del tri\u00e1ngulo de Pascal. Por\n-- ejemplo, \n--    ghci> take 6 pascal1\n--    [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1],[1,5,10,10,5,1]]\n-- ---------------------------------------------------------------------\n\npascal1 :: [[Integer]]\npascal1 = iterate f [1]\n    where f xs = zipWith (+) (0:xs) (xs++[0])\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 11.2. Definir la funci\u00f3n\n--    pascal2 :: [[Integer]]\n-- tal que pascal es la lista de las l\u00edneas del tri\u00e1ngulo de Pascal. Por\n-- ejemplo, \n--    ghci> take 6 pascal2\n--    [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1],[1,5,10,10,5,1]]\n-- ---------------------------------------------------------------------\n\npascal2 :: [[Integer]]\npascal2 = [1] : map f pascal2\n    where f xs = zipWith (+) (0:xs) (xs++[0])\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 11.3. Escribir la traza del c\u00e1lculo de la expresi\u00f3n\n--    take 4 pascal\n-- ---------------------------------------------------------------------\n\n-- Nota: El c\u00e1lculo es\n--    take 4 pascal\n--    = take 4 ([1] : map f pascal)\n--    = [1] : (take 3 (map f pascal))    \n--    = [1] : (take 3 (map f ([1]:R1pascal)))\n--    = [1] : (take 3 ((f [1]) : map R1pascal)))\n--    = [1] : (take 3 ((zipWith (+) (0:[1]) ([1]++[0]) : map R1pascal)))\n--    = [1] : (take 3 ((zipWith (+) [0,1] [1,0]) : map R1pascal)))\n--    = [1] : (take 3 ([1,1] : map R1pascal)))\n--    = [1] : [1,1] : (take 2 (map R1pascal)))\n--    = [1] : [1,1] : (take 2 (map ([1,1]:R2pascal)))\n--    = [1] : [1,1] : (take 2 ((f [1,1]) : map R2pascal)))\n--    = [1] : [1,1] : (take 2 ((zipWith (+) (0:[1,1]) ([1,1]++[0]) : map R2pascal)))\n--    = [1] : [1,1] : (take 2 ((zipWith (+) [0,1,1] [1,1,0]) : map R2pascal)))\n--    = [1] : [1,1] : (take 2 ([1,2,1] : map R2pascal)))\n--    = [1] : [1,1] : [1,2,1] : (take 1 (map R2pascal)))\n--    = [1] : [1,1] : [1,2,1] : (take 1 (map ([1,2,1]:R3pascal)))\n--    = [1] : [1,1] : [1,2,1] : (take 1 ((f [1,2,1]) : map R3pascal)))\n--    = [1] : [1,1] : [1,2,1] : (take 1 ((zipWith (+) (0:[1,2,1]) ([1,2,1]++[0]) : map R3pascal)))\n--    = [1] : [1,1] : [1,2,1] : (take 1 ((zipWith (+) [0,1,2,1] [1,2,1,0]) : map R3pascal)))\n--    = [1] : [1,1] : [1,2,1] : (take 1 ([1,3,3,1] : map R3pascal)))\n--    = [1] : [1,1] : [1,2,1] : [1,3,3,1] : (take 0 (map R3pascal)))\n--    = [1] : [1,1] : [1,2,1] : [1,3,3,1] : []\n--    = [[1],[1,1],[1,2,1],[1,3,3,1]]\n-- en el c\u00e1lculo con R1pascal, R2pascal y R3pascal es la el tri\u00e1ngulo de\n-- Pascal si el primero, los dos primeros o los tres primeros elementos,\n-- respectivamente. \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 ejercicios de evaluaci\u00f3n perezosa y listas infinitas de la 9\u00aa relaci\u00f3n. Los ejercicios, 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":[238],"tags":[270,305,126],"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\/4615"}],"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=4615"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4615\/revisions"}],"predecessor-version":[{"id":4616,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4615\/revisions\/4616"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=4615"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=4615"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=4615"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}