El período de una lista xs es la lista más corta ys tal que xs se puede obtener concatenando varias veces la lista ys. Por ejemplo, el período "abababab" es "ab" ya que "abababab" se obtiene repitiendo tres veces la lista "ab".
Definir la función
periodo :: Eq a => [a] -> [a]
tal que (periodo xs) es el período de xs. Por ejemplo,
periodo "ababab" == "ab" periodo "buenobueno" == "bueno" periodo "oooooo" == "o" periodo "sevilla" == "sevilla"
Definir la función
mezclaTodas :: Ord a => [[a]] -> [a]
tal que (mezclaTodas xss) es la mezcla ordenada de xss, donde tanto xss como sus elementos son listas infinitas ordenadas. Por ejemplo,
λ> take 10 (mezclaTodas [[n,2*n..] | n <- [2..]]) [2,3,4,5,6,7,8,9,10,11] λ> take 10 (mezclaTodas [[n,2*n..] | n <- [2,9..]]) [2,4,6,8,9,10,12,14,16,18]
El siguiente tipo de dato representa expresiones construidas con variables, sumas y productos
data Expr = Var String | S Expr Expr | P Expr Expre
Por ejemplo, x.(y+z) se representa por (P (V "x") (S (V "y") (V "z")))
Una expresión es un término si es un producto de variables. Por ejemplo, x.(y.z) es un término pero x+(y.z) ni x.(y+z) lo son.
Una expresión está en forma normal si es una suma de términos. Por ejemplo, x.(y,z) y x+(y.z) está en forma normal; pero x.(y+z) y (x+y).(x+z) no lo están.
Definir las funciones
esTermino, esNormal :: Expr -> Bool
tales que
esTermino (V "x") == True esTermino (P (V "x") (P (V "y") (V "z"))) == True esTermino (P (V "x") (S (V "y") (V "z"))) == False esTermino (S (V "x") (P (V "y") (V "z"))) == False
esNormal (V "x") == True esNormal (P (V "x") (P (V "y") (V "z"))) == True esNormal (S (V "x") (P (V "y") (V "z"))) == True esNormal (P (V "x") (S (V "y") (V "z"))) == False esNormal (P (S (V "x") (V "y")) (S (V "y") (V "z"))) == False
Una serie de potencias es una serie de la forma
a₀ + a₁x + a₂x² + a₃x³ + ...
Las series de potencias se pueden representar mediante listas infinitas. Por ejemplo, la serie de la función exponencial es
e^x = 1 + x + x²/2! + x³/3! + ...
y se puede representar por [1, 1, 1/2, 1/6, 1/24, 1/120, ...]
Las operaciones con series se pueden ver como una generalización de las de los polinomios.
En lo que sigue, usaremos el tipo (Serie a) para representar las series de potencias con coeficientes en a y su definición es
type Serie a = [a]
Definir las siguientes funciones
opuesta :: Num a => Serie a -> Serie a suma :: Num a => Serie a -> Serie a -> Serie a resta :: Num a => Serie a -> Serie a -> Serie a producto :: Num a => Serie a -> Serie a -> Serie a cociente :: Fractional a => Serie a -> Serie a -> Serie a derivada :: (Num a, Enum a) => Serie a -> Serie a integral :: (Fractional a, Enum a) => Serie a -> Serie a expx :: Serie Rational
tales que
λ> take 7 (opuesta [-6,-4..]) [6,4,2,0,-2,-4,-6]
λ> take 7 (suma [1,3..] [2,4..]) [3,7,11,15,19,23,27]
λ> take 7 (resta [3,5..] [2,4..]) [1,1,1,1,1,1,1] λ> take 7 (resta ([3,7,11,15,19,23,27] ++ repeat 0) [1,3..]) [2,4,6,8,10,12,14]
λ> take 7 (producto [3,5..] [2,4..]) [6,22,52,100,170,266,392]
λ> take 7 (cociente ([6,22,52,100,170,266,392] ++ repeat 0) [3,5..]) [2.0,4.0,6.0,8.0,10.0,12.0,14.0]
λ> take 7 (derivada [2,4..]) [4,12,24,40,60,84,112]
λ> take 7 (integral ([4,12,24,40,60,84,112] ++ repeat 0)) [0.0,4.0,6.0,8.0,10.0,12.0,14.0]
λ> take 8 expx [1 % 1,1 % 1,1 % 2,1 % 6,1 % 24,1 % 120,1 % 720,1 % 5040] λ> take 8 (derivada expx) [1 % 1,1 % 1,1 % 2,1 % 6,1 % 24,1 % 120,1 % 720,1 % 5040] λ> take 8 (integral expx) [0 % 1,1 % 1,1 % 2,1 % 6,1 % 24,1 % 120,1 % 720,1 % 5040]
Un número con n dígitos es pandigital si contiene todos los dígitos del 1 a n exactamente una vez. Por ejemplo, 2143 es un pandigital con 4 dígitos y, además, es primo.
Definir la constante
pandigitalesPrimos :: [Int]
tal que sus elementos son los números pandigitales, ordenados de mayor a menor. Por ejemplo,
take 3 pandigitalesPrimos == [7652413,7642513,7641253] 2143 `elem` pandigitalesPrimos == True length pandigitalesPrimos == 538
Definir la función
nMinimoCambios :: Ord a => [a] -> Int
tal que (nMinimoCambios xs) es el menor número de elementos de xs que hay que cambiar para que todos sean iguales. Por ejemplo,
nMinimoCambios [3,5,3,7,9,6] == 4 nMinimoCambios [3,5,3,7,3,3] == 2 nMinimoCambios "Salamanca" == 5 nMinimoCambios (4 : [1..500000]) == 499999
En el primer ejemplo, los elementos que hay que cambiar son 5, 7, 9 y 6.
Sea \(\{b_i \mid i \geq 1\}\) una sucesión infinita de números enteros mayores que 1. Entonces, todo entero \(x\) mayor que cero se puede escribir de forma única como \[ x = x_0 + x_1 b_1 + x_2 b_1 b_2 + \dots + x_n b_1 b_2 \dotsm b_n, \] donde cada \(x_i\) satisface la condición \(0 \leq x_i < b_{i+1}\). Se dice que \([x_n, x_{n-1}, \dots, x_2, x_1, x_0]\) es la representación de \(x\) en la base \((b_i).
Por ejemplo, la representación de 377 en la base \((2i)_{i \geq 1}\) es \([7,5,0,1]\), ya que \[ 377 = 1 + 0 \times 2 + 5 \times 2 \times 4 + 7 \times 2 \times 4 \times 6, \] y además: \[ 0 \leq 1 < 2, \quad 0 \leq 0 < 4, \quad 0 \leq 5 < 6, \quad 0 \leq 7 < 8. \]
Definir las funciones
decimalAmultiple :: [Int] -> Int -> [Int] multipleAdecimal :: [Int] -> [Int] -> Int
tales que (decimalAmultiple bs x) es la representación del número x en la base bs y (multipleAdecimal bs cs) es el número decimal cuya representación en la base bs es cs. Por ejemplo,
decimalAmultiple [2,4..] 377 == [7,5,0,1] multipleAdecimal [2,4..] [7,5,0,1] == 377 decimalAmultiple [2,5..] 377 == [4,5,3,1] multipleAdecimal [2,5..] [4,5,3,1] == 377 decimalAmultiple [2^n | n <- [1..]] 2015 == [1,15,3,3,1] multipleAdecimal [2^n | n <- [1..]] [1,15,3,3,1] == 2015 decimalAmultiple (repeat 10) 2015 == [2,0,1,5] multipleAdecimal (repeat 10) [2,0,1,5] == 2015
Comprobar con QuickCheck que se verifican las siguientes propiedades
prop_inversas :: [Int] -> Int -> Property prop_inversas bs x = x > 0 ==> multipleAdecimal bs (decimalAmultiple bs x) == x prop_coeficientes :: [Int] -> Int -> Property prop_coeficientes bs x = x > 0 ==> and [0 <= c && c < b | (c,b) <- zip cs bs] where cs = reverse (decimalAmultiple bs x)
para distintas bases dadas. Por ejemplo,
λ> quickCheck (prop_inversas [2,4..]) +++ OK, passed 100 tests. λ> quickCheck (prop_inversas [3,5..]) +++ OK, passed 100 tests. λ> quickCheck (prop_coeficientes [2,4..]) +++ OK, passed 100 tests. λ> quickCheck (prop_coeficientes [3,5..]) +++ OK, passed 100 tests.
Definir la función
productos :: Integer -> Integer -> [[Integer]]
tal que (productos n x) es las listas de n elementos consecutivos cuyo producto es x. Por ejemplo,
productos 2 6 == [[2,3]] productos 3 6 == [[1,2,3]] productos 4 1680 == [[5,6,7,8]] productos 2 5 == []
Comprobar con QuickCheck que si n > 0 y x > 0, entonces
productos n (product [x..x+n-1]) == [[x..x+n-1]]
Usando productos, definir la función
productosDe2y3consecutivos :: [Integer]
cuyos elementos son los números naturales (no nulos) que pueden expresarse simultáneamente como producto de dos y tres números consecutivos. Por ejemplo,
head productosDe2y3consecutivos == 6
Nota. Según demostró Mordell en 1962, productosDe2y3consecutivos sólo tiene dos elementos.
Los horarios de los cursos se pueden representar mediante matrices donde las filas indican los curso, las columnas las horas de clase y el valor correspondiente al curso i y la hora j es verdadero indica que i tiene clase a la hora j.
En Haskell, podemos usar la matrices de la librería Data.Matrix y definir el tipo de los horarios por
type Horario = Matrix Bool
Un ejemplo de horario es
ejHorarios1 :: Horario ejHorarios1 = fromLists [[True, True, False, False], [False, True, True, False], [False, False, True, True]]
en el que el 1º curso tiene clase a la 1ª y 2ª hora, el 2º a la 2ª y a la 3ª y el 3º a la 3ª y a la 4ª.
Definir la función
cursosConflictivos :: Horario -> [Int] -> Bool
tal que (cursosConflictivos h is) se verifica para si los cursos de la lista is hay alguna hora en la que más de uno tiene clase a dicha hora. Por ejemplo,
cursosConflictivos ejHorarios1 [1,2] == True cursosConflictivos ejHorarios1 [1,3] == False
En 1772, Euler publicó que el polinomio n² + n + 41 genera 40 números primos para todos los valores de n entre 0 y 39. Sin embargo, cuando n=40, 40²+40+41 = 40(40+1)+41 es divisible por 41.
Usando ordenadores, se descubrió el polinomio n² - 79n + 1601 que genera 80 números primos para todos los valores de n entre 0 y 79.
Definir la función
generadoresMaximales :: Integer -> (Int,[(Integer,Integer)])
tal que (generadoresMaximales n) es el par (m,xs) donde
Por ejemplo,
generadoresMaximales 4 == ( 3,[(-2,3),(-1,3),(3,3)]) generadoresMaximales 6 == ( 5,[(-1,5),(5,5)]) generadoresMaximales 50 == (43,[(-5,47)]) generadoresMaximales 100 == (48,[(-15,97)]) generadoresMaximales 200 == (53,[(-25,197)]) generadoresMaximales 1650 == (80,[(-79,1601)])