I1M2017: Definiciones de la lista infinita de factoriales en Haskell

En clase de hoy de Informática de 1º del Grado en Matemáticas hemos comentando el ejercicio 9 de la 10ª relación en el se compara 5 definiciones de la lista infinita de los factoriales desde el punto de vista de su simplicidad y eficiencia.

Las definiciones y comparaciones estudiadas son las que se muestran a continuación

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

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

-- ---------------------------------------------------------------------

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

Se puede imprimir o compartir con