Menu Close

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.

-- ---------------------------------------------------------------------
-- § 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

PeH