I1M2013: 6º examen de programación con Haskell

En la clase de hoy del curso Informática (de 1º de Grado en Matemáticas) se ha realizado el 6º examen del curso en dos turnos. A continuación se muestran los ejercicios y soluciones de cada examen.

Ejercicios y soluciones del primer turno

-- Librerías auxiliares                                             --
-- ====================
import Data.List
import Data.Array

-- ---------------------------------------------------------------------
-- Ejercicio 1 [2 puntos]. Definir la función 
--     siembra :: [a] -> [[a]] -> [[a]]
-- tal que (siembra xs yss) es la lista obtenida introduciendo cada uno
-- de los elementos de xs en la lista correspondiente de yss; es decir,
-- el primer elemento de xs en la primera lista de yss, el segundo
-- elemento de xs en la segunda lista de yss, etc. Por ejemplo,
--    siembra [1,2,3] [[4,7],[6],[9,5,8]]  ==  [[1,4,7],[2,6],[3,9,5,8]]
--    siembra [1,2] [[4,7],[6],[9,5,8]]    ==  [[1,4,7],[2,6],[9,5,8]]
--    siembra [1,2,3] [[4,7],[6]]          ==  [[1,4,7],[2,6]]
-- ---------------------------------------------------------------------

siembra :: [a] -> [[a]] -> [[a]]
siembra [] yss          = yss
siembra xs []           = []
siembra (x:xs) (ys:yss) = (x:ys) : siembra xs yss

-- ---------------------------------------------------------------------
-- Ejercicio 2 [2 puntos]. Definir la función 
--    primosEquidistantes :: Integer -> [(Integer,Integer)]
-- tal que (primosEquidistantes k) es la lista de los pares de primos
-- consecutivos cuya diferencia es k. Por ejemplo,
--    take 3 (primosEquidistantes 2)  ==  [(3,5),(5,7),(11,13)]
--    take 3 (primosEquidistantes 4)  ==  [(7,11),(13,17),(19,23)]
--    take 3 (primosEquidistantes 6)  ==  [(23,29),(31,37),(47,53)]
--    take 3 (primosEquidistantes 8)  ==  [(89,97),(359,367),(389,397)]
-- ---------------------------------------------------------------------

primosEquidistantes :: Integer -> [(Integer,Integer)]
primosEquidistantes k = aux primos
    where aux (x:y:ps) | y - x == k = (x,y) : aux (y:ps)
                       | otherwise  = aux (y:ps)
 
-- (primo x) se verifica si x es primo. Por ejemplo,
--    primo 7  ==  True
--    primo 8  ==  False
primo :: Integer -> Bool
primo x = [y | y <- [1..x], x `rem` y == 0] == [1,x]
 
-- primos es la lista de los números primos. Por ejemplo,
--    take 10 primos  ==  [2,3,5,7,11,13,17,19,23,29]
primos :: [Integer]
primos = 2 : [x | x <- [3,5..], primo x]

-- ---------------------------------------------------------------------
-- Ejercicio 3 [2 puntos]. Se consideran los árboles con operaciones
-- booleanas definidos por  
--    data ArbolB = H Bool 
--                | Conj ArbolB ArbolB
--                | Disy ArbolB ArbolB
--                | Neg ArbolB
-- 
-- Por ejemplo, los árboles
--                Conj                            Conj          
--               /   \                           /   \          
--              /     \                         /     \         
--           Disy      Conj                  Disy      Conj     
--          /   \       /  \                /   \      /   \    
--       Conj    Neg   Neg True          Conj    Neg   Neg  True 
--       /  \    |     |                 /  \    |     |        
--    True False False False          True False True  False     
--
-- se definen por
--    ej1, ej2:: ArbolB
--    ej1 = Conj (Disy (Conj (H True) (H False))
--                     (Neg (H False)))
--               (Conj (Neg (H False))
--                     (H True))
--    
--    ej2 = Conj (Disy (Conj (H True) (H False))
--                     (Neg (H True)))
--               (Conj (Neg (H False))
--                     (H True))
-- 
-- Definir la función 
--    valor:: ArbolB -> Bool
-- tal que (valor ar) es el resultado de procesar el árbol realizando
-- las operaciones booleanas especificadas en los nodos. Por ejemplo,
--    valor ej1 == True
--    valor ej2 == False
-- ---------------------------------------------------------------------

data ArbolB = H Bool 
            | Conj ArbolB ArbolB
            | Disy ArbolB ArbolB
            | Neg ArbolB

ej1, ej2:: ArbolB
ej1 = Conj (Disy (Conj (H True) (H False))
                 (Neg (H False)))
           (Conj (Neg (H False))
                 (H True))

ej2 = Conj (Disy (Conj (H True) (H False))
                 (Neg (H True)))
           (Conj (Neg (H False))
                 (H True))

valor:: ArbolB -> Bool
valor (H x)     = x
valor (Neg a)    = not (valor a)
valor (Conj i d) = (valor i) && (valor d)
valor (Disy i d) = (valor i) || (valor d)

-- ---------------------------------------------------------------------
-- Ejercicio 4 [2 puntos]. La matriz de Vandermonde generada por
-- [a(1),a(2),a(3),...,a(n)] es la siguiente
--    |1  a(1)  a(1)^2 ... a(1)^{n-1}|
--    |1  a(2)  a(2)^2 ... a(2)^{n-1}|
--    |1  a(3)  a(3)^2 ... a(3)^{n-1}|
--    |.  .     .          .         |
--    |.  .     .          .         |
--    |.  .     .          .         |
--    |1  a(n)  a(n)^2 ... a(n)^{n-1}|
--
-- Las matrices se representan con tablas cuyos índices son pares de
-- números naturales.  
--    type Matriz a = Array (Int,Int) a
--
-- Definir la función 
--    vandermonde:: [Integer] -> Matriz Integer
-- tal que (vandermonde xs) es la matriz de Vandermonde cuyos
-- generadores son los elementos de xs. Por ejemplo,
--    ghci> vandermonde [5,2,3,4]
--    array ((1,1),(4,4)) [((1,1),1),((1,2),5),((1,3),25),((1,4),125),
--                         ((2,1),1),((2,2),2),((2,3), 4),((2,4),  8),
--                         ((3,1),1),((3,2),3),((3,3), 9),((3,4), 27),
--                         ((4,1),1),((4,2),4),((4,3),16),((4,4), 64)]
-- ---------------------------------------------------------------------

type Matriz a = Array (Int,Int) a

-- 1ª solución
-- ===========

vandermonde1 :: [Integer] -> Matriz Integer
vandermonde1 xs = array ((1,1), (n,n)) 
                  [((i,j), f i j) | i <- [1..n], j <- [1..n]]
      where n     = length xs
            f i j = (xs!!(i-1))^(j-1)

-- 2ª solución
-- ===========

vandermonde2 :: [Integer] -> Matriz Integer
vandermonde2 xs = listArray ((1,1),(n,n)) (concat (listaVandermonde xs))
    where n = length xs

-- (listaVandermonde xs) es la lista correspondiente a la matriz de
-- Vandermonde generada por xs. Por ejemplo,
--    ghci> listaVandermonde [5,2,3,4]
--    [[1,5,25,125],[1,2,4,8],[1,3,9,27],[1,4,16,64]]
listaVandermonde :: [Integer] -> [[Integer]]
listaVandermonde xs = [[x^i | i <- [0..n-1]] | x <- xs]
    where n = length xs

-- ---------------------------------------------------------------------
-- Ejercicio 5 [2 puntos]. El número 595 es palíndromo y, además, es
-- suma de cuadrados consecutivos, pues 
--    595 = 6^2 + 7^2 + 8^2 + 9^2 + 10^2 + 11^2 + 12^2. 
-- 
-- Definir la función 
--    sucesion:: [Integer]
-- tal que sucesion es la lista de los números que son palíndromos y
-- suma de cuadrados consecutivos. Por ejemplo,
--    take 10 sucesion == [1,4,5,9,55,77,121,181,313,434]
--    take 15 sucesion == [1,4,5,9,55,77,121,181,313,434,484,505,545,595,636]
-- ---------------------------------------------------------------------

sucesion:: [Integer]
sucesion = [x | x <-[1..], palindromo x, esSumaCuadradosConsecutivos x]

palindromo :: Integer -> Bool
palindromo n = show n == reverse (show n)

sucSumaCuadradosDesde :: Integer -> [Integer]    
sucSumaCuadradosDesde k = scanl (\s n -> s + n^2) 0 [k..]


esSumaCuadradosConsecutivos n =
    or [pertenece n (sucSumaCuadradosDesde k) | k <- [1..m]]
    where pertenece x xs = elem x (takeWhile (<=x) xs)
          m              = floor (sqrt (fromIntegral n))

-- 2ª solución para esSumaCuadradosConsecutivos:
        
esSumaCuadradosConsecutivos2 n = any (==n) (map sum yss)
    where m = floor (sqrt (fromIntegral n))
          xss = segmentos [1..m]
          yss = map (map (^2)) xss

segmentos :: [a] -> [[a]]
segmentos xs = concat [tail (inits ys) | ys <- init (tails xs)]
  
sucesion2:: [Integer]
sucesion2 = [x | x <-[1..], palindromo x, esSumaCuadradosConsecutivos2 x]

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

-- Librerías auxiliares --

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

import Data.List

import Data.Array

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

-- Ejercicio 1 [2 puntos]. Definir la función

-- siembra :: [a] -> [[a]] -> [[a]]

-- tal que (siembra xs yss) es la lista obtenida introduciendo cada uno

-- de los elementos de xs en la lista correspondiente de yss; es decir,

-- el primer elemento de xs en la primera lista de yss, el segundo

-- elemento de xs en la segunda lista de yss, etc. Por ejemplo,

-- siembra [1,2,3] [[4,7],[6],[9,5,8]] == [[1,4,7],[2,6],[3,9,5,8]]

-- siembra [1,2] [[4,7],[6],[9,5,8]] == [[1,4,7],[2,6],[9,5,8]]

-- siembra [1,2,3] [[4,7],[6]] == [[1,4,7],[2,6]]

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

siembra :: [a] -> [[a]] -> [[a]]

siembra [] yss = yss

siembra xs [] = []

siembra (x:xs) (ys:yss) = (x:ys) : siembra xs yss

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

-- Ejercicio 2 [2 puntos]. Definir la función

-- primosEquidistantes :: Integer -> [(Integer,Integer)]

-- tal que (primosEquidistantes k) es la lista de los pares de primos

-- consecutivos cuya diferencia es k. Por ejemplo,

-- take 3 (primosEquidistantes 2) == [(3,5),(5,7),(11,13)]

-- take 3 (primosEquidistantes 4) == [(7,11),(13,17),(19,23)]

-- take 3 (primosEquidistantes 6) == [(23,29),(31,37),(47,53)]

-- take 3 (primosEquidistantes 8) == [(89,97),(359,367),(389,397)]

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

primosEquidistantes :: Integer -> [(Integer,Integer)]

primosEquidistantes k = aux primos

where aux (x:y:ps) | y - x == k = (x,y) : aux (y:ps)

| otherwise = aux (y:ps)

-- (primo x) se verifica si x es primo. Por ejemplo,

-- primo 7 == True

-- primo 8 == False

primo :: Integer -> Bool

primo x = [y | y <- [1..x], x `rem` y == 0] == [1,x]

-- primos es la lista de los números primos. Por ejemplo,

-- take 10 primos == [2,3,5,7,11,13,17,19,23,29]

primos :: [Integer]

primos = 2 : [x | x <- [3,5..], primo x]

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

-- Ejercicio 3 [2 puntos]. Se consideran los árboles con operaciones

-- booleanas definidos por

-- data ArbolB = H Bool

-- | Conj ArbolB ArbolB

-- | Disy ArbolB ArbolB

-- | Neg ArbolB

-- Por ejemplo, los árboles

-- Conj Conj

-- / \ / \

-- Disy Conj Disy Conj

-- / \ / \ / \ / \

-- Conj Neg Neg True Conj Neg Neg True

-- / \ | | / \ | |

-- True False False False True False True False

-- se definen por

-- ej1, ej2:: ArbolB

-- ej1 = Conj (Disy (Conj (H True) (H False))

-- (Neg (H False)))

-- (Conj (Neg (H False))

-- (H True))

-- ej2 = Conj (Disy (Conj (H True) (H False))

-- (Neg (H True)))

-- (Conj (Neg (H False))

-- (H True))

-- Definir la función

-- valor:: ArbolB -> Bool

-- tal que (valor ar) es el resultado de procesar el árbol realizando

-- las operaciones booleanas especificadas en los nodos. Por ejemplo,

-- valor ej1 == True

-- valor ej2 == False

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

data ArbolB = H Bool

| Conj ArbolB ArbolB

| Disy ArbolB ArbolB

| Neg ArbolB

ej1, ej2:: ArbolB

ej1 = Conj (Disy (Conj (H True) (H False))

(Neg (H False)))

(Conj (Neg (H False))

(H True))

ej2 = Conj (Disy (Conj (H True) (H False))

(Neg (H True)))

(Conj (Neg (H False))

(H True))

valor:: ArbolB -> Bool

valor (H x) = x

valor (Neg a) = not (valor a)

valor (Conj i d) = (valor i) && (valor d)

valor (Disy i d) = (valor i) || (valor d)

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

-- Ejercicio 4 [2 puntos]. La matriz de Vandermonde generada por

-- [a(1),a(2),a(3),...,a(n)] es la siguiente

-- |1 a(1) a(1)^2 ... a(1)^{n-1}|

-- |1 a(2) a(2)^2 ... a(2)^{n-1}|

-- |1 a(3) a(3)^2 ... a(3)^{n-1}|

-- |. . . . |

-- |1 a(n) a(n)^2 ... a(n)^{n-1}|

-- Las matrices se representan con tablas cuyos índices son pares de

-- números naturales.

-- type Matriz a = Array (Int,Int) a

-- Definir la función

-- vandermonde:: [Integer] -> Matriz Integer

-- tal que (vandermonde xs) es la matriz de Vandermonde cuyos

-- generadores son los elementos de xs. Por ejemplo,

-- ghci> vandermonde [5,2,3,4]

-- array ((1,1),(4,4)) [((1,1),1),((1,2),5),((1,3),25),((1,4),125),

-- ((2,1),1),((2,2),2),((2,3), 4),((2,4), 8),

-- ((3,1),1),((3,2),3),((3,3), 9),((3,4), 27),

-- ((4,1),1),((4,2),4),((4,3),16),((4,4), 64)]

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

type Matriz a = Array (Int,Int) a

-- 1ª solución

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

vandermonde1 :: [Integer] -> Matriz Integer

vandermonde1 xs = array ((1,1), (n,n))

[((i,j), f i j) | i <- [1..n], j <- [1..n]]

where n = length xs

f i j = (xs!!(i-1))^(j-1)

-- 2ª solución

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

vandermonde2 :: [Integer] -> Matriz Integer

vandermonde2 xs = listArray ((1,1),(n,n)) (concat (listaVandermonde xs))

where n = length xs

-- (listaVandermonde xs) es la lista correspondiente a la matriz de

-- Vandermonde generada por xs. Por ejemplo,

-- ghci> listaVandermonde [5,2,3,4]

-- [[1,5,25,125],[1,2,4,8],[1,3,9,27],[1,4,16,64]]

listaVandermonde :: [Integer] -> [[Integer]]

listaVandermonde xs = [[x^i | i <- [0..n-1]] | x <- xs]

where n = length xs

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

-- Ejercicio 5 [2 puntos]. El número 595 es palíndromo y, además, es

-- suma de cuadrados consecutivos, pues

-- 595 = 6^2 + 7^2 + 8^2 + 9^2 + 10^2 + 11^2 + 12^2.

-- Definir la función

-- sucesion:: [Integer]

-- tal que sucesion es la lista de los números que son palíndromos y

-- suma de cuadrados consecutivos. Por ejemplo,

-- take 10 sucesion == [1,4,5,9,55,77,121,181,313,434]

-- take 15 sucesion == [1,4,5,9,55,77,121,181,313,434,484,505,545,595,636]

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

sucesion:: [Integer]

sucesion = [x | x <-[1..], palindromo x, esSumaCuadradosConsecutivos x]

palindromo :: Integer -> Bool

palindromo n = show n == reverse (show n)

sucSumaCuadradosDesde :: Integer -> [Integer]

sucSumaCuadradosDesde k = scanl (\s n -> s + n^2) 0 [k..]

esSumaCuadradosConsecutivos n =

or [pertenece n (sucSumaCuadradosDesde k) | k <- [1..m]]

where pertenece x xs = elem x (takeWhile (<=x) xs)

m = floor (sqrt (fromIntegral n))

-- 2ª solución para esSumaCuadradosConsecutivos:

esSumaCuadradosConsecutivos2 n = any (==n) (map sum yss)

where m = floor (sqrt (fromIntegral n))

xss = segmentos [1..m]

yss = map (map (^2)) xss

segmentos :: [a] -> [[a]]

segmentos xs = concat [tail (inits ys) | ys <- init (tails xs)]

sucesion2:: [Integer]

sucesion2 = [x | x <-[1..], palindromo x, esSumaCuadradosConsecutivos2 x]

Ejercicios y soluciones del segundo turno

-- Librería auxiliar
-- =================
import Data.Array

-- ---------------------------------------------------------------------
-- Ejercicio 1 [2 puntos]. Definir la función
--    divisiblesPorPrimero :: [Int] -> Bool
-- tal que (divisibles xs) se verifica si todos los elementos positivos
-- de xs son divisibles por el primero. Por ejemplo,
--    divisiblesPorPrimero [2,6,-3,0,18,-17,10]  ==  True
--    divisiblesPorPrimero [-13]                 ==  True
--    divisiblesPorPrimero [-3,6,1,-3,9,18]      ==  False
--    divisiblesPorPrimero [5,-2,-6,3]           ==  False
--    divisiblesPorPrimero []                    ==  False
--    divisiblesPorPrimero [0,2,4]               ==  False
-- ---------------------------------------------------------------------

-- 1ª definición (por comprensión)
divisiblesPorPrimero1 :: [Int] -> Bool
divisiblesPorPrimero1 []     = False
divisiblesPorPrimero1 (0:_)  = False
divisiblesPorPrimero1 (x:xs) = and [y `rem` x == 0 | y <- xs, y > 0]

-- 2ª definición (por recursión)
divisiblesPorPrimero2 :: [Int] -> Bool
divisiblesPorPrimero2 []     = False
divisiblesPorPrimero2 (0:_)  = False
divisiblesPorPrimero2 (x:xs) = aux xs
    where aux [] = True
          aux (y:ys) | y > 0     = y `rem` x == 0 && aux ys
                     | otherwise = aux ys 

-- ---------------------------------------------------------------------
-- Ejercicio 2 [2 puntos]. Definir la constante
--    primosConsecutivosConMediaCapicua :: [(Int,Int,Int)]
-- tal que primosConsecutivosConMediaCapicua es la lista de las ternas 
-- (x,y,z) tales que x e y son primos consecutivos tales que su media,
-- z, es capicúa. Por ejemplo,
--    ghci> take 5 primosConsecutivosConMediaCapicua
--    [(3,5,4),(5,7,6),(7,11,9),(97,101,99),(109,113,111)]
-- Calcular cuántos hay anteriores a 2014.
-- ---------------------------------------------------------------------

primosConsecutivosConMediaCapicua :: [(Int,Int,Int)]
primosConsecutivosConMediaCapicua =
    [(x,y,z) | (x,y) <- zip primos (tail primos),
               let z = (x + y) `div` 2,
               capicua z]

-- (primo x) se verifica si x es primo. Por ejemplo,
--    primo 7  ==  True
--    primo 8  ==  False
primo :: Int -> Bool
primo x = [y | y <- [1..x], x `rem` y == 0] == [1,x]

-- primos es la lista de los números primos mayores que 2. Por ejemplo,
--    take 10 primos  ==  [3,5,7,11,13,17,19,23,29]
primos :: [Int]
primos = [x | x <- [3,5..], primo x]

-- (capicua x) se verifica si x es capicúa. Por ejemplo,
capicua :: Int -> Bool
capicua x = ys == reverse ys
    where ys = show x

-- El cálculo es
--    ghci> length (takeWhile (\(x,y,z) -> y < 2014) primosConsecutivosConMediaCapicua)
--    20

-- ---------------------------------------------------------------------
-- Ejercicio 3 [2 puntos]. Un elemento x de un conjunto xs es minimal
-- respecto de una relación r si no existe ningún elemento y en xs tal
-- que (r y x). Por ejemplo,  
-- 
-- Definir la función
--    minimales :: Eq a => (a -> a -> Bool) -> [a] -> [a]
-- tal que (minimales xss) es la lista de los elementos minimales de
-- xs. Por ejemplo, 
--    ghci> minimales (\x y -> y `rem` x == 0) [2,3,6,12,18]
--    [2,3]
--    ghci> minimales (\x y -> x `rem` y == 0) [2,3,6,12,18]
--    [12,18]
--    ghci> minimales (\x y -> maximum x < maximum y) ["ac","cd","aacb"]
--    ["ac","aacb"]
--    ghci> minimales (\xs ys -> all (`elem` ys) xs) ["ab","c","abc","d","dc"]
--    ["ab","c","d"]
-- ---------------------------------------------------------------------

minimales :: Eq a => (a -> a -> Bool) -> [a] -> [a]
minimales r xs = [x | x <- xs, esMinimal r xs x]

-- (esMinimal r xs x) s verifica si xs no tiene ningún elemento menor
-- que x respecto de la relación r. 
esMinimal :: Eq a => (a -> a -> Bool) -> [a] -> a -> Bool
esMinimal r xs x = null [y | y <- xs, y /= x, r y x]

-- ---------------------------------------------------------------------
-- Ejercicio 4 [2 puntos]. Una matriz es monomial si en cada una de sus
-- filas y columnas todos los elementos son nulos excepto 1. Por
-- ejemplo, de las matrices 
--    |0  0 3 0|     |0  0 3 0|
--    |0 -2 0 0|     |0 -2 0 0|
--    |1  0 0 0|     |1  0 0 0|
--    |0  0 0 1|     |0  1 0 1|
-- la primera es monomial y la segunda no lo es.
--
-- Las matrices puede representarse mediante tablas cuyos
-- índices son pares de números naturales:    
--    type Matriz = Array (Int,Int) Int
-- Por ejemplo, las matrices anteriores se pueden definir por
--    ej1, ej2 :: Matriz
--    ej1 = listArray ((1,1),(4,4)) [0,  0, 3, 0,
--                                   0, -2, 0, 0,
--                                   1,  0, 0, 0,
--                                   0,  0, 0, 1]
--    ej2 = listArray ((1,1),(4,4)) [0,  0, 3, 0,
--                                   0, -2, 0, 0,
--                                   1,  0, 0, 0,
--                                   0,  1, 0, 1]
-- Definir la función 
--    esMonomial :: Matriz -> Bool
-- tal que (esMonomial p) se verifica si la matriz p es monomial. Por
-- ejemplo, 
--    esMonomial ej1  ==  True
--    esMonomial ej2  ==  False
-- ---------------------------------------------------------------------

type Matriz = Array (Int,Int) Int

ej1, ej2 :: Matriz
ej1 = listArray ((1,1),(4,4)) [0,  0, 3, 0,
                               0, -2, 0, 0,
                               1,  0, 0, 0,
                               0,  0, 0, 1]
ej2 = listArray ((1,1),(4,4)) [0,  0, 3, 0,
                               0, -2, 0, 0,
                               1,  0, 0, 0,
                               0,  1, 0, 1]

esMonomial :: Matriz -> Bool
esMonomial p = all esListaMonomial (filas p ++ columnas p)

-- (filas p) es la lista de las filas de la matriz p. Por ejemplo,
--    filas ej1  ==  [[0,0,3,0],[0,-2,0,0],[1,0,0,0],[0,0,0,1]]
filas :: Matriz -> [[Int]]
filas p = [[p!(i,j) | j <- [1..n]] | i <- [1..m]]
    where (_,(m,n)) = bounds p

-- (columnas p) es la lista de las columnas de la matriz p. Por ejemplo,
--    columnas ej1  ==  [[0,0,1,0],[0,-2,0,0],[3,0,0,0],[0,0,0,1]]
columnas :: Matriz -> [[Int]]
columnas p = [[p!(i,j) | i <- [1..m]] | j <- [1..n]]
    where (_,(m,n)) = bounds p

-- (esListaMonomial xs) se verifica si todos los elementos de xs excepto
-- uno son nulos. Por ejemplo,
--    esListaMonomial [0,3,0,0]  ==  True
--    esListaMonomial [0,3,0,2]  ==  False
--    esListaMonomial [0,0,0,0]  ==  False
esListaMonomial :: [Int] -> Bool
esListaMonomial xs = length (filter (/=0) xs) == 1

-- ---------------------------------------------------------------------
-- Ejercicio 5 [2 puntos]. Se consideran las expresiones vectoriales
-- formadas por un vector, la suma de dos expresiones vectoriales o el
-- producto de un entero por una expresión vectorial. El siguiente tipo
-- de dato define las expresiones vectoriales 
--    data ExpV = Vec Int Int
--              | Sum ExpV ExpV
--              | Mul Int ExpV
--              deriving Show
-- Definir la función 
--    valor :: ExpV -> (Int,Int)
-- tal que (valor e) es el valor de la expresión vectorial c. Por
-- ejemplo, 
--    valor (Vec 1 2)                                  ==  (1,2)
--    valor (Sum (Vec 1 2 ) (Vec 3 4))                 ==  (4,6)
--    valor (Mul 2 (Vec 3 4))                          ==  (6,8)
--    valor (Mul 2 (Sum (Vec 1 2 ) (Vec 3 4)))         ==  (8,12)
--    valor (Sum (Mul 2 (Vec 1 2)) (Mul 2 (Vec 3 4)))  ==  (8,12)
-- ---------------------------------------------------------------------

data ExpV = Vec Int Int
          | Sum ExpV ExpV
          | Mul Int ExpV
          deriving Show

-- 1ª solución
-- ===========
valor :: ExpV -> (Int,Int)
valor (Vec x y)   = (x,y)
valor (Sum e1 e2) = (x1+x2,y1+y2) where (x1,y1) = valor e1  
                                        (x2,y2) = valor e2  
valor (Mul n e)   = (n*x,n*y) where (x,y) = valor e  

-- 2ª solución
-- ===========
valor2 :: ExpV -> (Int,Int)
valor2 (Vec a b)   = (a, b)
valor2 (Sum e1 e2) = suma (valor2 e1) (valor2 e2)
valor2 (Mul n e1)  = multiplica n (valor2 e1)

suma :: (Int,Int) -> (Int,Int) -> (Int,Int)
suma (a,b) (c,d) = (a+c,b+d)

multiplica :: Int -> (Int, Int) -> (Int, Int)
multiplica n (a,b) = (n*a,n*b)

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

-- Librería auxiliar

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

import Data.Array

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

-- Ejercicio 1 [2 puntos]. Definir la función

-- divisiblesPorPrimero :: [Int] -> Bool

-- tal que (divisibles xs) se verifica si todos los elementos positivos

-- de xs son divisibles por el primero. Por ejemplo,

-- divisiblesPorPrimero [2,6,-3,0,18,-17,10] == True

-- divisiblesPorPrimero [-13] == True

-- divisiblesPorPrimero [-3,6,1,-3,9,18] == False

-- divisiblesPorPrimero [5,-2,-6,3] == False

-- divisiblesPorPrimero [] == False

-- divisiblesPorPrimero [0,2,4] == False

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

-- 1ª definición (por comprensión)

divisiblesPorPrimero1 :: [Int] -> Bool

divisiblesPorPrimero1 [] = False

divisiblesPorPrimero1 (0:_) = False

divisiblesPorPrimero1 (x:xs) = and [y `rem` x == 0 | y <- xs, y > 0]

-- 2ª definición (por recursión)

divisiblesPorPrimero2 :: [Int] -> Bool

divisiblesPorPrimero2 [] = False

divisiblesPorPrimero2 (0:_) = False

divisiblesPorPrimero2 (x:xs) = aux xs

where aux [] = True

aux (y:ys) | y > 0 = y `rem` x == 0 && aux ys

| otherwise = aux ys

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

-- Ejercicio 2 [2 puntos]. Definir la constante

-- primosConsecutivosConMediaCapicua :: [(Int,Int,Int)]

-- tal que primosConsecutivosConMediaCapicua es la lista de las ternas

-- (x,y,z) tales que x e y son primos consecutivos tales que su media,

-- z, es capicúa. Por ejemplo,

-- ghci> take 5 primosConsecutivosConMediaCapicua

-- [(3,5,4),(5,7,6),(7,11,9),(97,101,99),(109,113,111)]

-- Calcular cuántos hay anteriores a 2014.

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

primosConsecutivosConMediaCapicua :: [(Int,Int,Int)]

primosConsecutivosConMediaCapicua =

[(x,y,z) | (x,y) <- zip primos (tail primos),

let z = (x + y) `div` 2,

capicua z]

-- (primo x) se verifica si x es primo. Por ejemplo,

-- primo 7 == True

-- primo 8 == False

primo :: Int -> Bool

primo x = [y | y <- [1..x], x `rem` y == 0] == [1,x]

-- primos es la lista de los números primos mayores que 2. Por ejemplo,

-- take 10 primos == [3,5,7,11,13,17,19,23,29]

primos :: [Int]

primos = [x | x <- [3,5..], primo x]

-- (capicua x) se verifica si x es capicúa. Por ejemplo,

capicua :: Int -> Bool

capicua x = ys == reverse ys

where ys = show x

-- El cálculo es

-- ghci> length (takeWhile (\(x,y,z) -> y < 2014) primosConsecutivosConMediaCapicua)

-- 20

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

-- Ejercicio 3 [2 puntos]. Un elemento x de un conjunto xs es minimal

-- respecto de una relación r si no existe ningún elemento y en xs tal

-- que (r y x). Por ejemplo,

-- Definir la función

-- minimales :: Eq a => (a -> a -> Bool) -> [a] -> [a]

-- tal que (minimales xss) es la lista de los elementos minimales de

-- xs. Por ejemplo,

-- ghci> minimales (\x y -> y `rem` x == 0) [2,3,6,12,18]

-- [2,3]

-- ghci> minimales (\x y -> x `rem` y == 0) [2,3,6,12,18]

-- [12,18]

-- ghci> minimales (\x y -> maximum x < maximum y) ["ac","cd","aacb"]

-- ["ac","aacb"]

-- ghci> minimales (\xs ys -> all (`elem` ys) xs) ["ab","c","abc","d","dc"]

-- ["ab","c","d"]

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

minimales :: Eq a => (a -> a -> Bool) -> [a] -> [a]

minimales r xs = [x | x <- xs, esMinimal r xs x]

-- (esMinimal r xs x) s verifica si xs no tiene ningún elemento menor

-- que x respecto de la relación r.

esMinimal :: Eq a => (a -> a -> Bool) -> [a] -> a -> Bool

esMinimal r xs x = null [y | y <- xs, y /= x, r y x]

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

-- Ejercicio 4 [2 puntos]. Una matriz es monomial si en cada una de sus

-- filas y columnas todos los elementos son nulos excepto 1. Por

-- ejemplo, de las matrices

-- |0 0 3 0| |0 0 3 0|

-- |0 -2 0 0| |0 -2 0 0|

-- |1 0 0 0| |1 0 0 0|

-- |0 0 0 1| |0 1 0 1|

-- la primera es monomial y la segunda no lo es.

-- Las matrices puede representarse mediante tablas cuyos

-- índices son pares de números naturales:

-- type Matriz = Array (Int,Int) Int

-- Por ejemplo, las matrices anteriores se pueden definir por

-- ej1, ej2 :: Matriz

-- ej1 = listArray ((1,1),(4,4)) [0, 0, 3, 0,

-- 0, -2, 0, 0,

-- 1, 0, 0, 0,

-- 0, 0, 0, 1]

-- ej2 = listArray ((1,1),(4,4)) [0, 0, 3, 0,

-- 0, -2, 0, 0,

-- 1, 0, 0, 0,

-- 0, 1, 0, 1]

-- Definir la función

-- esMonomial :: Matriz -> Bool

-- tal que (esMonomial p) se verifica si la matriz p es monomial. Por

-- ejemplo,

-- esMonomial ej1 == True

-- esMonomial ej2 == False

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

type Matriz = Array (Int,Int) Int

ej1, ej2 :: Matriz

ej1 = listArray ((1,1),(4,4)) [0, 0, 3, 0,

0, -2, 0, 0,

1, 0, 0, 0,

0, 0, 0, 1]

ej2 = listArray ((1,1),(4,4)) [0, 0, 3, 0,

0, -2, 0, 0,

1, 0, 0, 0,

0, 1, 0, 1]

esMonomial :: Matriz -> Bool

esMonomial p = all esListaMonomial (filas p ++ columnas p)

-- (filas p) es la lista de las filas de la matriz p. Por ejemplo,

-- filas ej1 == [[0,0,3,0],[0,-2,0,0],[1,0,0,0],[0,0,0,1]]

filas :: Matriz -> [[Int]]

filas p = [[p!(i,j) | j <- [1..n]] | i <- [1..m]]

where (_,(m,n)) = bounds p

-- (columnas p) es la lista de las columnas de la matriz p. Por ejemplo,

-- columnas ej1 == [[0,0,1,0],[0,-2,0,0],[3,0,0,0],[0,0,0,1]]

columnas :: Matriz -> [[Int]]

columnas p = [[p!(i,j) | i <- [1..m]] | j <- [1..n]]

where (_,(m,n)) = bounds p

-- (esListaMonomial xs) se verifica si todos los elementos de xs excepto

-- uno son nulos. Por ejemplo,

-- esListaMonomial [0,3,0,0] == True

-- esListaMonomial [0,3,0,2] == False

-- esListaMonomial [0,0,0,0] == False

esListaMonomial :: [Int] -> Bool

esListaMonomial xs = length (filter (/=0) xs) == 1

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

-- Ejercicio 5 [2 puntos]. Se consideran las expresiones vectoriales

-- formadas por un vector, la suma de dos expresiones vectoriales o el

-- producto de un entero por una expresión vectorial. El siguiente tipo

-- de dato define las expresiones vectoriales

-- data ExpV = Vec Int Int

-- | Sum ExpV ExpV

-- | Mul Int ExpV

-- deriving Show

-- Definir la función

-- valor :: ExpV -> (Int,Int)

-- tal que (valor e) es el valor de la expresión vectorial c. Por

-- ejemplo,

-- valor (Vec 1 2) == (1,2)

-- valor (Sum (Vec 1 2 ) (Vec 3 4)) == (4,6)

-- valor (Mul 2 (Vec 3 4)) == (6,8)

-- valor (Mul 2 (Sum (Vec 1 2 ) (Vec 3 4))) == (8,12)

-- valor (Sum (Mul 2 (Vec 1 2)) (Mul 2 (Vec 3 4))) == (8,12)

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

data ExpV = Vec Int Int

| Sum ExpV ExpV

| Mul Int ExpV

deriving Show

-- 1ª solución

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

valor :: ExpV -> (Int,Int)

valor (Vec x y) = (x,y)

valor (Sum e1 e2) = (x1+x2,y1+y2) where (x1,y1) = valor e1

(x2,y2) = valor e2

valor (Mul n e) = (n*x,n*y) where (x,y) = valor e

-- 2ª solución

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

valor2 :: ExpV -> (Int,Int)

valor2 (Vec a b) = (a, b)

valor2 (Sum e1 e2) = suma (valor2 e1) (valor2 e2)

valor2 (Mul n e1) = multiplica n (valor2 e1)

suma :: (Int,Int) -> (Int,Int) -> (Int,Int)

suma (a,b) (c,d) = (a+c,b+d)

multiplica :: Int -> (Int, Int) -> (Int, Int)

multiplica n (a,b) = (n*a,n*b)

Ejercicios y soluciones del primer turno

Ejercicios y soluciones del segundo turno

Se puede imprimir o compartir con