PeH: Sucesión de Fibonacci, evaluación perezosa y números construibles
Continuando con ejemplos de evaluación perezosa en Haskell, un clásico es la sucsión de Fibonacci: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, … cuyos dos primeros términos son 0 y 1 y los restantes se calcula sumando los dos anteriores.
En la siguiente relación de ejercicios se presentan distintas definiciones de la sucesión de Fibonacci basadas en la evaluación perezosa y la última
usando números construibles mediante la librería Data.Real.Constructible.
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 |
-- --------------------------------------------------------------------- -- § Librerías auxiliares -- -- --------------------------------------------------------------------- import Data.Real.Constructible -- --------------------------------------------------------------------- -- Ejercicio 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. 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 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 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 5. Definir, mediante una red de procesos, 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 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 7. Definir, mediante una red de procesos 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 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) -- --------------------------------------------------------------------- -- Ejercicio 9. El n-ésimo término de la sucesión de Fibonacci es -- (((1+sqrt(5))/2)^n - ((1-sqrt(5))/2)^n)/sqrt(5) -- -- Definir, usando la expresión anterior y los número construibles, la -- función -- fib2 :: Int -> Construct -- tal que (fib2 n) es el n-ésimo término de la sucesión de Fibonacci. -- Por ejemplo, -- fib 8 == 21 -- --------------------------------------------------------------------- fib2 :: Int -> Construct fib2 n = (((1+sqrt(5))/2)^n - ((1-sqrt(5))/2)^n)/sqrt(5) -- --------------------------------------------------------------------- -- Ejercicio 11. Comparar el tiempo y espacio necesarios para calcular -- las siguientes expresiones -- fibs4 !! 100000*0 -- (fib2 100000)*0 -- --------------------------------------------------------------------- -- El cálculo es -- ghci> fibs4 !! 100000*0 -- 0 -- (1.88 secs, 445800056 bytes) -- ghci> (fib2 100000)*0 -- 0 -- (0.04 secs, 1932628 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.