Relación 6 Sol

-- I1M 2021-22:
-- Funciones de orden superior y definiciones por plegados (II)
-- Departamento de Ciencias de la Computación e Inteligencia Artificial
-- Universidad de Sevilla
-- ============================================================================

-- ============================================================================
-- Librerías auxiliares
-- ============================================================================

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

-- ----------------------------------------------------------------------------
-- Ejercicio 1. Se considera la función
--      resultadoPos :: (a -> Integer) -> [a] -> [a]
-- tal que (resultadoPos f xs) es la lista de los elementos de la lista
-- xs tales que el valor de la función f sobre ellos es positivo. Por ejemplo,
--   resultadoPos head [[-1,2],[-9,4],[2,3]]       ==  [[2,3]]
--   resultadoPos sum [[1,2],[9],[-8,3],[],[3,5]]  ==  [[1,2],[9],[3,5]]
--
-- Define esta función
-- 1) por comprensión,
-- 2) por orden superior,
-- 3) por recursión,
-- 4) por plegado.
-- -----------------------------------------------------------------------------

-- Álvaro Galisteo: 

-- 1) por comprensión,
resultadoPosC :: (a -> Integer) -> [a] -> [a]
resultadoPosC f xs = [ ns | ns <- xs, f ns > 0]

-- 2) por orden superior,
resultadoPosOS :: (a -> Integer) -> [a] -> [a]
resultadoPosOS f xs = filter (\ x -> f x > 0) xs

-- 3) por recursión,
resultadoPosR :: (a -> Integer) -> [a] -> [a]
resultadoPosR _ [] = []
resultadoPosR f (x:xs) = if f x > 0 then x:resultadoPosR f xs
                            else resultadoPosR f xs 

-- 4) por plegado.
resultadoPosP :: (a -> Integer) -> [a] -> [a]
resultadoPosP f xs = foldr (\ x y -> if f x > 0 then (x:y) else y ) [] xs

-- ----------------------------------------------------------------------------
-- Ejercicio 2. Se considera la función
--     intercala :: Int -> [Int] -> [Int]
-- tal que (intercala y xs) es la lista que resulta de intercalar el elemento
-- y delante de todos los elementos de la lista xs que sean menores que y.
-- Por ejemplo,
--   intercala 5 [1,2,6,3,7,9]  ==  [5,1,5,2,6,5,3,7,9]
--   intercala 5 [6,7,9,8]      ==  [6,7,9,8]
--
-- Define esta función
-- 1) por comprensión,
-- 2) por orden superior,
-- 3) por recursión,
-- 4) por plegado.
-- ----------------------------------------------------------------------------

-- Álvaro Galisteo: 

-- 1) por comprensión,
intercalaC :: Int -> [Int] -> [Int]
intercalaC n xs = concat [if x < n then [n,x] else [x] | x <- xs]

-- 2) por orden superior,
intercalaOS :: Int -> [Int] -> [Int]
intercalaOS n xs = concat (map (\ x -> if x<n then [n,x] else [x]) xs)

-- 3) por recursión,
intercalaR :: Int -> [Int] -> [Int]
intercalaR _ [] = []
intercalaR n (x:xs) = if x<n then [n,x]++intercalaR n xs
                             else [x]++intercalaR n xs 


-- 4) por plegado.
intercalaP :: Int -> [Int] -> [Int]
intercalaP n xs = foldl (\ x y -> if y < n then x++[n,y] else x++[y]) [] xs

-- ----------------------------------------------------------------------------
-- Ejercicio 3. Se considera la función
--    dec2ent :: [Integer] -> Integer
-- tal que (dec2ent xs) es el número entero cuyas cifras ordenadas son los
-- elementos de la lista xs. Por ejemplo,
--   dec2ent [2,3,4,5]  ==  2345
--   dec2ent [1..9]     ==  123456789
--
-- Defie esta función
-- 1) por comprensión,
-- 2) por orden superior,
-- 3) por recursión,
-- 4) por plegado.
-- ----------------------------------------------------------------------------

-- Álvaro Galisteo: 

-- 1) por comprensión,
dec2entC :: [Integer] -> Integer
dec2entC xs = sum [x*10^y | (x,y) <- zip xs (reverse [0..(length xs - 1)])]

-- 2) por orden superior,
dec2entOS :: [Integer] -> Integer
dec2entOS xs = read (concat (map show xs)) :: Integer

-- 3) por recursión,
dec2entR :: [Integer] -> Integer
dec2entR xs = dec2entR' xs (length xs - 1)

dec2entR' :: [Integer] -> Int -> Integer
dec2entR' [] _ = 0 
dec2entR' (x:xs) n = x*10^n + dec2entR' xs (n-1)

-- 4) por plegado.
dec2entP :: [Integer] -> Integer
dec2entP xs = foldl (\ x y -> x*10 + y) 0 xs 

-- ----------------------------------------------------------------------------
-- Ejercicio 4. Se considera la función
--     diferencia :: Eq a => [a] -> [a] -> [a]
-- tal que (diferencia xs ys) es la diferencia entre los conjuntos xs e
-- ys; es decir, el conjunto de los elementos de la lista xs que no se
-- encuentran en la lista ys. Por ejemplo,
--   diferencia [2,3,5,6] [5,2,7]  ==  [3,6]
--   diferencia [1,3,5,7] [2,4,6]  ==  [1,3,5,7]
--   diferencia [1,3] [1..9]       ==  []
--
-- Define esta función
-- 1) por comprensión,
-- 2) por orden superior,
-- 3) por recursión,
-- 4) por plegado.
-- ----------------------------------------------------------------------------

-- Álvaro Galisteo: 

-- 1) por comprensión,
diferenciaC :: Eq a => [a] -> [a] -> [a]
diferenciaC xs ys = [x | x <- xs, notElem x ys]

-- 2) por orden superior,
diferenciaOS :: Eq a => [a] -> [a] -> [a]
diferenciaOS xs ys = filter (\ x -> notElem x ys) xs

-- 3) por recursión,
diferenciaR :: Eq a => [a] -> [a] -> [a]
diferenciaR [] ys = []
diferenciaR (x:xs) ys = if notElem x ys then x:diferenciaR xs ys
                             else diferenciaR xs ys 

-- 4) por plegado.
diferenciaP :: Eq a => [a] -> [a] -> [a]
diferenciaP xs ys = foldr (\ x y -> if notElem x ys then x:y else y) [] xs

-- ----------------------------------------------------------------------------
-- Ejercicio 5. Se considera la función
--   primerosYultimos :: [[a]] -> ([a],[a])
-- tal que (primerosYultimos xss) es el par formado por la lista de los
-- primeros elementos de las listas no vacías de xss y la lista de los
-- últimos elementos de las listas no vacías de xss. Por ejemplo,
--   primerosYultimos [[1,2],[5,3,4],[],[9]]  ==  ([1,5,9],[2,4,9])
--   primerosYultimos [[1,2],[1,2,3],[1..4]]  ==  ([1,1,1],[2,3,4])

--
-- Define esta función
-- 1) por comprensión,
-- 2) por orden superior,
-- 3) por recursión,
-- 4) por plegado.
-- ----------------------------------------------------------------------------

-- Álvaro Galisteo: 

-- 1) por comprensión,
primerosYultimosC :: [[a]] -> ([a],[a])
primerosYultimosC xss = ([head xs | xs <- xss, not (null xs)], [last xs | xs <- xss, not (null xs)])

-- 2) por orden superior,
primerosYultimosOS :: [[a]] -> ([a],[a])
primerosYultimosOS xss = (map head (filter (not . null) xss), map last (filter (not . null) xss))

-- 3) por recursión,
primerosYultimosR :: [[a]] -> ([a],[a])
primerosYultimosR xss = (primeros xss, ultimos xss)

primeros, ultimos :: [[a]] -> [a]

primeros [] = []
primeros (xs:xss) = if null xs then primeros xss else [head xs] ++ primeros xss

ultimos [] = []
ultimos (xs:xss) = if null xs then ultimos xss else [last xs] ++ ultimos xss

-- 4) por plegado.
primerosYultimosP :: [[a]] -> ([a],[a])
primerosYultimosP xss = (foldl (\ xs ys -> if not (null ys)  then xs ++ [head ys] else xs) [] xss,
                         foldl (\ xs ys -> if not (null ys) then xs ++ [last ys] else xs) [] xss)

-- ----------------------------------------------------------------------------
-- Ejercicio 6. Una lista hermanada es una lista de números estrictamente
-- positivos en la que cada elemento tiene algún factor primo en común con el
-- siguiente, en caso de que exista, o alguno de los dos es un 1. Por ejemplo,
-- [2,6,3,9,1,5] es una lista hermanada.

-- Se considera la función
--    hermanada :: [Int] -> Bool
-- tal que (hermanada xs) comprueba que la lista xs es hermanada según la
-- definición anterior. Por ejemplo,
--    hermanada [2,6,3,9,1,5]  ==  True
--    hermanada [2,3,5]        ==  False
--
-- Se pide definir esta función
-- 1) por comprensión,
-- 2) por orden superior,
-- 3) por recursión,
-- 4) por plegado.
-- ----------------------------------------------------------------------------
-- Nota: Usa la función 'gcd'
-- ----------------------------------------------------------------------------

-- Álvaro Galisteo: 

-- 1) por comprensión,
hermanadaC :: [Int] -> Bool
hermanadaC xs = and [gcd x y > 1 | (x,y) <- zip xs (tail xs), x /= 1, y /= 1] 

-- 2) por orden superior,
hermanadaOS :: [Int] -> Bool
hermanadaOS xs = and (map (\ (x,y) -> if x == 1 || y == 1 then True else gcd x y > 1) (zip xs (tail xs)))

-- 3) por recursión,
hermanadaR :: [Int] -> Bool
hermanadaR [_] = True
hermanadaR (x:y:xs) =  if x == 1 || y == 1 then True  && hermanadaR (y:xs) else gcd x y > 1 && hermanadaR (y:xs) 

-- 4) por plegado.
hermanadaP :: [Int] -> Bool
hermanadaP xs = foldr (\ (x,y) l -> (x == 1 || y == 1 || gcd x y > 1) && l) True (zip xs (tail xs))


-- ----------------------------------------------------------------------------
-- Ejercicio 7. Un elemento de una lista es permanente si ninguno de los que
-- vienen a continuación en la lista es mayor que él. Consideramos la función
--   permanentes :: [Int] -> [Int]
-- tal que (permanentes xs) es la lista de los elementos permanentes de la
-- lista xs. Por ejemplo,
--   permanentes [80,1,7,8,4]  ==  [80,8,4]

-- Se pide definir esta función
-- 1) por comprensión,
-- 2) por orden superior,
-- 3) por recursión,
-- 4) por plegado.
-- ---------------------------------------------------------------------------
-- Nota: Usa la función 'tails' de Data.List.
-- ----------------------------------------------------------------------------

-- Álvaro Galisteo: 

-- 1) por comprensión,
permanentesC :: [Int] -> [Int]
permanentesC xs = [x | (x,y) <- zip xs (tails xs), x == maximum y]

-- 2) por orden superior,
permanentesOS :: [Int] -> [Int]
permanentesOS xs = concat (map (\ (x,y) -> if x == maximum y then [x] else []) (zip xs (tails xs))) 

-- 3) por recursión,
permanentesR :: [Int] -> [Int]
permanentesR [x] = [x]
permanentesR (x:xs) = if all (<x) xs then x:permanentesR xs else permanentesR xs

-- 4) por plegado.
permanentesP :: [Int] -> [Int]
permanentesP xs = foldr (\ x y -> if all (<x) y then x:y else y) [] xs

               
-- ---------------------------------------------------------------------
-- Ejercicio 8. Un número entero positivo n es muy primo si es n primo
-- y todos los números que resultan de ir suprimimiendo la última cifra
-- también son primos. Por ejemplo, 7193 es muy primo pues los números
-- 7193, 719, 71 y 7 son todos primos. 
-- 
-- Define la función 
--    muyPrimo :: Integer -> Bool
-- que (muyPrimo n) se verifica si n es muy primo. Por ejemplo,
--    muyPrimo 7193  == True
--    muyPrimo 71932 == False
-- --------------------------------------------------------------------

-- Álvaro Galisteo: 

primo :: Int -> Bool
primo 1 = False 
primo x = and [gcd n x == 1| n <- [2..(x-1)]]

muyPrimo :: Int -> Bool
muyPrimo x = and [primo n | n <- listaNumero x]

listaNumero :: Int -> [Int]
listaNumero x | x < 10 = [x]
              | otherwise = x:listaNumero (div x 10) 

-- ---------------------------------------------------------------------
-- ¿Cuántos números de cinco cifras son muy primos?
-- ---------------------------------------------------------------------

-- Álvaro Galisteo: 

-- El cálculo es

muyPrimosDeCincoCifras :: Int
muyPrimosDeCincoCifras = sum [1 | x <- [10000..99999], primo (div x 10000) && primo (div x 1000) && primo (div x 100)&& primo (div x 10) && primo x]

-- *Main> muyPrimosDeCincoCifras
-- 15


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