I1M2013: Ejercicios de evaluación perezosa y listas infinitas en Haskell (3)
En la clase de hoy de Informática de 1º del Grado en Matemáticas hemos comentado las soluciones de los dos primeros ejercicios sobre evaluación perezosa y listas infinitas de la relación 17.
Los ejercicios de la relación 17, y sus soluciones, se muestran a continuación.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 |
-- --------------------------------------------------------------------- -- § Librerías auxiliares -- -- --------------------------------------------------------------------- import Data.Char import Data.List import Test.QuickCheck -- --------------------------------------------------------------------- -- § La lista infinita de factoriales, -- -- --------------------------------------------------------------------- -- --------------------------------------------------------------------- -- Ejercicio 1.1. Definir, por comprensión, la función -- factoriales1 :: [Integer] -- tal que factoriales1 es la lista de los factoriales. Por ejemplo, -- take 10 factoriales1 == [1,1,2,6,24,120,720,5040,40320,362880] -- --------------------------------------------------------------------- factoriales1 :: [Integer] factoriales1 = [factorial n | n <- [0..]] -- (factorial n) es el factorial de n. Por ejemplo, -- factorial 4 == 24 factorial :: Integer -> Integer factorial n = product [1..n] -- --------------------------------------------------------------------- -- Ejercicio 1.2. Definir, usando zipWith, la función -- factoriales2 :: [Integer] -- tal que factoriales2 es la lista de los factoriales. Por ejemplo, -- take 10 factoriales2 == [1,1,2,6,24,120,720,5040,40320,362880] -- --------------------------------------------------------------------- factoriales2 :: [Integer] factoriales2 = 1 : zipWith (*) [1..] factoriales2 -- --------------------------------------------------------------------- -- Ejercicio 1.3. Comparar el tiempo y espacio necesarios para calcular -- las siguientes expresiones -- let xs = take 3000 factoriales1 in (sum xs - sum xs) -- let xs = take 3000 factoriales2 in (sum xs - sum xs) -- --------------------------------------------------------------------- -- El cálculo es -- ghci> let xs = take 3000 factoriales1 in (sum xs - sum xs) -- 0 -- (17.51 secs, 5631214332 bytes) -- ghci> let xs = take 3000 factoriales2 in (sum xs - sum xs) -- 0 -- (0.04 secs, 17382284 bytes) -- --------------------------------------------------------------------- -- Ejercicio 1.4. Definir, por recursión, la función -- factoriales3 :: [Integer] -- tal que factoriales3 es la lista de los factoriales. Por ejemplo, -- take 10 factoriales3 == [1,1,2,6,24,120,720,5040,40320,362880] -- --------------------------------------------------------------------- factoriales3 :: [Integer] factoriales3 = 1 : aux 1 [1..] where aux x (y:ys) = z : aux z ys where z = x*y -- --------------------------------------------------------------------- -- Ejercicio 1.5. Comparar el tiempo y espacio necesarios para calcular -- las siguientes expresiones -- let xs = take 3000 factoriales2 in (sum xs - sum xs) -- let xs = take 3000 factoriales3 in (sum xs - sum xs) -- --------------------------------------------------------------------- -- El cálculo es -- ghci> let xs = take 3000 factoriales2 in (sum xs - sum xs) -- 0 -- (0.04 secs, 17382284 bytes) -- ghci> let xs = take 3000 factoriales3 in (sum xs - sum xs) -- 0 -- (0.04 secs, 18110224 bytes) -- --------------------------------------------------------------------- -- Ejercicio 1.6. Definir, usando scanl1, la función -- factoriales4 :: [Integer] -- tal que factoriales4 es la lista de los factoriales. Por ejemplo, -- take 10 factoriales4 == [1,1,2,6,24,120,720,5040,40320,362880] -- --------------------------------------------------------------------- factoriales4 :: [Integer] factoriales4 = 1 : scanl1 (*) [1..] -- --------------------------------------------------------------------- -- Ejercicio 1.7. Comparar el tiempo y espacio necesarios para calcular -- las siguientes expresiones -- let xs = take 3000 factoriales3 in (sum xs - sum xs) -- let xs = take 3000 factoriales4 in (sum xs - sum xs) -- --------------------------------------------------------------------- -- El cálculo es -- ghci> let xs = take 3000 factoriales3 in (sum xs - sum xs) -- 0 -- (0.04 secs, 18110224 bytes) -- ghci> let xs = take 3000 factoriales4 in (sum xs - sum xs) -- 0 -- (0.03 secs, 11965328 bytes) -- --------------------------------------------------------------------- -- Ejercicio 1.8. Definir, usando iterate, la función -- factoriales5 :: [Integer] -- tal que factoriales5 es la lista de los factoriales. Por ejemplo, -- take 10 factoriales5 == [1,1,2,6,24,120,720,5040,40320,362880] -- --------------------------------------------------------------------- factoriales5 :: [Integer] factoriales5 = map snd aux where aux = iterate f (1,1) where f (x,y) = (x+1,x*y) -- --------------------------------------------------------------------- -- Ejercicio 1.9. Comparar el tiempo y espacio necesarios para calcular -- las siguientes expresiones -- let xs = take 3000 factoriales4 in (sum xs - sum xs) -- let xs = take 3000 factoriales5 in (sum xs - sum xs) -- --------------------------------------------------------------------- -- El cálculo es -- ghci> let xs = take 3000 factoriales4 in (sum xs - sum xs) -- 0 -- (0.04 secs, 18110224 bytes) -- ghci> let xs = take 3000 factoriales5 in (sum xs - sum xs) -- 0 -- (0.03 secs, 11965760 bytes) -- --------------------------------------------------------------------- -- § La sucesión de Fibonacci -- -- --------------------------------------------------------------------- -- --------------------------------------------------------------------- -- Ejercicio 2.1. La sucesión de Fibonacci está definida por -- f(0) = 0 -- f(1) = 1 -- f(n) = f(n-1)+f(n-2), si n > 1. -- -- Definir la función -- fib :: Integer -> Integer -- tal que (fib n) es el n-ésimo término de la sucesión de Fibonacci. -- Por ejemplo, -- fib 8 == 21 -- --------------------------------------------------------------------- fib :: Integer -> Integer fib 0 = 0 fib 1 = 1 fib n = fib (n-1) + fib (n-2) -- --------------------------------------------------------------------- -- Ejercicio 2.2. Definir, por comprensión, la función -- fibs1 :: [Integer] -- tal que fibs1 es la sucesión de Fibonacci. Por ejemplo, -- take 10 fibs1 == [0,1,1,2,3,5,8,13,21,34] -- --------------------------------------------------------------------- fibs1 :: [Integer] fibs1 = [fib n | n <- [0..]] -- --------------------------------------------------------------------- -- Ejercicio 2.3. Definir, por recursión, la función -- fibs2 :: [Integer] -- tal que fibs2 es la sucesión de Fibonacci. Por ejemplo, -- take 10 fibs2 == [0,1,1,2,3,5,8,13,21,34] -- --------------------------------------------------------------------- fibs2 :: [Integer] fibs2 = aux 0 1 where aux x y = x : aux y (x+y) -- --------------------------------------------------------------------- -- Ejercicio 2.4. Comparar el tiempo y espacio necesarios para calcular -- las siguientes expresiones -- let xs = take 30 fibs1 in (sum xs - sum xs) -- let xs = take 30 fibs2 in (sum xs - sum xs) -- --------------------------------------------------------------------- -- El cálculo es -- ghci> let xs = take 30 fibs1 in (sum xs - sum xs) -- 0 -- (6.02 secs, 421589672 bytes) -- ghci> let xs = take 30 fibs2 in (sum xs - sum xs) -- 0 -- (0.01 secs, 515856 bytes) -- --------------------------------------------------------------------- -- Ejercicio 2.5. Definir, por recursión con zipWith, la función -- fibs3 :: [Integer] -- tal que fibs3 es la sucesión de Fibonacci. Por ejemplo, -- take 10 fibs3 == [0,1,1,2,3,5,8,13,21,34] -- --------------------------------------------------------------------- fibs3 :: [Integer] fibs3 = 0 : 1: zipWith (+) fibs3 (tail fibs3) -- --------------------------------------------------------------------- -- Ejercicio 2.6. Comparar el tiempo y espacio necesarios para calcular -- las siguientes expresiones -- let xs = take 40000 fibs2 in (sum xs - sum xs) -- let xs = take 40000 fibs3 in (sum xs - sum xs) -- --------------------------------------------------------------------- -- El cálculo es -- ghci> let xs = take 40000 fibs2 in (sum xs - sum xs) -- 0 -- (0.90 secs, 221634544 bytes) -- ghci> let xs = take 40000 fibs3 in (sum xs - sum xs) -- 0 -- (1.14 secs, 219448176 bytes) -- --------------------------------------------------------------------- -- Ejercicio 2.7. Definir, por recursión con acumuladores, la función -- fibs4 :: [Integer] -- tal que fibs4 es la sucesión de Fibonacci. Por ejemplo, -- take 10 fibs4 == [0,1,1,2,3,5,8,13,21,34] -- --------------------------------------------------------------------- fibs4 :: [Integer] fibs4 = fs where (xs,ys,fs) = (zipWith (+) ys fs, 1:xs, 0:ys) -- --------------------------------------------------------------------- -- Ejercicio 2.8. Comparar el tiempo y espacio necesarios para calcular -- las siguientes expresiones -- let xs = take 40000 fibs3 in (sum xs - sum xs) -- let xs = take 40000 fibs4 in (sum xs - sum xs) -- --------------------------------------------------------------------- -- El cálculo es -- ghci> let xs = take 40000 fibs2 in (sum xs - sum xs) -- 0 -- (0.90 secs, 221634544 bytes) -- ghci> let xs = take 40000 fibs4 in (sum xs - sum xs) -- 0 -- (0.84 secs, 219587064 bytes) |