I1M2013: El triángulo de Floyd en Haskell

En la segunda parte de la clase de hoy de Informática de 1º del Grado en Matemáticas se han explicado las soluciones del ejercicio 6 de la relación 17 sobre el triángulo de Floyd.

Los ejercicios, y sus soluciones, se muestran a continuación.

-- ---------------------------------------------------------------------
-- § El triángulo de Floyd                                            --
-- ---------------------------------------------------------------------

-- El triángulo de Floyd, llamado así en honor a Robert Floyd, es un
-- triángulo rectángulo formado con números naturales. Para crear un
-- triángulo de Floyd, se comienza con un 1 en la esquina superior
-- izquierda, y se continúa escribiendo la secuencia de los números
-- naturales de manera que cada línea contenga un número más que la
-- anterior. Las 5 primeras líneas del triángulo de Floyd son
--     1
--     2   3
--     4   5   6
--     7   8   9  10
--    11  12  13  14  15
-- 
-- El triángulo de Floyd tiene varias propiedades matemáticas
-- interesantes. Los números del cateto de la parte izquierda forman la
-- secuencia de los números poligonales centrales, mientras que los de
-- la hipotenusa nos dan el conjunto de los números triangulares.

-- ---------------------------------------------------------------------
-- § Librerías auxiliares                                             --
-- ---------------------------------------------------------------------

import Data.Char 
import Data.List 
import Test.QuickCheck

-- ---------------------------------------------------------------------
-- Ejercicio 6.1. Definir la función
--    siguienteF :: [Integer] -> [Integer]
-- tal que (siguienteF xs) es la lista de los elementos de la línea xs en
-- el triángulo de Lloyd. Por ejemplo,
--    siguienteF [2,3]    ==  [4,5,6]
--    siguienteF [4,5,6]  ==  [7,8,9,10]
-- ---------------------------------------------------------------------

siguienteF :: [Integer] -> [Integer]
siguienteF xs = [a..a+n]
    where a = 1+last xs
          n = genericLength xs

-- ---------------------------------------------------------------------
-- Ejercicio 6.2. Definir la función        
--    trianguloFloyd :: [[Integer]]
-- tal que trianguloFloyd es el triángulo de Floyd. Por ejemplo,
--    ghci> take 4 trianguloFloyd
--    [[1],
--     [2,3],
--     [4,5,6],
--     [7,8,9,10]]
-- ---------------------------------------------------------------------

trianguloFloyd :: [[Integer]]
trianguloFloyd = iterate siguienteF [1]

-- Filas del triángulo de Floyd
-- ============================

-- ---------------------------------------------------------------------
-- Ejercicio 6.3. Definir la función
--    filaTrianguloFloyd :: Integer -> [Integer]
-- tal que (filaTrianguloFloyd n) es la fila n-ésima del triángulo de
-- Floyd. Por ejemplo,  
--    filaTrianguloFloyd 3  ==  [4,5,6]
--    filaTrianguloFloyd 4  ==  [7,8,9,10]
-- ---------------------------------------------------------------------

filaTrianguloFloyd :: Integer -> [Integer]
filaTrianguloFloyd n = trianguloFloyd `genericIndex` (n-1)

-- ---------------------------------------------------------------------
-- Ejercicio 6.4. Definir la función
--    sumaFilaTrianguloFloyd :: Integer -> Integer
-- tal que (sumaFilaTrianguloFloyd n) es la suma de los fila n-ésima del
-- triángulo de Floyd. Por ejemplo,
--    sumaFilaTrianguloFloyd 1  ==  1
--    sumaFilaTrianguloFloyd 2  ==  5
--    sumaFilaTrianguloFloyd 3  ==  15
--    sumaFilaTrianguloFloyd 4  ==  34
--    sumaFilaTrianguloFloyd 5  ==  65
-- ---------------------------------------------------------------------

sumaFilaTrianguloFloyd :: Integer -> Integer
sumaFilaTrianguloFloyd = sum . filaTrianguloFloyd

-- ---------------------------------------------------------------------
-- Ejercicio 6.5. A partir de los valores de (sumaFilaTrianguloFloyd n)
-- para n entre 1 y 5, conjeturar una fórmula para calcular
-- (sumaFilaTrianguloFloyd n). 
-- ---------------------------------------------------------------------

-- Usando Wolfram Alpha (como se indica en http://wolfr.am/19XAl2X )
-- a partir de 1, 5, 15, 34, 65, ... se obtiene la fórmula
--    (n^3+n)/2

-- ---------------------------------------------------------------------
-- Ejecicio 6. Comprobar con QuickCheck la conjetura obtenida en el
-- ejercicio anterior.
-- ---------------------------------------------------------------------

-- La conjetura es
prop_sumaFilaTrianguloFloyd :: Integer -> Property
prop_sumaFilaTrianguloFloyd n =        
    n > 0 ==> sum (filaTrianguloFloyd n) == (n^3+n) `div` 2
  
-- La comprobación es
--    ghci> quickCheck prop_sumaFilaTrianguloFloyd
--    +++ OK, passed 100 tests.

-- Hipotenusa del triángulo de Floyd y números triangulares
-- ========================================================

-- ---------------------------------------------------------------------
-- Ejercicio 6.7. Definir la función
--    hipotenusaFloyd :: [Integer]
-- tal que hipotenusaFloyd es la lista de los elementos de la hipotenusa
-- del triángulo de Floyd. Por ejemplo, 
--    take 5 hipotenusaFloyd  ==  [1,3,6,10,15]
-- ---------------------------------------------------------------------

hipotenusaFloyd :: [Integer]
hipotenusaFloyd = map last trianguloFloyd

-- ---------------------------------------------------------------------
-- Ejercicio 6.8. Lo números triangulares se forman como sigue
--    *     *      * 
--         * *    * *
--               * * *
--    1     3      6
-- 
-- La sucesión de los números triangulares se obtiene sumando los
-- números naturales. Así, los 5 primeros números triangulares son
--     1 = 1
--     3 = 1+2
--     6 = 1+2+3
--    10 = 1+2+3+4
--    15 = 1+2+3+4+5
-- 
-- Definir la función
--    triangulares :: [Integer]
-- tal que triangulares es la lista de los números triangulares. Por
-- ejemplo, 
--    take 10 triangulares  ==  [1,3,6,10,15,21,28,36,45,55]
-- ---------------------------------------------------------------------

triangulares :: [Integer]
triangulares = 1 : [x+y | (x,y) <- zip [2..] triangulares]

-- 2ª definición (usando scanl):
triangulares2 :: [Integer]
triangulares2 = scanl (+) 1 [2..]

-- 3ª definición (usando la fórmula de la suma de la progresión):
triangulares3 :: [Integer]
triangulares3 = [(n*(n+1)) `div` 2 | n <- [1..]]

-- ---------------------------------------------------------------------
-- Ejercicio 6.9. Definir la función 
--    prop_hipotenusaFloyd :: Int -> Bool
-- tal que (prop_hipotenusaFloyd n) se verifica si los n primeros
-- elementos de la hipotenusa del triángulo de Floy son los primeros n
-- números triangulares. 
-- 
-- Comprobar la propiedad para los 1000 primeros elementos.
-- ---------------------------------------------------------------------

-- La propiedad es
prop_hipotenusaFloyd :: Int -> Bool
prop_hipotenusaFloyd n = 
    take n hipotenusaFloyd == take n triangulares

-- La comprobación es
--    ghci> prop_hipotenusaFloyd 1000
--    True

-- Cateto del triángulo de Floyd y números poligonales centrales
-- =============================================================

-- ---------------------------------------------------------------------
-- Ejercicio 6.10. Definir la función
--    catetoFloyd :: [Integer]
-- tal que catetoFloyd es la lista de los elementos del cateto izquierdo
-- del triángulo de Floyd. Por ejemplo, 
--    take 5 catetoFloyd  ==  [1,2,4,7,11]
-- ---------------------------------------------------------------------

catetoFloyd :: [Integer]
catetoFloyd = map head trianguloFloyd

-- ---------------------------------------------------------------------
-- Ejercicio 6.11. El n-ésimo número poligonal centrado es el máximo
-- número de piezas que se pueden obtener a partir de un círculo con n
-- líneas rectas. Por ejemplo,
--    poligonales_centrados.jpg
--
-- Definir la función
--    poligonalCentrado :: Integer -> Integer
-- tal que (poligonalCentrado n) es el n-ésimo número poligonal
-- centrado. Por ejemplo, 
--    [poligonalCentrado n | n <- [0..5]]  ==  [1,2,4,7,11,16]
-- ---------------------------------------------------------------------

poligonalCentrado :: Integer -> Integer
poligonalCentrado 0 = 1
poligonalCentrado n = n + poligonalCentrado (n-1)

-- ---------------------------------------------------------------------
-- Ejercicio 6.12. Definir la función
--    poligonalesCentrados :: [Integer]
-- tal que poligonalesCentrados es la lista de los números poligonales
-- centrados. Por ejemplo, 
--    take 10 poligonalesCentrados  ==  [1,3,6,10,15,21,28,36,45,55]
-- ---------------------------------------------------------------------

-- 1ª definición:
poligonalesCentrados1 :: [Integer]
poligonalesCentrados1 = [poligonalCentrado n | n <- [0..]]

-- 2ª definición (usando scanl):
poligonalesCentrados :: [Integer]
poligonalesCentrados = scanl (+) 1 [1..]

-- ---------------------------------------------------------------------
-- Ejercicio 6.13. Definir la función 
--    prop_catetoFloyd :: Int -> Bool
-- tal que (prop_catetoFloyd n) se verifica si los n primeros
-- elementos del cateto izquierdo del triángulo de Floy son los primeros
-- n números poligonales centrados.
-- 
-- Comprobar la propiedad para los 1000 primeros elementos.
-- ---------------------------------------------------------------------

-- La propiedad es
prop_catetoFloyd :: Int -> Bool
prop_catetoFloyd n = 
    take n catetoFloyd == take n poligonalesCentrados

-- La comprobación es
--    ghci> prop_catetoFloyd 1000
--    True

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

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

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

-- § El triángulo de Floyd --

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

-- El triángulo de Floyd, llamado así en honor a Robert Floyd, es un

-- triángulo rectángulo formado con números naturales. Para crear un

-- triángulo de Floyd, se comienza con un 1 en la esquina superior

-- izquierda, y se continúa escribiendo la secuencia de los números

-- naturales de manera que cada línea contenga un número más que la

-- anterior. Las 5 primeras líneas del triángulo de Floyd son

-- 1

-- 2 3

-- 4 5 6

-- 7 8 9 10

-- 11 12 13 14 15

-- El triángulo de Floyd tiene varias propiedades matemáticas

-- interesantes. Los números del cateto de la parte izquierda forman la

-- secuencia de los números poligonales centrales, mientras que los de

-- la hipotenusa nos dan el conjunto de los números triangulares.

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

-- § Librerías auxiliares --

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

import Data.Char

import Data.List

import Test.QuickCheck

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

-- Ejercicio 6.1. Definir la función

-- siguienteF :: [Integer] -> [Integer]

-- tal que (siguienteF xs) es la lista de los elementos de la línea xs en

-- el triángulo de Lloyd. Por ejemplo,

-- siguienteF [2,3] == [4,5,6]

-- siguienteF [4,5,6] == [7,8,9,10]

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

siguienteF :: [Integer] -> [Integer]

siguienteF xs = [a..a+n]

where a = 1+last xs

n = genericLength xs

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

-- Ejercicio 6.2. Definir la función

-- trianguloFloyd :: [[Integer]]

-- tal que trianguloFloyd es el triángulo de Floyd. Por ejemplo,

-- ghci> take 4 trianguloFloyd

-- [[1],

-- [2,3],

-- [4,5,6],

-- [7,8,9,10]]

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

trianguloFloyd :: [[Integer]]

trianguloFloyd = iterate siguienteF [1]

-- Filas del triángulo de Floyd

-- ============================

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

-- Ejercicio 6.3. Definir la función

-- filaTrianguloFloyd :: Integer -> [Integer]

-- tal que (filaTrianguloFloyd n) es la fila n-ésima del triángulo de

-- Floyd. Por ejemplo,

-- filaTrianguloFloyd 3 == [4,5,6]

-- filaTrianguloFloyd 4 == [7,8,9,10]

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

filaTrianguloFloyd :: Integer -> [Integer]

filaTrianguloFloyd n = trianguloFloyd `genericIndex` (n-1)

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

-- Ejercicio 6.4. Definir la función

-- sumaFilaTrianguloFloyd :: Integer -> Integer

-- tal que (sumaFilaTrianguloFloyd n) es la suma de los fila n-ésima del

-- triángulo de Floyd. Por ejemplo,

-- sumaFilaTrianguloFloyd 1 == 1

-- sumaFilaTrianguloFloyd 2 == 5

-- sumaFilaTrianguloFloyd 3 == 15

-- sumaFilaTrianguloFloyd 4 == 34

-- sumaFilaTrianguloFloyd 5 == 65

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

sumaFilaTrianguloFloyd :: Integer -> Integer

sumaFilaTrianguloFloyd = sum . filaTrianguloFloyd

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

-- Ejercicio 6.5. A partir de los valores de (sumaFilaTrianguloFloyd n)

-- para n entre 1 y 5, conjeturar una fórmula para calcular

-- (sumaFilaTrianguloFloyd n).

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

-- Usando Wolfram Alpha (como se indica en http://wolfr.am/19XAl2X )

-- a partir de 1, 5, 15, 34, 65, ... se obtiene la fórmula

-- (n^3+n)/2

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

-- Ejecicio 6. Comprobar con QuickCheck la conjetura obtenida en el

-- ejercicio anterior.

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

-- La conjetura es

prop_sumaFilaTrianguloFloyd :: Integer -> Property

prop_sumaFilaTrianguloFloyd n =

n > 0 ==> sum (filaTrianguloFloyd n) == (n^3+n) `div` 2

-- La comprobación es

-- ghci> quickCheck prop_sumaFilaTrianguloFloyd

-- +++ OK, passed 100 tests.

-- Hipotenusa del triángulo de Floyd y números triangulares

-- ========================================================

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

-- Ejercicio 6.7. Definir la función

-- hipotenusaFloyd :: [Integer]

-- tal que hipotenusaFloyd es la lista de los elementos de la hipotenusa

-- del triángulo de Floyd. Por ejemplo,

-- take 5 hipotenusaFloyd == [1,3,6,10,15]

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

hipotenusaFloyd :: [Integer]

hipotenusaFloyd = map last trianguloFloyd

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

-- Ejercicio 6.8. Lo números triangulares se forman como sigue

-- * * *

-- * * * *

-- * * *

-- 1 3 6

-- La sucesión de los números triangulares se obtiene sumando los

-- números naturales. Así, los 5 primeros números triangulares son

-- 1 = 1

-- 3 = 1+2

-- 6 = 1+2+3

-- 10 = 1+2+3+4

-- 15 = 1+2+3+4+5

-- Definir la función

-- triangulares :: [Integer]

-- tal que triangulares es la lista de los números triangulares. Por

-- ejemplo,

-- take 10 triangulares == [1,3,6,10,15,21,28,36,45,55]

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

triangulares :: [Integer]

triangulares = 1 : [x+y | (x,y) <- zip [2..] triangulares]

-- 2ª definición (usando scanl):

triangulares2 :: [Integer]

triangulares2 = scanl (+) 1 [2..]

-- 3ª definición (usando la fórmula de la suma de la progresión):

triangulares3 :: [Integer]

triangulares3 = [(n*(n+1)) `div` 2 | n <- [1..]]

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

-- Ejercicio 6.9. Definir la función

-- prop_hipotenusaFloyd :: Int -> Bool

-- tal que (prop_hipotenusaFloyd n) se verifica si los n primeros

-- elementos de la hipotenusa del triángulo de Floy son los primeros n

-- números triangulares.

-- Comprobar la propiedad para los 1000 primeros elementos.

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

-- La propiedad es

prop_hipotenusaFloyd :: Int -> Bool

prop_hipotenusaFloyd n =

take n hipotenusaFloyd == take n triangulares

-- La comprobación es

-- ghci> prop_hipotenusaFloyd 1000

-- True

-- Cateto del triángulo de Floyd y números poligonales centrales

-- =============================================================

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

-- Ejercicio 6.10. Definir la función

-- catetoFloyd :: [Integer]

-- tal que catetoFloyd es la lista de los elementos del cateto izquierdo

-- del triángulo de Floyd. Por ejemplo,

-- take 5 catetoFloyd == [1,2,4,7,11]

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

catetoFloyd :: [Integer]

catetoFloyd = map head trianguloFloyd

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

-- Ejercicio 6.11. El n-ésimo número poligonal centrado es el máximo

-- número de piezas que se pueden obtener a partir de un círculo con n

-- líneas rectas. Por ejemplo,

-- poligonales_centrados.jpg

-- Definir la función

-- poligonalCentrado :: Integer -> Integer

-- tal que (poligonalCentrado n) es el n-ésimo número poligonal

-- centrado. Por ejemplo,

-- [poligonalCentrado n | n <- [0..5]] == [1,2,4,7,11,16]

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

poligonalCentrado :: Integer -> Integer

poligonalCentrado 0 = 1

poligonalCentrado n = n + poligonalCentrado (n-1)

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

-- Ejercicio 6.12. Definir la función

-- poligonalesCentrados :: [Integer]

-- tal que poligonalesCentrados es la lista de los números poligonales

-- centrados. Por ejemplo,

-- take 10 poligonalesCentrados == [1,3,6,10,15,21,28,36,45,55]

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

-- 1ª definición:

poligonalesCentrados1 :: [Integer]

poligonalesCentrados1 = [poligonalCentrado n | n <- [0..]]

-- 2ª definición (usando scanl):

poligonalesCentrados :: [Integer]

poligonalesCentrados = scanl (+) 1 [1..]

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

-- Ejercicio 6.13. Definir la función

-- prop_catetoFloyd :: Int -> Bool

-- tal que (prop_catetoFloyd n) se verifica si los n primeros

-- elementos del cateto izquierdo del triángulo de Floy son los primeros

-- n números poligonales centrados.

-- Comprobar la propiedad para los 1000 primeros elementos.

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

-- La propiedad es

prop_catetoFloyd :: Int -> Bool

prop_catetoFloyd n =

take n catetoFloyd == take n poligonalesCentrados

-- La comprobación es

-- ghci> prop_catetoFloyd 1000

-- True

Se puede imprimir o compartir con