-- I1M 2021-22: Relación 11 solución
-- Evaluación perezosa y listas infinitas.
-- Departamento de Ciencias de la Computación e I.A.
-- Universidad de Sevilla
-- =====================================================================
-- ---------------------------------------------------------------------
-- Introducción --
-- ---------------------------------------------------------------------
-- En esta relación se presentan ejercicios con listas infinitas y
-- evaluación perezosa. Estos ejercicios corresponden al tema 10 que
-- se encuentra en
-- https://www.cs.us.es/~jalonso/cursos/i1m/temas/tema-10.html
-- ---------------------------------------------------------------------
-- Importación de librerías auxiliares
-- ---------------------------------------------------------------------
import Test.QuickCheck
-- ---------------------------------------------------------------------
-- Ejercicio 1.1. Definir, por recursión, la función
-- repite :: a -> [a]
-- tal que (repite x) es la lista infinita cuyos elementos son x. Por
-- ejemplo,
-- repite 5 == [5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,...
-- take 3 (repite 5) == [5,5,5]
--
-- Nota: La función repite es equivalente a la función repeat definida
-- en el preludio de Haskell.
-- ---------------------------------------------------------------------
-- 1ª definición:
repite1 :: a -> [a]
repite1 x = x : repite1 x
-- 2ª definición:
repite2 :: a -> [a]
repite2 x = ys
where ys = x:ys
-- La 2ª definición es más eficiente:
-- ghci> last (take 100000000 (repite1 5))
-- 5
-- (46.56 secs, 16001567944 bytes)
-- ghci> last (take 100000000 (repite2 5))
-- 5
-- (2.34 secs, 5601589608 bytes)
-- Usaremos como repite la 2ª definición
repite :: a -> [a]
repite = repite2
-- ---------------------------------------------------------------------
-- Ejercicio 1.2. Definir, por comprensión, la función
-- repiteC :: a -> [a]
-- tal que (repiteC x) es la lista infinita cuyos elementos son x. Por
-- ejemplo,
-- repiteC 5 == [5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,...
-- take 3 (repiteC 5) == [5,5,5]
--
-- Nota: La función repiteC es equivalente a la función repeat definida
-- en el preludio de Haskell.
-- ---------------------------------------------------------------------
repiteC :: a -> [a]
repiteC x = [x | _ <- [1..]]
-- La función repite2 es más eficiente que repiteC
-- ghci> last (take 10000000 (repiteC 5))
-- 5
-- (6.05 secs, 1,997,740,536 bytes)
-- ghci> last (take 10000000 (repite2 5))
-- 5
-- (0.31 secs, 541,471,280 bytes)
-- ---------------------------------------------------------------------
-- Ejercicio 2.1. Definir, por recursión, la función
-- repiteFinitaR :: Int-> a -> [a]
-- tal que (repiteFinitaR n x) es la lista con n elementos iguales a
-- x. Por ejemplo,
-- repiteFinitaR 3 5 == [5,5,5]
--
-- Nota: La función repiteFinitaR es equivalente a la función replicate
-- definida en el preludio de Haskell.
-- ---------------------------------------------------------------------
repiteFinitaR :: Int -> a -> [a]
repiteFinitaR n x | n <= 0 = []
| otherwise = x : repiteFinitaR (n-1) x
-- ---------------------------------------------------------------------
-- Ejercicio 2.2. Definir, por comprensión, la función
-- repiteFinitaC :: Int-> a -> [a]
-- tal que (repiteFinitaC n x) es la lista con n elementos iguales a
-- x. Por ejemplo,
-- repiteFinitaC 3 5 == [5,5,5]
--
-- Nota: La función repiteFinitaC es equivalente a la función replicate
-- definida en el preludio de Haskell.
-- ---------------------------------------------------------------------
repiteFinitaC :: Int -> a -> [a]
repiteFinitaC n x = [x | _ <- [1..n]]
-- La función repiteFinitaC es más eficiente que repiteFinitaR
-- ghci> last (repiteFinitaR 10000000 5)
-- 5
-- (17.04 secs, 2,475,222,448 bytes)
-- ghci> last (repiteFinitaC 10000000 5)
-- 5
-- (5.43 secs, 1,511,227,176 bytes)
-- ---------------------------------------------------------------------
-- Ejercicio 2.3. Definir, usando repite, la función
-- repiteFinita :: Int-> a -> [a]
-- tal que (repiteFinita n x) es la lista con n elementos iguales a
-- x. Por ejemplo,
-- repiteFinita 3 5 == [5,5,5]
--
-- Nota: La función repiteFinita es equivalente a la función replicate
-- definida en el preludio de Haskell.
-- ---------------------------------------------------------------------
repiteFinita :: Int -> a -> [a]
repiteFinita n x = take n (repite x)
-- La función repiteFinita es más eficiente que repiteFinitaC
-- ghci> last (repiteFinitaC 10000000 5)
-- 5
-- (5.43 secs, 1,511,227,176 bytes)
-- ghci> last (repiteFinita 10000000 5)
-- 5
-- (0.29 secs, 541,809,248 bytes)
-- 2ª definición
repiteFinita2 :: Int -> a -> [a]
repiteFinita2 n = take n . repite
-- ---------------------------------------------------------------------
-- Ejercicio 2.4. Comprobar con QuickCheck que las funciones
-- repiteFinitaR, repiteFinitaC y repiteFinita son equivalentes a
-- replicate.
--
-- Nota. Al hacer la comprobación limitar el tamaño de las pruebas como
-- se indica a continuación
-- quickCheckWith (stdArgs {maxSize=7}) prop_repiteFinitaEquiv
-- ---------------------------------------------------------------------
-- La propiedad es
prop_repiteFinitaEquiv :: Int -> Int -> Bool
prop_repiteFinitaEquiv n x =
repiteFinitaR n x == y &&
repiteFinitaC n x == y &&
repiteFinita n x == y
where y = replicate n x
-- La comprobación es
-- ghci> quickCheckWith (stdArgs {maxSize=20}) prop_repiteFinitaEquiv
-- +++ OK, passed 100 tests.
-- ---------------------------------------------------------------------
-- Ejercicio 2.5. Comprobar con QuickCheck que la longitud de
-- (repiteFinita n x) es n, si n es positivo y 0 si no lo es.
--
-- Nota. Al hacer la comprobación limitar el tamaño de las pruebas como
-- se indica a continuación
-- quickCheckWith (stdArgs {maxSize=30}) prop_repiteFinitaLongitud
-- ---------------------------------------------------------------------
-- La propiedad es
prop_repiteFinitaLongitud :: Int -> Int -> Bool
prop_repiteFinitaLongitud n x
| n > 0 = length (repiteFinita n x) == n
| otherwise = null (repiteFinita n x)
-- La comprobación es
-- ghci> quickCheckWith (stdArgs {maxSize=30}) prop_repiteFinitaLongitud
-- +++ OK, passed 100 tests.
-- La expresión de la propiedad se puede simplificar
prop_repiteFinitaLongitud2 :: Int -> Int -> Bool
prop_repiteFinitaLongitud2 n x =
length (repiteFinita n x) == (if n > 0 then n else 0)
-- ---------------------------------------------------------------------
-- Ejercicio 2.6. Comprobar con QuickCheck que todos los elementos de
-- (repiteFinita n x) son iguales a x.
-- ---------------------------------------------------------------------
-- La propiedad es
prop_repiteFinitaIguales :: Int -> Int -> Bool
prop_repiteFinitaIguales n x =
all (==x) (repiteFinita n x)
-- La comprobación es
-- ghci> quickCheckWith (stdArgs {maxSize=30}) prop_repiteFinitaIguales
-- +++ OK, passed 100 tests.
-- ---------------------------------------------------------------------
-- Ejercicio 3.1. Definir, por comprensión, la función
-- ecoC :: String -> String
-- tal que (ecoC xs) es la cadena obtenida a partir de la cadena xs
-- repitiendo cada elemento tantas veces como indica su posición: el
-- primer elemento se repite 1 vez, el segundo 2 veces y así
-- sucesivamente. Por ejemplo,
-- ecoC "abcd" == "abbcccdddd"
-- ---------------------------------------------------------------------
ecoC :: String -> String
ecoC xs = concat [replicate i x | (i,x) <- zip [1..] xs]
-- 2ª definición
ecoC1 :: String -> String
ecoC1 = concat . zipWith replicate [1..]
-- ---------------------------------------------------------------------
-- Ejercicio 3.2. Definir, por recursión, la función
-- ecoR :: String -> String
-- tal que (ecoR xs) es la cadena obtenida a partir de la cadena xs
-- repitiendo cada elemento tantas veces como indica su posición: el
-- primer elemento se repite 1 vez, el segundo 2 veces y así
-- sucesivamente. Por ejemplo,
-- ecoR "abcd" == "abbcccdddd"
-- ---------------------------------------------------------------------
-- 1ª definición
ecoR :: String -> String
ecoR = aux 1
where aux _ [] = []
aux n (x:xs) = replicate n x ++ aux (n+1) xs
-- ---------------------------------------------------------------------
-- Ejercicio 4. Definir, por recursión, la función
-- itera :: (a -> a) -> a -> [a]
-- tal que (itera f x) es la lista cuyo primer elemento es x y los
-- siguientes elementos se calculan aplicando la función f al elemento
-- anterior. Por ejemplo,
-- ghci> itera (+1) 3
-- [3,4,5,6,7,8,9,10,11,12,{Interrupted!}
-- ghci> itera (*2) 1
-- [1,2,4,8,16,32,64,{Interrupted!}
-- ghci> itera (`div` 10) 1972
-- [1972,197,19,1,0,0,0,0,0,0,{Interrupted!}
--
-- Nota: La función itera es equivalente a la función iterate definida
-- en el preludio de Haskell.
-- ---------------------------------------------------------------------
itera :: (a -> a) -> a -> [a]
itera f x = x : itera f (f x)
-- ----------------------------------------------------------------------------
-- Ejercicio 5.1. Definir, por recursión, la función
-- agrupaR :: Int -> [a] -> [[a]]
-- tal que (agrupaR n xs) es la lista formada por listas de n elementos
-- consecutivos de la lista xs (salvo posiblemente la última que puede
-- tener menos de n elementos). Por ejemplo,
-- ghci> agrupaR 2 [3,1,5,8,2,7]
-- [[3,1],[5,8],[2,7]]
-- ghci> agrupaR 2 [3,1,5,8,2,7,9]
-- [[3,1],[5,8],[2,7],[9]]
-- ghci> agrupaR 5 "todo necio confunde valor y precio"
-- ["todo ","necio"," conf","unde ","valor"," y pr","ecio"]
-- ----------------------------------------------------------------------------
agrupaR :: Int -> [a] -> [[a]]
agrupaR _ [] = []
agrupaR n xs = take n xs : agrupaR n (drop n xs)
-- ----------------------------------------------------------------------------
-- Ejercicio 5.2. Definir, de manera no recursiva con iterate, la función
-- agrupa :: Int -> [a] -> [[a]]
-- tal que (agrupa n xs) es la lista formada por listas de n elementos
-- consecutivos de la lista xs (salvo posiblemente la última que puede
-- tener menos de n elementos). Por ejemplo,
-- ghci> agrupa 2 [3,1,5,8,2,7]
-- [[3,1],[5,8],[2,7]]
-- ghci> agrupa 2 [3,1,5,8,2,7,9]
-- [[3,1],[5,8],[2,7],[9]]
-- ghci> agrupa 5 "todo necio confunde valor y precio"
-- ["todo ","necio"," conf","unde ","valor"," y pr","ecio"]
-- ----------------------------------------------------------------------------
agrupa :: Int -> [a] -> [[a]]
agrupa n = takeWhile (not . null)
. map (take n)
. iterate (drop n)
-- Puede verse su funcionamiento en el siguiente ejemplo,
-- iterate (drop 2) [5..10]
-- ==> [[5,6,7,8,9,10],[7,8,9,10],[9,10],[],[],...
-- map (take 2) (iterate (drop 2) [5..10])
-- ==> [[5,6],[7,8],[9,10],[],[],[],[],...
-- takeWhile (not . null) (map (take 2) (iterate (drop 2) [5..10]))
-- ==> [[5,6],[7,8],[9,10]]
-- ----------------------------------------------------------------------------
-- Ejercicio 5.3. Comprobar con QuickCheck que todos los grupos de
-- (agrupa n xs) tienen longitud n (salvo el último que puede tener una
-- longitud menor).
-- ----------------------------------------------------------------------------
-- La propiedad es
prop_AgrupaLongitud :: Int -> [Int] -> Property
prop_AgrupaLongitud n xs =
n > 0 && not (null gs) ==>
and [length g == n | g <- init gs] &&
0 < length (last gs) && length (last gs) <= n
where gs = agrupa n xs
-- La comprobación es
-- ghci> quickCheck prop_AgrupaLongitud
-- OK, passed 100 tests.
-- ----------------------------------------------------------------------------
-- Ejercicio 5.4. Comprobar con QuickCheck que combinando todos los
-- grupos de (agrupa n xs) se obtiene la lista xs.
-- ----------------------------------------------------------------------------
-- La segunda propiedad es
prop_AgrupaCombina :: Int -> [Int] -> Property
prop_AgrupaCombina n xs =
n > 0 ==> concat (agrupa n xs) == xs
-- La comprobación es
-- ghci> quickCheck prop_AgrupaCombina
-- OK, passed 100 tests.
-- ---------------------------------------------------------------------
-- Ejercicio 6.1. Sea la siguiente operación, aplicable a cualquier
-- número entero positivo:
-- * Si el número es par, se divide entre 2.
-- * Si el número es impar, se multiplica por 3 y se suma 1.
-- Dado un número cualquiera, podemos considerar su órbita, es decir,
-- las imágenes sucesivas al iterar la función. Por ejemplo, la órbita
-- de 13 es
-- 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1,...
-- Si observamos este ejemplo, la órbita de 13 es periódica, es decir,
-- se repite indefinidamente a partir de un momento dado). La conjetura
-- de Collatz dice que siempre alcanzaremos el 1 para cualquier número
-- con el que comencemos. Ejemplos:
-- * Empezando en n = 6 se obtiene 6, 3, 10, 5, 16, 8, 4, 2, 1.
-- * Empezando en n = 11 se obtiene: 11, 34, 17, 52, 26, 13, 40, 20,
-- 10, 5, 16, 8, 4, 2, 1.
-- * Empezando en n = 27, la sucesión tiene 112 pasos, llegando hasta
-- 9232 antes de descender a 1: 27, 82, 41, 124, 62, 31, 94, 47,
-- 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274,
-- 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263,
-- 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502,
-- 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958,
-- 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644,
-- 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308,
-- 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122,
-- 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5,
-- 16, 8, 4, 2, 1.
--
-- Definir la función
-- siguiente :: Integer -> Integer
-- tal que (siguiente n) es el siguiente de n en la sucesión de
-- Collatz. Por ejemplo,
-- siguiente 13 == 40
-- siguiente 40 == 20
-- ---------------------------------------------------------------------
siguiente :: Integer -> Integer
siguiente n | even n = n `div` 2
| otherwise = 3*n+1
-- ---------------------------------------------------------------------
-- Ejercicio 6.2. Definir, por recursión, la función
-- collatzR :: Integer -> [Integer]
-- tal que (collatzR n) es la órbita de CollatzR de n hasta alcanzar el
-- 1. Por ejemplo,
-- collatzR 13 == [13,40,20,10,5,16,8,4,2,1]
-- ---------------------------------------------------------------------
collatzR :: Integer -> [Integer]
collatzR 1 = [1]
collatzR n = n : collatzR (siguiente n)
-- ---------------------------------------------------------------------
-- Ejercicio 6.3. Definir, sin recursión y con iterate, la función
-- collatz :: Integer -> [Integer]
-- tal que (collatz n) es la órbita de Collatz d n hasta alcanzar el
-- 1. Por ejemplo,
-- collatz 13 == [13,40,20,10,5,16,8,4,2,1]
-- Indicación: Usar takeWhile e iterate.
-- ---------------------------------------------------------------------
collatz :: Integer -> [Integer]
collatz n = takeWhile (/=1) (iterate siguiente n) ++ [1]
-- ---------------------------------------------------------------------
-- Ejercicio 6.4. Definir la función
-- menorCollatzMayor :: Int -> Integer
-- tal que (menorCollatzMayor x) es el menor número cuya órbita de
-- Collatz tiene más de x elementos. Por ejemplo,
-- menorCollatzMayor 100 == 27
-- ---------------------------------------------------------------------
menorCollatzMayor :: Int -> Integer
menorCollatzMayor x = head [y | y <- [1..], length (collatz y) > x]
-- ---------------------------------------------------------------------
-- Ejercicio 6.5. Definir la función
-- menorCollatzSupera :: Integer -> Integer
-- tal que (menorCollatzSupera x) es el menor número cuya órbita de
-- Collatz tiene algún elemento mayor que x. Por ejemplo,
-- menorCollatzSupera 100 == 15
-- ---------------------------------------------------------------------
-- 1ª definición
menorCollatzSupera :: Integer -> Integer
menorCollatzSupera x =
head [n | n <- [1..], any (> x) (collatzR n)]
-- 2ª definición
menorCollatzSupera2 :: Integer -> Integer
menorCollatzSupera2 x =
head [y | y <- [1..], maximum (collatz y) > x]
-- ---------------------------------------------------------------------
-- Ejercicio 7. Definir, usando takeWhile y map, la función
-- potenciasMenores :: Int -> Int -> [Int]
-- tal que (potenciasMenores x y) es la lista de las potencias de x
-- menores que y. Por ejemplo,
-- potenciasMenores 2 1000 == [2,4,8,16,32,64,128,256,512]
-- ---------------------------------------------------------------------
potenciasMenores :: Int -> Int -> [Int]
potenciasMenores x y = takeWhile (<y) (map (x^) [1..])
-- ---------------------------------------------------------------------
-- Ejercicio 8.1. Definir, usando la criba de Eratóstenes, la constante
-- primos :: Integral a => [a]
-- cuyo valor es la lista de los números primos. Por ejemplo,
-- take 10 primos == [2,3,5,7,11,13,17,19,23,29]
-- ---------------------------------------------------------------------
primos :: Integral a => [a]
primos = criba [2..]
where criba [] = []
criba (n:ns) = n : criba (elimina n ns)
elimina n xs = [x | x <- xs, x `mod` n /= 0]
-- ---------------------------------------------------------------------
-- Ejercicio 8.2. Definir la función
-- primo :: Integral a => a -> Bool
-- tal que (primo n) se verifica si n es primo. Por ejemplo,
-- primo 7 == True
-- primo 9 == False
-- ---------------------------------------------------------------------
primo :: Int -> Bool
primo n = head (dropWhile (<n) primos) == n
-- ---------------------------------------------------------------------
-- Ejercicio 8.3. Definir la función
-- sumaDeDosPrimos :: Int -> [(Int,Int)]
-- tal que (sumaDeDosPrimos n) es la lista de las distintas
-- descomposiciones de n como suma de dos números primos. Por ejemplo,
-- sumaDeDosPrimos 30 == [(7,23),(11,19),(13,17)]
-- sumaDeDosPrimos 10 == [(3,7),(5,5)]
-- Calcular, usando la función sumaDeDosPrimos, el menor número que
-- puede escribirse de 10 formas distintas como suma de dos primos.
-- ---------------------------------------------------------------------
sumaDeDosPrimos :: Int -> [(Int,Int)]
sumaDeDosPrimos n =
[(x,n-x) | x <- primosN, primo (n-x)]
where primosN = takeWhile (<= (n `div` 2)) primos
-- El cálculo es
-- ghci> head [x | x <- [1..], length (sumaDeDosPrimos x) == 10]
-- 114
-- ---------------------------------------------------------------------
-- § La lista infinita de factoriales, --
-- ---------------------------------------------------------------------
-- ---------------------------------------------------------------------
-- Ejercicio 9.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 9.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
-- El cálculo es
-- take 4 factoriales2
-- = take 4 (1 : zipWith (*) [1..] factoriales2)
-- = 1 : take 3 (zipWith (*) [1..] factoriales2)
-- = 1 : take 3 (zipWith (*) [1..] [1|R1]) {R1 es tail factoriales2}
-- = 1 : take 3 (1 : zipWith (*) [2..] [R1])
-- = 1 : 1 : take 2 (zipWith (*) [2..] [1|R2]) {R2 es drop 2 factoriales2}
-- = 1 : 1 : take 2 (2 : zipWith (*) [3..] [R2])
-- = 1 : 1 : 2 : take 1 (zipWith (*) [3..] [2|R3]) {R3 es drop 3 factoriales2}
-- = 1 : 1 : 2 : take 1 (6 : zipWith (*) [4..] [R3])
-- = 1 : 1 : 2 : 6 : take 0 (zipWith (*) [4..] [R3])
-- = 1 : 1 : 2 : 6 : []
-- = [1, 1, 2, 6]
-- ---------------------------------------------------------------------
-- Ejercicio 9.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 9.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
-- El cálculo es
-- take 4 factoriales3
-- = take 4 (1 : aux 1 [1..])
-- = 1 : take 3 (aux 1 [1..])
-- = 1 : take 3 (1 : aux 1 [2..])
-- = 1 : 1 : take 2 (aux 1 [2..])
-- = 1 : 1 : take 2 (2 : aux 2 [3..])
-- = 1 : 1 : 2 : take 1 (aux 2 [3..])
-- = 1 : 1 : 2 : take 1 (6 : aux 6 [4..])
-- = 1 : 1 : 2 : 6 : take 0 (aux 6 [4..])
-- = 1 : 1 : 2 : 6 : []
-- = [1,1,2,6]
-- ---------------------------------------------------------------------
-- Ejercicio 9.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 9.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 9.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 9.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 (iterate f (1,1))
where f (x,y) = (x+1,x*y)
-- El cálculo es
-- take 4 factoriales5
-- = take 4 (map snd aux)
-- = take 4 (map snd (iterate f (1,1)))
-- = take 4 (map snd [(1,1),(2,1),(3,2),(4,6),...])
-- = take 4 [1,1,2,6,...]
-- = [1,1,2,6]
-- ---------------------------------------------------------------------
-- Ejercicio 9.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 10.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 10.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 10.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 10.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 10.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 10.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 10.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)
fibs4' :: [Integer]
fibs4' = fs
where fs = 0:ys
ys = 1:xs
xs = zipWith (+) ys fs
-- El cálculo de fibs4 es
-- +------------------------+-----------------+-------------------+
-- | xs = zipWith (+) ys fs | ys = 1:xs | fs = 0:ys |
-- +------------------------+-----------------+-------------------+
-- | | 1:... | 0:... |
-- | | ^ | ^ |
-- | 1:... | 1:1:... | 0:1:1:... |
-- | | ^ | ^ |
-- | 1:2:... | 1:1:2:... | 0:1:1:2:... |
-- | | ^ | ^ |
-- | 1:2:3:... | 1:1:2:3:... | 0:1:1:2:3:... |
-- | | ^ | ^ |
-- | 1:2:3:5:... | 1:1:2:3:5:... | 0:1:1:2:3:5:... |
-- | | ^ | ^ |
-- | 1:2:3:5:8:... | 1:1:2:3:5:8:... | 0:1:1:2:3:5:8:... |
-- +------------------------+-----------------+-------------------+
-- En la tercera columna se va construyendo la sucesión.
-- ---------------------------------------------------------------------
-- Ejercicio 10.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)
-- ---------------------------------------------------------------------
-- § El triángulo de Pascal --
-- ---------------------------------------------------------------------
-- ---------------------------------------------------------------------
-- Ejercicio 11.1. El triángulo de Pascal es un triángulo de números
-- 1
-- 1 1
-- 1 2 1
-- 1 3 3 1
-- 1 4 6 4 1
-- 1 5 10 10 5 1
-- ...............
-- construido de la siguiente forma
-- + la primera fila está formada por el número 1;
-- + las filas siguientes se construyen sumando los números adyacentes
-- de la fila superior y añadiendo un 1 al principio y al final de la
-- fila.
--
-- Definir, con iterate y zipWith, la función
-- pascal1 :: [[Integer]]
-- tal que pascal es la lista de las líneas del triángulo de Pascal. Por
-- ejemplo,
-- ghci> take 6 pascal1
-- [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1],[1,5,10,10,5,1]]
-- ---------------------------------------------------------------------
pascal1 :: [[Integer]]
pascal1 = iterate f [1]
where f xs = zipWith (+) (0:xs) (xs++[0])
-- Por ejemplo,
-- xs = [1,2,1]
-- 0:xs = [0,1,2,1]
-- xs++[0] = [1,2,1,0]
-- + = [1,3,3,1]
-- ---------------------------------------------------------------------
-- Ejercicio 11.2. Definir la función, con map y zipWith,
-- pascal2 :: [[Integer]]
-- tal que pascal es la lista de las líneas del triángulo de Pascal. Por
-- ejemplo,
-- ghci> take 6 pascal2
-- [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1],[1,5,10,10,5,1]]
-- ---------------------------------------------------------------------
pascal2 :: [[Integer]]
pascal2 = [1] : map f pascal2
where f xs = zipWith (+) (0:xs) (xs++[0])
-- ---------------------------------------------------------------------
-- Ejercicio 11.3. Escribir la traza del cálculo de la expresión
-- take 4 pascal
-- ---------------------------------------------------------------------
-- Nota: El cálculo es
-- take 4 pascal
-- = take 4 ([1] : map f pascal)
-- = [1] : (take 3 (map f pascal))
-- = [1] : (take 3 (map f ([1]:R1pascal)))
-- = [1] : (take 3 ((f [1]) : map R1pascal)))
-- = [1] : (take 3 ((zipWith (+) (0:[1]) ([1]++[0]) : map R1pascal)))
-- = [1] : (take 3 ((zipWith (+) [0,1] [1,0]) : map R1pascal)))
-- = [1] : (take 3 ([1,1] : map R1pascal)))
-- = [1] : [1,1] : (take 2 (map R1pascal)))
-- = [1] : [1,1] : (take 2 (map ([1,1]:R2pascal)))
-- = [1] : [1,1] : (take 2 ((f [1,1]) : map R2pascal)))
-- = [1] : [1,1] : (take 2 ((zipWith (+) (0:[1,1]) ([1,1]++[0]) : map R2pascal)))
-- = [1] : [1,1] : (take 2 ((zipWith (+) [0,1,1] [1,1,0]) : map R2pascal)))
-- = [1] : [1,1] : (take 2 ([1,2,1] : map R2pascal)))
-- = [1] : [1,1] : [1,2,1] : (take 1 (map R2pascal)))
-- = [1] : [1,1] : [1,2,1] : (take 1 (map ([1,2,1]:R3pascal)))
-- = [1] : [1,1] : [1,2,1] : (take 1 ((f [1,2,1]) : map R3pascal)))
-- = [1] : [1,1] : [1,2,1] : (take 1 ((zipWith (+) (0:[1,2,1]) ([1,2,1]++[0]) : map R3pascal)))
-- = [1] : [1,1] : [1,2,1] : (take 1 ((zipWith (+) [0,1,2,1] [1,2,1,0]) : map R3pascal)))
-- = [1] : [1,1] : [1,2,1] : (take 1 ([1,3,3,1] : map R3pascal)))
-- = [1] : [1,1] : [1,2,1] : [1,3,3,1] : (take 0 (map R3pascal)))
-- = [1] : [1,1] : [1,2,1] : [1,3,3,1] : []
-- = [[1],[1,1],[1,2,1],[1,3,3,1]]
-- en el cálculo con R1pascal, R2pascal y R3pascal es el triángulo de
-- Pascal sin el primero, los dos primeros o los tres primeros elementos,
-- respectivamente.
![Informática de 1º de Matemáticas [Curso 2021-22, Grupo 2]](/WIKIS/I1M2021G2/resources/assets/logoUS.png)