Una relación binaria R sobre un conjunto A es transitiva cuando se cumple que siempre que un elemento se relaciona con otro y éste último con un tercero, entonces el primero se relaciona con el
Definir la función
transitiva :: Eq a => [(a,a)] -> Bool
tal que (transitiva r) se verifica si la relación r es transitiva. Por ejemplo,
transitiva [(1,1),(1,3),(3,1),(3,3),(5,5)] == True transitiva [(1,1),(1,3),(3,1),(5,5)] == False
Las relaciones binarias en un conjunto A se pueden representar mediante conjuntos de pares de elementos de A. Por ejemplo, la relación de divisibilidad en el conjunto {1,2,3,6} se representa por
[(1,1),(1,2),(1,3),(1,6),(2,2),(2,6),(3,3),(3,6),(6,6)]
La composición de dos relaciones binarias R y S en el conjunto A es la relación binaria formada por los pares (x,y) para los que existe un z tal que (x,z) ∈ R y (z,y) ∈ S.
Definir la función
composicion :: Eq a => [(a,a)] -> [(a,a)] -> [(a,a)]
tal que (composicion r s) es la composición de las relaciones binarias r y s. Por ejemplo,
λ> composicion [(1,2)] [(2,3),(2,4)] [(1,3),(1,4)] λ> composicion [(1,2),(5,2)] [(2,3),(2,4)] [(1,3),(1,4),(5,3),(5,4)] λ> composicion [(1,2),(1,4),(1,5)] [(2,3),(4,3)] [(1,3)] λ> composicion [(0,1)] [(2,3)] []
Nota: Se supone que las relaciones binarias son listas sin elementos repetidos.
Un número de Smith es un número natural compuesto que cumple que la suma de sus dígitos es igual a la suma de los dígitos de todos sus factores primos (si tenemos algún factor primo repetido lo sumamos tantas veces como aparezca). Por ejemplo, el 22 es un número de Smith ya que
22 = 2*11 y 2+2 = 2+(1+1)
y el 4937775 también lo es ya que
4937775 = 3*5*5*65837 y 4+9+3+7+7+7+5 = 3+5+5+(6+5+8+3+7)
Definir las funciones
esSmith :: Integer -> Bool smith :: [Integer]
tales que
esSmith 22 == True esSmith 29 == False esSmith 2015 == False esSmith 4937775 == True esSmith 4567597056 == True
λ> take 17 smith [4,22,27,58,85,94,121,166,202,265,274,319,346,355,378,382,391] λ> smith !! 2000 62158
Un número de n dígitos es un número de Armstrong si es igual a la suma de las n-ésimas potencias de sus dígitos. Por ejemplo, 371, 8208 y 4210818 son números de Armstrong ya que
371 = 3^3 + 7^3 + 1^3 8208 = 8^4 + 2^4 + 0^4 + 8^4 4210818 = 4^7 + 2^7 + 1^7 + 0^7 + 8^7 + 1^7 + 8^7
Definir las funciones
esArmstrong :: Integer -> Bool armstrong :: [Integer]
tales que
esArmstrong 371 == True esArmstrong 8208 == True esArmstrong 4210818 == True esArmstrong 2015 == False esArmstrong 115132219018763992565095597973971522401 == True esArmstrong 115132219018763992565095597973971522402 == False
λ> take 18 armstrong [1,2,3,4,5,6,7,8,9,153,370,371,407,1634,8208,9474,54748,92727]
Comprobar con QuickCheck que los números mayores que 115132219018763992565095597973971522401 no son números de Armstrong.
Definir la sucesión
raicesEnterasDePrimos :: [Integer]
cuyos elementos son las partes enteras de las raíces cuadradas de los números primos. Por ejemplo,
λ> take 30 raicesEnterasDePrimos [1,1,2,2,3,3,4,4,4,5,5,6,6,6,6,7,7,7,8,8,8,8,9,9,9,10,10,10,10,10] λ> raicesEnterasDePrimos !! 9963 322 λ> raicesEnterasDePrimos !! 9964 323
Comprobar con QuickCheck que la diferencia entre dos términos consecutivos de la sucesión es como máximo igual a 1.
Los árboles binarios con valores en las hojas y en los nodos se definen por
data Arbol a = H a | N a (Arbol a) (Arbol a) deriving Show
Por ejemplo, el árbol
5
/ \
/ \
9 7
/ \ / \
1 4 6 8
se puede representar por
N 5 (N 9 (H 1) (H 4)) (N 7 (H 6) (H 8))
Decimos que un árbol binario es par si la mayoría de sus nodos son pares e impar en caso contrario.
Para representar la paridad se define el tipo Paridad
data Paridad = Par | Impar deriving (Eq, Show)
Definir la función
paridad :: Arbol3 Int -> Paridad
tal que (paridad a) es la paridad del árbol a. Por ejemplo,
paridad (N 8 (N 6 (H 3) (H 4)) (H 5)) == Par paridad (N 8 (N 9 (H 3) (H 4)) (H 5)) == Impar
Definir las funciones
separacion :: [a] -> ([a],[a]) mezcla :: ([a],[a]) -> [a]
tales que (separacion xs) es el par formado eligiendo alternativamente elementos de xs mientras que mezcla intercala los elementos de las dos listas. Por ejemplo,
separacion [1..5] == ([1,3,5],[2,4]) mezcla ([1,3,5],[2,4]) == [1,2,3,4,5] separacion "Telescopio" == ("Tlsoi","eecpo") mezcla ("Tlsoi","eecpo") == "Telescopio" take 5 (fst (separacion [2,4..])) == [2,6,10,14,18] take 6 (mezcla ([2,4..],[7,14..])) == [2,7,4,14,6,21]
Comprobar con QuickCheck que
mezcla (separacion xs) == xs
Definir la función
particiones :: [a] -> Int -> [[[a]]]
tal que (particiones xs k) es la lista de las particiones de xs en k subconjuntos disjuntos. Por ejemplo,
λ> particiones [2,3,6] 2 [[[2],[3,6]],[[2,3],[6]],[[3],[2,6]]] λ> particiones [2,3,6] 3 [[[2],[3],[6]]] λ> particiones [4,2,3,6] 3 [[[4],[2],[3,6]],[[4],[2,3],[6]],[[4],[3],[2,6]], [[4,2],[3],[6]],[[2],[4,3],[6]],[[2],[3],[4,6]]] λ> particiones [4,2,3,6] 1 [[[4,2,3,6]]] λ> particiones [4,2,3,6] 4 [[[4],[2],[3],[6]]]
Definir la función
transformada :: [a] -> [a]
tal que (transformada xs) es la lista obtenida repitiendo cada elemento tantas veces como indica su posición en la lista. Por ejemplo,
transformada [7,2,5] == [7,2,2,5,5,5] transformada "eco" == "eccooo"
Comprobar con QuickCheck si la transformada de una lista de n números enteros, con n >= 2, tiene menos de n^3 elementos.
Un número semiprimo es un número natural que es producto de dos números primos no necesariamente distintos. Por ejemplo, 26 es semiprimo (porque ' 26 = 2*13' ) y 49 también lo es (porque 49 = 7*7).
Definir la función
mayorSemiprimoMenor :: Integer -> Integer
tal que (mayorSemiprimoMenor n) es el mayor semiprimo menor que n (suponiendo que n > 4). Por ejemplo,
mayorSemiprimoMenor 27 == 26 mayorSemiprimoMenor 50 == 49 mayorSemiprimoMenor 49 == 46 mayorSemiprimoMenor (10^6) == 999997