PeH: Lista de factoriales perezosa en Haskell
Continuando con la serie sobre evaluación perezosa en Haskell, otro ejemplo clásico es la lista de los factoriales: 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, …
En la siguiente relación se proponen distintas definiciones para calcular la lista de factoriales.
|
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 |
-- --------------------------------------------------------------------- -- Ejercicio 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 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 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 4. Definir, usando una red de procesos, 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 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 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 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 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 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) |
Destino
La anterior relación de ejercicios la ha elaborado para
- la asignatura de Informática de 1º del Grado en Matemáticas y
- la ampliación del libro Piensa en Haskell.