I1M2012: Ejercicios de evaluación perezosa y listas infinitas (2)

En la clase de hoy de Informática de 1º del Grado en Matemáticas hemos comentando soluciones de ejercicios sobre evaluación perezosa y listas infinitas de las relación 17.

En los comentarios se ha resaltado

en los ejercicios 2 y 3:
- la importancia del orden de las condiciones en las definiciones de listas por comprensión,
- la eficiencia del cálculo sobre la búsqueda.
en el ejecicio 6.2 el uso de iterate y
en la definición de los números triangulares el uso de scanl.

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

-- ---------------------------------------------------------------------
-- Ejercicio 1.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 1.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 2. 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, x <= n-x, elem (n-x) primosN]
    where primosN = takeWhile (<=n) primos


-- El cálculo es
--    ghci> head [x | x <- [1..], length (sumaDeDosPrimos x) == 10]
--    114

-- ---------------------------------------------------------------------
-- Ejercicio 3. Definir la función
--    esProductoDeDosPrimos :: Int -> Bool
-- tal que (esProductoDeDosPrimos n) se verifica si n es el producto de
-- dos primos distintos. Por ejemplo,
--    esProductoDeDosPrimos 6  ==  True
--    esProductoDeDosPrimos 9  ==  False
-- ---------------------------------------------------------------------

esProductoDeDosPrimos :: Int -> Bool
esProductoDeDosPrimos n =
    [x | x <- primosN, 
         mod n x == 0, 
         div n x /= x, 
         elem (div n x) primosN] /= []
    where primosN = takeWhile (<=n) primos

-- ---------------------------------------------------------------------
-- Ejercicio 4.1. [Problema 37 del proyecto Euler] Un número primo es
-- truncable si los números que se obtienen eliminado cifras, de derecha
-- a izquierda, son primos. Por ejemplo, 599 es un primo truncable
-- porque 599, 59 y 5 son primos; en cambio, 577 es un primo no
-- truncable porque 57 no es primo.   
-- 
-- Definir la función 
--    primoTruncable :: Int -> Bool
-- tal que (primoTruncable x) se verifica si x es un primo
-- truncable. Por ejemplo,
--    primoTruncable 599  ==  True
--    primoTruncable 577  ==  False
-- ---------------------------------------------------------------------

primoTruncable :: Int -> Bool
primoTruncable x 
    | x < 10    = primo x
    | otherwise = primo x && primoTruncable (x `div` 10)

-- ---------------------------------------------------------------------
-- Ejercicio 4.2. Definir la función
--    sumaPrimosTruncables :: Int -> Int
-- tal que (sumaPrimosTruncables n) es la suma de los n primeros primos
-- truncables. Por ejemplo,
--    sumaPrimosTruncables 10  ==  249
-- Calcular la suma de los 20 primos truncables.
-- ---------------------------------------------------------------------

sumaPrimosTruncables :: Int -> Int
sumaPrimosTruncables n = 
    sum (take n [x | x <- primos, primoTruncable x])

-- El cálculo es
--    ghci> sumaPrimosTruncables 20
--    2551

-- ---------------------------------------------------------------------
-- Ejercicio 5.1. Definir la función
--    intercala :: a -> [a] -> [[a]]
-- tal que (intercala x ys) es la lista de las listas obtenidas
-- intercalando x entre los elementos de ys. Por ejemplo, 
--    intercala 1 [2,3]  ==  [[1,2,3],[2,1,3],[2,3,1]]
-- ---------------------------------------------------------------------

-- Una definición recursiva es
intercala1 :: a -> [a] -> [[a]]
intercala1 x [] = [[x]]
intercala1 x (y:ys) = (x:y:ys) : [y:zs | zs <- intercala1 x ys]

-- Otra definición, más eficiente, es
intercala :: a -> [a] -> [[a]]
intercala y xs = 
    [take n xs ++ (y : drop n xs) | n <- [0..length xs]]

-- Por ejemplo,
--    ghci> length (intercala1 1 [2..10^4])
--    10000
--    (11.63 secs, 3016915472 bytes)
--    ghci> length (intercala 1 [2..10^4])
--    10000
--    (0.02 secs, 2631448 bytes)

-- ---------------------------------------------------------------------
-- Ejercicio 5.2. Definir la función 
--    permutaciones :: [a] -> [[a]]
-- tal que (permutaciones xs) es la lista de las permutaciones de la
-- lista xs. Por ejemplo, 
--    permutaciones "bc"   ==  ["bc","cb"]
--    permutaciones "abc"  ==  ["abc","bac","bca","acb","cab","cba"]
-- ---------------------------------------------------------------------

permutaciones :: [a] -> [[a]]
permutaciones []     = [[]]
permutaciones (x:xs) = 
    concat [intercala x ys | ys <- permutaciones xs]

-- ---------------------------------------------------------------------
-- Ejercicio 5.3. Definir la función
--    permutacionesN :: Integer -> [Integer]
-- tal que (permutacionesN x) es la lista de los números obtenidos
-- permutando las cifras de x. Por ejemplo,
--    permutacionesN 352  ==  [352,532,523,325,235,253]
-- ---------------------------------------------------------------------

permutacionesN :: Int -> [Int]
permutacionesN x = [read ys | ys <- permutaciones (show x)]

-- ---------------------------------------------------------------------
-- Ejercicio 5.4. Un primo permutable es un número primo tal que todos
-- los números obtenidos permutando sus cifras son primos. Por ejemplo,
-- 337 es un primo permutable ya que 337, 373 y 733 son primos. 
-- 
-- Definir la función  
--    primoPermutable :: Integer -> Bool
-- tal que (primoPermutable x) se verifica si x es un primo
-- permutable. Por ejemplo, 
--    primoPermutable 17  ==  True
--    primoPermutable 19  ==  False
-- ---------------------------------------------------------------------

primoPermutable :: Int -> Bool
primoPermutable x = and [primo y | y <- permutacionesN x]

-- ---------------------------------------------------------------------
-- Ejercicio 6.1. Los números enteros se pueden ordenar como sigue 
--    0, -1, 1, -2, 2, -3, 3, -4, 4, -5, 5, -6, 6, -7, 7, ...
-- Definir, por comprensión, la constante
--    enteros :: [Int]
-- tal que enteros es la lista de los enteros con la ordenación
-- anterior. Por ejemplo,
--    take 10 enteros  ==  [0,-1,1,-2,2,-3,3,-4,4,-5]
-- ---------------------------------------------------------------------

enteros :: [Int]
enteros = 0 : concat [[-x,x] | x <- [1..]]

-- ---------------------------------------------------------------------
-- Ejercicio 6.2. Definir, por iteración, la constante
--    enteros' :: [Int]
-- tal que enteros' es la lista de los enteros con la ordenación
-- anterior. Por ejemplo,
--    take 10 enteros  ==  [0,-1,1,-2,2,-3,3,-4,4,-5]
-- ---------------------------------------------------------------------

enteros' :: [Int]
enteros' = iterate siguiente 0
    where siguiente x | x >= 0    = -x-1
                      | otherwise = -x

-- ---------------------------------------------------------------------
-- Ejercicio 6.3. Definir, por selección con takeWhile, la función
--    posicion :: Int -> Int
-- tal que (posicion x) es la posición del entero x en la ordenación
-- anterior. Por ejemplo,
--    posicion 2  ==  4
-- ---------------------------------------------------------------------

posicion :: Int -> Int
posicion x = length (takeWhile (/=x) enteros)

-- ---------------------------------------------------------------------
-- Ejercicio 6.4. Definir, por recursión, la función
--    posicionR :: Int -> Int
-- tal que (posicionR x) es la posición del entero x en la ordenación
-- anterior. Por ejemplo,
--    posicionR 2  ==  4
-- ---------------------------------------------------------------------

posicionR :: Int -> Int
posicionR x = aux enteros 0
    where aux (y:ys) n | x == y    = n
                       | otherwise = aux ys (n+1)

-- ---------------------------------------------------------------------
-- Ejercicio 6.5. Definir, por comprensión, la función
--    posicionC :: Int -> Int
-- tal que (posicionC x) es la posición del entero x en la ordenación
-- anterior. Por ejemplo,
--    posicionC 2  ==  4
-- ---------------------------------------------------------------------

posicionC :: Int -> Int
posicionC x = head [n | (n,y) <- zip [0..] enteros, y == x]

-- ---------------------------------------------------------------------
-- Ejercicio 6.6. Definir, sin búsqueda, la función
--    posicion2 :: Int -> Int
-- tal que (posicion2 x) es la posición del entero x en la ordenación
-- anterior. Por ejemplo,
--    posicion2 2  ==  4
-- ---------------------------------------------------------------------

-- Definición directa
posicion2 :: Int -> Int
posicion2 x | x >= 0    = 2*x
            | otherwise = 2*(-x)-1

-- ---------------------------------------------------------------------
-- Ejercicio 7. (Problema 10 del Proyecto Euler) Definir la función 
--    sumaPrimoMenores :: Integer -> Integer
-- tal que (sumaPrimoMenores n) es la suma de los primos menores que
-- n. Por ejemplo,
--    sumaPrimoMenores 10  ==  17
-- ---------------------------------------------------------------------

-- Por recursión
sumaPrimoMenores :: Integer -> Integer
sumaPrimoMenores n = sumaMenores n primos 0
   where sumaMenores n (x:xs) a | n <= x    = a
                                | otherwise = sumaMenores n xs (a+x)

-- Por comprensión
sumaPrimoMenores2 :: Integer -> Integer
sumaPrimoMenores2 n = sum (takeWhile (<n) primos)

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

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

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

-- Ejercicio 1.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 1.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 2. 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, x <= n-x, elem (n-x) primosN]

where primosN = takeWhile (<=n) primos

-- El cálculo es

-- ghci> head [x | x <- [1..], length (sumaDeDosPrimos x) == 10]

-- 114

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

-- Ejercicio 3. Definir la función

-- esProductoDeDosPrimos :: Int -> Bool

-- tal que (esProductoDeDosPrimos n) se verifica si n es el producto de

-- dos primos distintos. Por ejemplo,

-- esProductoDeDosPrimos 6 == True

-- esProductoDeDosPrimos 9 == False

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

esProductoDeDosPrimos :: Int -> Bool

esProductoDeDosPrimos n =

[x | x <- primosN,

mod n x == 0,

div n x /= x,

elem (div n x) primosN] /= []

where primosN = takeWhile (<=n) primos

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

-- Ejercicio 4.1. [Problema 37 del proyecto Euler] Un número primo es

-- truncable si los números que se obtienen eliminado cifras, de derecha

-- a izquierda, son primos. Por ejemplo, 599 es un primo truncable

-- porque 599, 59 y 5 son primos; en cambio, 577 es un primo no

-- truncable porque 57 no es primo.

-- Definir la función

-- primoTruncable :: Int -> Bool

-- tal que (primoTruncable x) se verifica si x es un primo

-- truncable. Por ejemplo,

-- primoTruncable 599 == True

-- primoTruncable 577 == False

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

primoTruncable :: Int -> Bool

primoTruncable x

| x < 10 = primo x

| otherwise = primo x && primoTruncable (x `div` 10)

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

-- Ejercicio 4.2. Definir la función

-- sumaPrimosTruncables :: Int -> Int

-- tal que (sumaPrimosTruncables n) es la suma de los n primeros primos

-- truncables. Por ejemplo,

-- sumaPrimosTruncables 10 == 249

-- Calcular la suma de los 20 primos truncables.

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

sumaPrimosTruncables :: Int -> Int

sumaPrimosTruncables n =

sum (take n [x | x <- primos, primoTruncable x])

-- El cálculo es

-- ghci> sumaPrimosTruncables 20

-- 2551

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

-- Ejercicio 5.1. Definir la función

-- intercala :: a -> [a] -> [[a]]

-- tal que (intercala x ys) es la lista de las listas obtenidas

-- intercalando x entre los elementos de ys. Por ejemplo,

-- intercala 1 [2,3] == [[1,2,3],[2,1,3],[2,3,1]]

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

-- Una definición recursiva es

intercala1 :: a -> [a] -> [[a]]

intercala1 x [] = [[x]]

intercala1 x (y:ys) = (x:y:ys) : [y:zs | zs <- intercala1 x ys]

-- Otra definición, más eficiente, es

intercala :: a -> [a] -> [[a]]

intercala y xs =

[take n xs ++ (y : drop n xs) | n <- [0..length xs]]

-- Por ejemplo,

-- ghci> length (intercala1 1 [2..10^4])

-- 10000

-- (11.63 secs, 3016915472 bytes)

-- ghci> length (intercala 1 [2..10^4])

-- 10000

-- (0.02 secs, 2631448 bytes)

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

-- Ejercicio 5.2. Definir la función

-- permutaciones :: [a] -> [[a]]

-- tal que (permutaciones xs) es la lista de las permutaciones de la

-- lista xs. Por ejemplo,

-- permutaciones "bc" == ["bc","cb"]

-- permutaciones "abc" == ["abc","bac","bca","acb","cab","cba"]

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

permutaciones :: [a] -> [[a]]

permutaciones [] = [[]]

permutaciones (x:xs) =

concat [intercala x ys | ys <- permutaciones xs]

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

-- Ejercicio 5.3. Definir la función

-- permutacionesN :: Integer -> [Integer]

-- tal que (permutacionesN x) es la lista de los números obtenidos

-- permutando las cifras de x. Por ejemplo,

-- permutacionesN 352 == [352,532,523,325,235,253]

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

permutacionesN :: Int -> [Int]

permutacionesN x = [read ys | ys <- permutaciones (show x)]

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

-- Ejercicio 5.4. Un primo permutable es un número primo tal que todos

-- los números obtenidos permutando sus cifras son primos. Por ejemplo,

-- 337 es un primo permutable ya que 337, 373 y 733 son primos.

-- Definir la función

-- primoPermutable :: Integer -> Bool

-- tal que (primoPermutable x) se verifica si x es un primo

-- permutable. Por ejemplo,

-- primoPermutable 17 == True

-- primoPermutable 19 == False

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

primoPermutable :: Int -> Bool

primoPermutable x = and [primo y | y <- permutacionesN x]

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

-- Ejercicio 6.1. Los números enteros se pueden ordenar como sigue

-- 0, -1, 1, -2, 2, -3, 3, -4, 4, -5, 5, -6, 6, -7, 7, ...

-- Definir, por comprensión, la constante

-- enteros :: [Int]

-- tal que enteros es la lista de los enteros con la ordenación

-- anterior. Por ejemplo,

-- take 10 enteros == [0,-1,1,-2,2,-3,3,-4,4,-5]

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

enteros :: [Int]

enteros = 0 : concat [[-x,x] | x <- [1..]]

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

-- Ejercicio 6.2. Definir, por iteración, la constante

-- enteros' :: [Int]

-- tal que enteros' es la lista de los enteros con la ordenación

-- anterior. Por ejemplo,

-- take 10 enteros == [0,-1,1,-2,2,-3,3,-4,4,-5]

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

enteros' :: [Int]

enteros' = iterate siguiente 0

where siguiente x | x >= 0 = -x-1

| otherwise = -x

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

-- Ejercicio 6.3. Definir, por selección con takeWhile, la función

-- posicion :: Int -> Int

-- tal que (posicion x) es la posición del entero x en la ordenación

-- anterior. Por ejemplo,

-- posicion 2 == 4

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

posicion :: Int -> Int

posicion x = length (takeWhile (/=x) enteros)

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

-- Ejercicio 6.4. Definir, por recursión, la función

-- posicionR :: Int -> Int

-- tal que (posicionR x) es la posición del entero x en la ordenación

-- anterior. Por ejemplo,

-- posicionR 2 == 4

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

posicionR :: Int -> Int

posicionR x = aux enteros 0

where aux (y:ys) n | x == y = n

| otherwise = aux ys (n+1)

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

-- Ejercicio 6.5. Definir, por comprensión, la función

-- posicionC :: Int -> Int

-- tal que (posicionC x) es la posición del entero x en la ordenación

-- anterior. Por ejemplo,

-- posicionC 2 == 4

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

posicionC :: Int -> Int

posicionC x = head [n | (n,y) <- zip [0..] enteros, y == x]

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

-- Ejercicio 6.6. Definir, sin búsqueda, la función

-- posicion2 :: Int -> Int

-- tal que (posicion2 x) es la posición del entero x en la ordenación

-- anterior. Por ejemplo,

-- posicion2 2 == 4

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

-- Definición directa

posicion2 :: Int -> Int

posicion2 x | x >= 0 = 2*x

| otherwise = 2*(-x)-1

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

-- Ejercicio 7. (Problema 10 del Proyecto Euler) Definir la función

-- sumaPrimoMenores :: Integer -> Integer

-- tal que (sumaPrimoMenores n) es la suma de los primos menores que

-- n. Por ejemplo,

-- sumaPrimoMenores 10 == 17

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

-- Por recursión

sumaPrimoMenores :: Integer -> Integer

sumaPrimoMenores n = sumaMenores n primos 0

where sumaMenores n (x:xs) a | n <= x = a

| otherwise = sumaMenores n xs (a+x)

-- Por comprensión

sumaPrimoMenores2 :: Integer -> Integer

sumaPrimoMenores2 n = sum (takeWhile (<n) primos)

Se puede imprimir o compartir con