Tema 2 - Examples/Ejercicios

2. Define una función
            máximoYresto :: Ord a => [a] -> (a,[a])
que “devuelva” en forma de par el máximo de la lista y los restantes elementos. Considera dos casos:
      a.- el orden en que aparecen los restantes puede ser arbitrario:
             máximoYresto [1,2,30,4,5,6,7]   (30,[1,2,7,4,5,6])
      b.- los restantes deben aparecer en el orden original
             máximoYresto’ [1,2,30,4,5,6,7]  (30,[1,2,4,5,6,7])


maximoYresto :: Ord a => [a] -> (a,[a])
maximoYresto [] = (null,[])
maximoYresto (x:xs) = if(x>=head xs) then maximoYresto (x:tail xs)
                        else maximoYresto xs

8. Un número natural p es primo si tiene exactamente dos divisores positivos distintos: 1 y p; por
tanto, 1 no es un número primo.
        a) Define una función esPrimo para comprobar si un número es primo. Por ejemplo:
               esPrimo 7  True esPrimo 10  False
        b) Usando una lista por comprensión, define una función primosHasta que devuelva una lista
            con todos los números primos menores o iguales a un valor dado. Por ejemplo:
               primosHasta 50  [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]
         c) Da otra definición (con nombre primosHasta') que use la función predefinida filter en vez
          de la lista por comprensión.
        d) Comprueba que las dos funciones que has definido se comportan del mismo modo
         comprobando con QuickCheck la siguiente propiedad:
                p1_primos x = primosHasta x == primosHasta' x
        Nota: existen métodos más eficientes para calcular listas de primos( Criba de  Eratóstenes.)



divisoresDe :: Integer -> [Integer]
divisoresDe n | n > 0       = [d | d <- [1..n], n `mod` d == 0]
              | otherwise   = error "no existen"
           

esPrimo :: Integer -> Bool
esPrimo  x = length (divisoresDe x) ==2

-- B) Define una lista por compresión
primosHasta :: Integer -> [Integer]
primosHasta  m  = [x | x<-[1..m],esPrimo (x)]

-- C) Misma función usando filter
primosHasta':: Integer -> [Integer]
primosHasta'  m = filter esPrimo [1..m]
-- D) quickCheck
p1_primos x = primosHasta x == primosHasta' x


14. La función predefinida
             takeWhile :: (a -> Bool) -> [a] -> [a]
devuelve el prefijo más largo con los elementos de una lista (2º argumento) que cumplen una
condición (1er argumento). Por ejemplo:
             takeWhile even [2,4,6,8,11,13,16,20]  [2,4,6,8]
ya que el 11 es el primer elemento que no es par. Otro ejemplo de uso es:
            takeWhile (<5) [2,4,6,1]  [2,4]
ya que 6 es el primer elemento de la lista mayor o igual a 5. Para los mismos argumentos, la función
dropWhile suprime el prefijo que takeWhile devuelve. Por ejemplo:
           dropWhile even [2,4,6,8,11,13,16,20]  [11,13,16,20]
           dropWhile (<5) [2,4,6,1]  [6,1]
a) Usando estas funciones, define una función inserta que tome un elemento x y una lista xs que ya
está ordenada ascendentemente (asume que esta precondición se cumple), y que devuelva la lista
ordenada que se obtiene al insertar x en su posición adecuada dentro de xs. Por ejemplo:
             inserta 5 [1,2,4,7,8,11 ]  [1,2,4,5,7,8,11]
             inserta 2 [1,2,4,7,8,11]  [1,2,2,4,7,8,11]
             inserta 0 [1,2,4,7,8,11]  [0,1,2,4,7,8,11]
             inserta 20 [1,2,4,7,8,11]  [1,2,4,7,8,11,20]
b) Sin usar ninguna función auxiliar, define directamente y en forma recursiva la función inserta.
c) Lee, entiende y comprueba con QuickCheck la siguiente propiedad referente a la función inserta:
             p1_inserta x xs = desconocida xs ==> desconocida (inserta x xs)
d) Podemos utilizar la función inserta que hemos definido para ordenar ascendentemente una lista
desordenada. Por ejemplo, si quisiéramos ordenar la lista [9,3,7], podríamos hacerlo evaluando
la expresión:
            9 `inserta` (3 `inserta` (7 `inserta` []))
Razona por qué funciona este algoritmo para ordenar una lista.
e) Usando la función foldr y la función inserta, define una función ordena que tome una lista de
valores y la devuelva ordenada. Por ejemplo:
            ordena [9,3,7]  [3,7,9] ordena "abracadabra" "aaaaabbcdrr"
f) Escribe y comprueba con QuickCheck la siguiente propiedad: para cualquier lista xs, ordena xs es
una lista ordenada.
g) Demuestra la propiedad anterior por inducción sobre listas.



desconocida :: (Ord a) => [a] -> Bool
desconocida xs = and [ x<=y | (x,y) <- zip xs (tail xs) ]

-- A)
inserta :: Ord a => a -> [a] -> [a]
inserta x xs = (takeWhile (<x) (xs)) ++ [x] ++ (dropWhile (<=x) (xs))

-- B) inserta directamente  y versión recursiva
inserta' :: Ord a => a -> [a] -> [a]
inserta' x [ ]  = [x]
inserta' x (y:ys) = [y] ++ inserta x (ys)

-- C)
p_inserta x xs = length xs <= 10 && desconocida xs ==> desconocida (inserta x xs)
p_inserta' x xs = length xs <= 10 &&  desconocida xs ==> desconocida (inserta' x xs)
pinserta = quickCheck  (p_inserta :: Int -> [Int] -> Property)
pinserta' = quickCheck (p_inserta' :: Int -> [Int] -> Property)

-- D) ¿por qué está ordenada la lista 9 `inserta` (3 `inserta` (7 `inserta` []))

-- E) algoritmo de ordenación a través de foldr e inserta
ordena :: Ord a => [a] -> [a]
ordena xs = foldr inserta [] xs

16. Aunque la función predefinida lcm (least common multiple) ya lo hace, el objetivo de este ejercicio es escribir una función mcm para calcular el mínimo común múltiplo de dos naturales.
       a) Define una función múltiplosDe, que tome como parámetro un número mayor que cero y
          devuelva una lista infinita con sus múltiplos positivos. Por ejemplo:
                múltiplosDe 3  [3,6,9,12,15,...
       Ayuda: usa la función predefinida iterate, descrita en un ejercicio anterior.
       b) Define la función sobrecargada para tipos con orden
               primeroComún :: Ord a => [a] -> [a] -> a
       que tome dos listas ordenadas ascendentemente y devuelva el menor elemento común a ambas.
       Por ejemplo:
               primeroComún [1,2,5,7,9] [3,3,4,5,7]  5
        c) El mínimo común múltiplo de dos naturales x e y es el menor natural positivo múltiplo de
        ambos. Utilizando las funciones definidas en los apartados previos, escribe una función mcm
        que calcule el mínimo común múltiplo de dos naturales usando esta definición.
        d) Comprueba usando QuickCheck tu definición mediante esta propiedad:
               p_mcm x y = x>=0 && y>=0 ==> mcm x y == lcm x y

-- A)
múltiplosDe :: Integer -> [Integer]
múltiplosDe x = map (*x) [1,2..]

-- B)
primeroComún :: Ord a => [a] -> [a] -> a
primeroComún              (x:xs) (y:ys)
  | x > y    = primeroComún (x:xs)    ys
  | x< y     = primeroComún (xs)    (y:ys)
  |otherwise = x

-- C)
 mcm de dos naturales como menor mútiplo común positivo
mcm x y = primeroComún (múltiplosDe x) (múltiplosDe y)
-- D)
p_mcm x y = x>=0 && y>=0 ==> mcm x y == lcm x y