Relación 27

-- I1M 2021-22: Relación 27
-- El TAD de los polinomios
-- Departamento de Ciencias de la Computación e Inteligencia Artificial
-- Universidad de Sevilla
-- ============================================================================

-- ============================================================================
-- Introducción
-- ============================================================================

-- El objetivo de esta relación es definir operaciones sobre polinomios
-- utilizando las implementaciones del TAD de polinomio. Para realizar los
-- ejercicios hay que descargar, en el mismo directorio que el enunciado, el
-- código de los TAD
--   PolinomioConTipoDeDatoAlgebraico.hs
--   PolinomioConListaDensa.hs
--   PolinomioConListaDispersa.hs
--
-- El objetivo es hacer los ejercicios con una implementación y comprobar que
-- las definiciones también son válidas con las otras.
--
-- Además, en algunos ejemplos se usan polinomios con coeficientes racionales.
-- En Haskell, el número racional x/y se representa por x%y. El TAD de los
-- números racionales está definido en el módulo Data.Ratio.

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

import Data.Ratio
import Test.QuickCheck

-- Hay que elegir una implementación del TAD polinomios.
import PolinomioConTipoDeDatoAlgebraico
-- import PolinomioConListaDensa
-- import PolinomioConListaDispersa

-- ----------------------------------------------------------------------------
-- Ejercicio 1. Definir la función
--   creaPolDensa :: (Num a, Eq a) => [(Int,a)] -> Polinomio a
-- tal que '(creaPolDensa xs)' es el polinomio cuya representación densa
-- es la lista de pares 'xs'. Por ejemplo,
--   creaPolDensa [(5,7),(2,4),(0,3)]  =>  7*x^5 + 4*x^2 + 3
-- ----------------------------------------------------------------------------

--Daniel Cebrián Castillo
creaPolDensa :: (Num a, Eq a) => [(Int,a)] -> Polinomio a
creaPolDensa [] = polCero
creaPolDensa xs = consPol (fst (head xs)) (snd (head xs)) (creaPolDensa (tail xs))


-- Álvaro Galisteo: 

creaPolDensa :: (Num a, Eq a) => [(Int,a)] -> Polinomio a
creaPolDensa [] = polCero
creaPolDensa (x:xs) = consPol (fst x) (snd x) (creaPolDensa XS)


-- ----------------------------------------------------------------------------
-- Ejercicio 2. Definir la función
--   creaPolDispersa :: (Num a, Eq a) => [a] -> Polinomio a
-- tal que '(creaPolDispersa xs)' es el polinomio cuya representación dispersa
-- es la lista 'xs'. Por ejemplo,
--   creaPolDispersa [7,0,0,4,0,3]  =>  7*x^5 + 4*x^2 + 3
-- ----------------------------------------------------------------------------

--Daniel Cebrián Castillo
creaPolDispersa :: (Num a, Eq a) => [a] -> Polinomio a
creaPolDispersa [] = polCero
creaPolDispersa xs = consPol (length xs -1) (xs!!0) (creaPolDispersa(tail xs))


-- Álvaro Galisteo:

creaPolDispersa :: (Num a, Eq a) => [a] -> Polinomio a
creaPolDispersa [] = polCero
creaPolDispersa (x:xs) = consPol (length xs) x (creaPolDispersa xs)


-- ----------------------------------------------------------------------------
-- Ejercicio 3. Definir la función
--   densa :: (Num a, Eq a) => Polinomio a -> [(Int,a)]
-- tal que '(densa p)' es la representación densa del polinomio 'p'. Por
-- ejemplo,
--   densa (creaPolDispersa [1,0,0,5,4,0])  ==  [(5,1),(2,5),(1,4)]
-- ----------------------------------------------------------------------------

--Daniel Cebrián Castillo
densa :: (Num a, Eq a) => Polinomio a -> [(Int,a)]
densa p | esPolCero p = [(0,0)]
        | otherwise =(grado p, coefLider p ):(densa (restoPol p))


-- Álvaro Galisteo:

densa :: (Num a, Eq a) => Polinomio a -> [(Int,a)]
densa p | esPolCero p = []
        | otherwise = (grado p, coefLider p):(densa (restoPol p))


-- ----------------------------------------------------------------------------
-- Ejercicio 4. Definir la función
--   dispersa :: (Num a, Eq a) => Polinomio a -> [a]
-- tal que '(dispersa p)' es la representación dispersa del polinomio 'p'. Por
-- ejemplo,
--   dispersa (creaPolDispersa [1,0,0,5,4,0])  ==  [1,0,0,5,4,0]
-- ----------------------------------------------------------------------------

--Daniel Cebrián Castillo
dispersa :: (Num a, Eq a) => Polinomio a -> [a]
dispersa p | esPolCero p = []
           | grado p == 1 && coefLider (restoPol p) == 0 = [(coefLider p),0] 
           | otherwise = (coefLider p):(replicate ((grado p) - (grado (restoPol p)) -1) 0) ++(dispersa (restoPol p))


-- Álvaro Galisteo:

dispersa :: (Num a, Eq a) => Polinomio a -> [a]
dispersa p | esPolCero p = []
           | esPolCero (restoPol p) = [coefLider p]++(replicate (grado p) 0)
           | otherwise = [coefLider p] ++ replicate ((grado p ) - ((grado (restoPol p)) + 1)) 0 ++ (dispersa (restoPol p))


-- ----------------------------------------------------------------------------
-- Ejercicio 5. Definir la función
--   coeficiente :: (Num a, Eq a) => Int -> Polinomio a -> a
-- tal que '(coeficiente k p)' es el coeficiente del término de grado 'k' del
-- polinomio 'p'. Por ejemplo,
--   coeficiente 2 (creaPolDispersa [1,0,0,5,4,0])  ==  5
--   coeficiente 3 (creaPolDispersa [1,0,0,5,4,0])  ==  0
-- ----------------------------------------------------------------------------

--Daniel Cebrián Castillo
coeficiente :: (Num a, Eq a) => Int -> Polinomio a -> a
coeficiente  n p | esPolCero p = 0
                 | grado p == n = coefLider p
                 | otherwise = coeficiente n (restoPol p) 


-- Álvaro Galisteo:

coeficiente :: (Num a, Eq a) => Int -> Polinomio a -> a
coeficiente k p | grado p > k = coeficiente k (restoPol p)
                | grado p == k = coefLider p 
                | otherwise = 0


-- ----------------------------------------------------------------------------
-- Ejercicio 6. Definir la función
--   creaTermino :: (Num a, Eq a) => Int -> a -> Polinomio a
-- tal que '(creaTermino n a)' es el término 'a*x^n'. Por ejemplo,
--   creaTermino 2 5  =>  5*x^2
-- ----------------------------------------------------------------------------

--Daniel Cebrián Castillo, Álvaro Galisteo:
creaTermino :: (Num a, Eq a) => Int -> a -> Polinomio a
creaTermino n a = consPol n a polCero

-- ----------------------------------------------------------------------------
-- Ejercicio 7. Definir la función
--   termLider :: (Num a, Eq a) => Polinomio a -> Polinomio a
-- tal que '(termLider p)' es el término líder del polinomio 'p'. Por ejemplo,
--   termLider (creaPolDispersa [1,0,0,5,4,0])  =>  x^5
-- ----------------------------------------------------------------------------

--Daniel Cebrián Castillo, Álvaro Galisteo:
termLider :: (Num a, Eq a) => Polinomio a -> Polinomio a
termLider p = creaTermino (grado p) (coefLider p)

-- ----------------------------------------------------------------------------
-- Ejercicio 8. Definir la función
--   sumaPol :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a
-- tal que '(sumaPol p q)' es la suma de los polinomios 'p' y 'q'. Por ejemplo,
--   sumaPol (creaPolDispersa [1,0,0,5,4,0]) (creaPolDispersa [3,1])  =>
--     x^5 + 5*x^2 + 7*x + 1
-- ----------------------------------------------------------------------------

--Daniel Cebrián Castillo
sumaPol :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a
sumaPol p q | esPolCero p = q
            | esPolCero q = p
            | grado p == grado q = consPol (grado p) (coefLider p + coefLider q) (sumaPol (restoPol p) (restoPol q))
            | grado p < grado q = consPol (grado q) (coefLider q) (sumaPol (p) (restoPol q))
            | otherwise = consPol (grado p) (coefLider p) (sumaPol (q) (restoPol p))
            

-- Álvaro Galisteo:

sumaPol :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a
sumaPol p q | esPolCero p = q
            | otherwise = sumaPol (restoPol p) (consPol (grado p) (coefLider p) q)


-- ----------------------------------------------------------------------------
-- Ejercicio 9. Definir la función
--   multTermPol :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a
-- tal que '(multTermPol t p)' es el producto del término 't' por el polinomio
-- 'p'. Por ejemplo,
--   multTermPol (creaTermino 3 1) (creaPolDispersa [3,1])  =>  3*x^4 + x^3
-- ----------------------------------------------------------------------------

--Daniel Cebrián Castillo
multTermPol :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a
multTermPol t p | esPolCero p || esPolCero t = polCero 
                |otherwise = consPol (grado t + grado p) (coefLider t * coefLider p) (multTermPol (t) (restoPol p))



-- Álvaro Galisteo:

multTermPol :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a
multTermPol t p | esPolCero p = polCero
                | otherwise = consPol ((grado t)+(grado p)) ((coefLider t)*(coefLider p)) (multTermPol t (restoPol p))

-- ----------------------------------------------------------------------------
-- Ejercicio 10. Definir la función
--   resta :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a
-- tal que '(resta p q)' es el polinomio obtenido restando el polinomio 'q' al
-- polinomio 'p'. Por ejemplo,
--   restaPol (creaPolDispersa [1,0,0,5,4,0]) (creaPolDispersa [3,1])  =>
--     x^5 + 5*x^2 + x - 1
-- ----------------------------------------------------------------------------
--Daniel Cebrián Castillo
restaPol :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a
restaPol p q = sumaPol p (multTermPol (creaPolDensa [(0,-1)]) q)


-- Álvaro Galisteo:

restaPol :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a
restaPol p q | esPolCero q = p
             | otherwise = restaPol (consPol (grado q) (-(coefLider q)) p) (restoPol q) 


-- ----------------------------------------------------------------------------
-- Ejercicio 11. Definir la función
--   multPol :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a
-- tal que '(multPol p q)' es el producto de los polinomios 'p' y 'q'. Por
-- ejemplo,
--   multPol (creaPolDispersa [1,0,0,5,4,0]) (creaPolDispersa [3,1])  =>
--     3*x^6 + x^5 + 15*x^3 + 17*x^2 + 4*x
-- ----------------------------------------------------------------------------
--Daniel Cebrián Castillo
multPol :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a
multPol p q |esPolCero p = polCero
            |esPolCero q = polCero
            |otherwise = sumaPol (multTermPol (termLider q) p) (multPol p (restoPol q))



-- Álvaro Galisteo:

multPol :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a
multPol p q | esPolCero p = polCero
            | otherwise = sumaPol (multTermPol (termLider p)  q) (multPol (restoPol p) q)


-- ----------------------------------------------------------------------------
-- Ejercicio 12. Definir la función
--   valor :: (Num a, Eq a) => Polinomio a -> a -> a
-- tal que '(valor p v)' es el valor del polinomio 'p' al sustituir su variable
-- por el número 'c'. Por ejemplo,
--   valor (creaPolDispersa [1,0,0,5,4,0]) 0     ==  0
--   valor (creaPolDispersa [1,0,0,5,4,0]) 1     ==  10
--   valor (creaPolDispersa [1,0,0,5,4,0]) (-2)  ==  -20
-- ----------------------------------------------------------------------------

--Daniel Cebrián Castillo, Álvaro Galisteo:

valor :: (Num a, Eq a) => Polinomio a -> a -> a
valor p a | esPolCero p = 0
          | otherwise = (coefLider p) * (a)^(grado p) + (valor (restoPol p) a)


-- ----------------------------------------------------------------------------
-- Ejercicio 13. Definir la función
--   potencia :: (Num a, Eq a) => Polinomio a -> Int -> Polinomio a
-- tal que '(potencia p n)' es la potencia 'n'-ésima del polinomio 'p'. Por
-- ejemplo,
--   potencia (creaPolDispersa [3,1]) 2  =>  9*x^2 + 6*x + 1
--   potencia (creaPolDispersa [3,1]) 3  =>  27*x^3 + 27*x^2 + 9*x + 1
-- ----------------------------------------------------------------------------
--Daniel Cebrián Castillo
potencia :: (Num a, Eq a) => Polinomio a -> Int -> Polinomio a
potencia p n | esPolCero p = polCero
             | otherwise = (iterate (multPol p) p)!!(n-1)


-- Álvaro Galisteo: 

potencia :: (Num a, Eq a) => Polinomio a -> Int -> Polinomio a
potencia p n = aux p p (n-1)
           where aux acum pol pot | pot > 0 = aux (multPol acum pol) pol (pot -1)
                                  | otherwise = acum


-- ----------------------------------------------------------------------------
-- Ejercicio 14. Definir la función
--   potenciaM :: (Num a, Eq a) => Polinomio a -> Int -> Polinomio a
-- tal que '(potenciaM p n)' es la potencia 'n'-ésima del polinomio 'p', usando
-- las siguientes propiedades:
-- * Si n es par,   entonces x^n = (x^2)^(n/2)
-- * Si n es impar, entonces x^n = x * (x^2)^((n-1)/2)
-- Por ejemplo,
--   potenciaM (creaPolDispersa [3,1]) 2  =>  9*x^2 + 6*x + 1
--   potenciaM (creaPolDispersa [3,1]) 3  =>  27*x^3 + 27*x^2 + 9*x + 1
-- ----------------------------------------------------------------------------

-- Álvaro Galisteo: 

potenciaM :: (Num a, Eq a) => Polinomio a -> Int -> Polinomio a
potenciaM p n | even n = potencia (potencia p 2) (div n 2)
              | otherwise = multPol p (potencia (potencia p 2) (div (n-1) 2))


-- ----------------------------------------------------------------------------
-- Ejercicio 15. Definir la función
--   derivada :: Polinomio Int -> Polinomio Int
-- tal que '(derivada p)' es la derivada del polinomio 'p' con respecto a su
-- variable. Por ejemplo,
--   derivada (creaPolDispersa [1,0,0,5,4,0])  =>  5*x^4 + 10*x + 4
-- ----------------------------------------------------------------------------

--Daniel Cebrián Castillo, Álvaro Galisteo:
derivada :: Polinomio Int -> Polinomio Int
derivada p | esPolCero p = polCero
           | otherwise = consPol (grado p -1)((coefLider p)*(grado p)) (derivada (restoPol p))


-- ----------------------------------------------------------------------------
-- Ejercicio 16. Definir la función
--   integral :: (Fractional a, Eq a) => Polinomio a -> Polinomio a
-- tal que '(integral p)' es la integral del polinomio 'p' con respecto a su
-- variable. En este caso los coeficientes del polinomio 'p' deben ser de la
-- clase 'Fractional', números racionales o números reales. Por ejemplo,
--   integral (creaPolDispersa [3%1,0,5,0,3])  =>
--     3 % 5*x^5 + 5 % 3*x^3 + 3 % 1*x
--   integral (creaPolDispersa [3.0,0,5,0,3])  =>
--     0.6*x^5 + 1.6666666666666667*x^3 + 3.0*x
-- ----------------------------------------------------------------------------

--Daniel Cebrián Castillo, Álvaro Galisteo:

integral :: (Fractional a, Eq a) => Polinomio a -> Polinomio a
integral p | esPolCero p = polCero
           | otherwise = consPol (grado p + 1) ((coefLider p)/((fromIntegral (grado p)) +1)) (integral (restoPol p))


-- ----------------------------------------------------------------------------
-- Ejercicio 17. Definir la función
--   integralDef :: (Fractional a, Eq a) => Polinomio a -> a -> a -> a
-- tal que '(integralDef p a b)' es la integral definida del polinomio 'p' con
-- respecto a su variable, en el intervalo '(a,b)'. En este caso los
-- coeficientes del polinomio 'p' deben ser de la clase 'Fractional', números
-- racionales o números reales. Por ejemplo,
--   integralDef (creaPolDispersa [3%1,0,5,0,3]) 0 1  ==  79 % 15
--   integralDef (creaPolDispersa [3.0,0,5,0,3]) 0 1  ==  5.266666666666667
-- ----------------------------------------------------------------------------

--Daniel Cebrián Castillo, Álvaro Galisteo:

integralDef :: (Fractional a, Eq a) => Polinomio a -> a -> a -> a
integralDef p a b = (valor (integral p) b) - (valor (integral p) a) 


-- ----------------------------------------------------------------------------
-- Ejercicio 18. Definir la función
--   multEscalar :: (Num a, Eq a) => a -> Polinomio a -> Polinomio a
-- tal que '(multEscalar c p)' es el polinomio obtenido multiplicando el número
-- 'c' por el polinomio 'p'. Por ejemplo,
--   multEscalar 4 (creaPolDispersa [3,1])  =>  12*x + 4
-- ----------------------------------------------------------------------------

--Daniel Cebrián Castillo, Álvaro Galisteo:

multEscalar :: (Num a, Eq a) => a -> Polinomio a -> Polinomio a
multEscalar c p | esPolCero p = polCero
                | otherwise = consPol (grado p) ((coefLider p)*(c)) (multEscalar c (restoPol p))


-- ----------------------------------------------------------------------------
-- Ejercicio 19. Definir la función
--   cociente :: (Fractional a, Eq a) =>
--               Polinomio a -> Polinomio a -> Polinomio a
-- tal que '(cociente p q)' es el cociente de la división del polinomio 'p'
-- entre el polinomio 'q'. En este caso los coeficientes de los polinomios 'p'
-- y 'q' deben ser de la clase 'Fractional', números racionales o números
-- reales. Por ejemplo,
--   cociente (creaPolDispersa [3%1,0,5,0,3]) (creaPolDispersa [6,2,0])  =>
--     1 % 2*x^2 - 1 % 6*x + 8 % 9
--   cociente (creaPolDispersa [3.0,0,5,0,3]) (creaPolDispersa [6,2,0])  =>
--     0.5*x^2 - 0.16666666666666666*x + 0.8888888888888888
-- ----------------------------------------------------------------------------
--Daniel Cebrián Castillo
cociente :: (Fractional a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a
cociente p q | esPolCero p = polCero
             | esPolCero q = error "Has intentado dividir por el polinomio cero. Buen intento -_-"
             | grado p < grado q = polCero
             | grado p  >= grado q = sumaPol  (x) (cociente (restaPol (restoPol p) (multTermPol (x) (restoPol q))) q)
  where x = consPol ((grado p)-(grado q)) ((coefLider p)/(coefLider q)) (polCero)


-- Álvaro Galisteo: 

cociente :: (Fractional a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a
cociente p q | grado q > grado p = polCero
             | otherwise = consPol (grado p - grado q) (coefLider p / coefLider q) (cociente (restaPol p (multPol (consPol (grado p - grado q) (coefLider p / coefLider q) polCero) q)) q)


-- ----------------------------------------------------------------------------
-- Ejercicio 20. Definir la función
--   resto :: (Fractional a, Eq a) =>
--            Polinomio a -> Polinomio a -> Polinomio a
-- tal que '(resto p q)' es el resto de la división del polinomio 'p' entre el
-- polinomio 'q'. En este caso los coeficientes de los polinomios 'p' y 'q'
-- deben ser de la clase 'Fractional', números racionales o números reales. Por
-- ejemplo,
--   resto (creaPolDispersa [3%1,0,5,0,3]) (creaPolDispersa [6,2,0])  =>
--     - 16 % 9*x + 3 % 1
--   resto (creaPolDispersa [3.0,0,5,0,3]) (creaPolDispersa [6,2,0])  =>
--     - 1.7777777777777777*x + 3.0
-- ----------------------------------------------------------------------------
--Daniel Cebrián Castillo
resto :: (Fractional a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a
resto  p q | esPolCero p = polCero
           | esPolCero q = error "Has intentado dividir por el polinomio cero. Buen intento -_-"
           | grado p < grado q = p
           | grado p >= grado q = resto (restaPol (restoPol p) (multTermPol (x) (restoPol q)))  q
 where x = consPol ((grado p)-(grado q)) ((coefLider p)/(coefLider q)) (polCero)



- Álvaro Galisteo: 

resto :: (Fractional a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a
resto p q = restaPol p (multPol (cociente p q) q)


-- ----------------------------------------------------------------------------
-- Ejercicio 21. Definir la función
--   divisiblePol :: (Fractional a, Eq a) =>
--                   Polinomio a -> Polinomio a -> Bool
-- tal que '(divisiblePol p q)' se verifica si el polinomio 'p' es divisible
-- por el polinomio 'q'. Por ejemplo,
--   divisiblePol (creaPolDispersa [6,2,0]) (creaPolDispersa [3,1])  ==  True
--   divisiblePol (creaPolDispersa [6,2,0]) (creaPolDispersa [3,2])  ==  False
-- ----------------------------------------------------------------------------
--Daniel Cebrián Castillo
divisiblePol :: (Fractional a, Eq a) => Polinomio a -> Polinomio a -> Bool
divisiblePol p q | esPolCero (resto p q) = True
                 | otherwise = False


-- Álvaro Galisteo: 

divisiblePol :: (Fractional a, Eq a) => Polinomio a -> Polinomio a -> Bool
divisiblePol p q = esPolCero (resto p q) 


-- ----------------------------------------------------------------------------
-- Ejercicio 22. El método de Horner para calcular el valor de un polinomio se
-- basa en representarlo de una forma alternativa. Por ejemplo, para calcular
-- el valor de
--   a*x^5 + b*x^4 + c*x^3 + d*x^2 + e*x + f
-- este polinomio se representa como
--   ((((a * x + b) * x + c) * x + d) * x + e) * x + f
-- y se evalúa de dentro hacia afuera.
--
-- Definir la función
--   horner :: (Eq a, Num a) => Polinomio a -> a -> a
-- tal que '(horner p c)' es el valor del polinomio 'p' al sustituir su
-- variable por el número 'c', calculado usando el método de Horner. Por
-- ejemplo,
--   horner (creaPolDispersa [1,0,0,5,4,0]) 0      ==  0
--   horner (creaPolDispersa [1,0,0,5,4,0]) 1      ==  10
--   horner (creaPolDispersa [1,0,0,5,4,0]) 1.5    ==  24.84375
--   horner (creaPolDispersa [1,0,0,5,4,0]) (3%2)  ==  795 % 32
-- ----------------------------------------------------------------------------

--Daniel Cebrián Castillo, Álvaro Galisteo: 

horner :: (Eq a, Num a) => Polinomio a -> a -> a
horner p c = foldl ((+).(c*)) (0) ((dispersa p))

     
-- ============================================================================
-- Factorización de polinomios
-- ============================================================================

-- ----------------------------------------------------------------------------
-- La regla de Ruffini facilita el cálculo rápido de la división de cualquier
-- polinomio entre un binomio de la forma (x-r). Además, esta regla permite
-- localizar las raíces enteras de un polinomio y factorizarlo en binomios de
-- la forma (x-r) (siendo r un número entero) siempre que sea posible.
--
-- La regla establece un método para la división de un polinomio
--             p = an x^n + a(n-1) x^(n-1) + ... + a2 x^2 + a1 x + a0
-- entre un binomio de la forma (x-r). Para ello se trazan dos líneas a modo de
-- ejes y se sitúan los coeficientes del polinomio ordenados y sin omitir
-- términos nulos (es decir su representación densa) en línea en la parte
-- superior; el número r (del binomio (x-r)) se sitúa en el lado izquierdo del
-- eje vertical:
--
--     | an a(n-1) ... a2 a1 a0
--   r |
--  ---+------------------------
--     |
--
-- El primer coeficiente del polinomio se sitúa debajo del eje horizontal, en
-- la misma columna:
--
--     | an     a(n-1)    ... a2 a1 a0
--   r |
--  ---+--------------------------------
--     | an
--
-- A continuación se multiplica r por an y se sitúa el resultado debajo del
-- siguiente término del polinomio (a(n-1)):
--
--     | an     a(n-1)    ... a2 a1 a0
--   r |         r*an
--  ---+--------------------------------
--     | an
--
-- Se suman los valores de esta columna y el resultado se coloca debajo del eje
-- horizontal, en la misma columna:
--
--     | an     a(n-1)    ... a2 a1 a0
--   r |         r*an
--  ---+--------------------------------
--     | an  a(n-1)+r*an
--
-- A continuación se repite el proceso de multiplicar r por el resultado de la
-- suma anterior; se coloca el resultado en la siguiente columna, debajo del
-- siguiente coeficiente del polinomio; se suman los números de esta columna y
-- se coloca el resultado de la suma debajo del eje horizontal, en la misma
-- columna.
--
-- El proceso se repite hasta llegar a la última columna, la del término
-- independiente del polinomio original.
--
-- El cociente de la división es el polinomio cuyos coeficientes (es decir, su
-- representación dispersa) son los que están debajo del eje horizontal salvo el
-- último, y el resto de la división es el número que aparece en la última
-- columna debajo del eje horizontal.
--
-- Algunos ejemplos:
--
-- - Dividiendo el polinomio x^3 + 2 x^2 - x - 2 entre (x-2)
--
--         | 1  2  -1  -2
--       2 |    2   8  14
--     ----+--------------
--         | 1  4   7  12
--
--   Cociente: x^2 + 4 x + 7         Resto: 12
--
-- - Dividiendo el polinomio 2 x^3 + 3 x^2 - 4 entre (x+1)
--
--         | 2  3   0  -4
--      -1 |   -2  -1   1
--     ----+--------------
--         | 2  1  -1  -3
--
--   Cociente: 2 x^2 + x - 1         Resto: -3
--
-- Cuando el resto es igual a 0, conseguimos factorizar el polinomio original.
-- Por ejemplo, al dividir el polinomio x^3 + x^2 - x - 1 entre (x+1) se tiene
--
--         | 1  1  -1  -1
--      -1 |   -1   0   1
--     ----+--------------
--         | 1  0  -1   0
--
-- Por tanto el cociente es x^2 - 1 y el resto 0, lo que quiere decir que
-- x^3 + x^2 - x - 1 = (x+1)*(x^2 - 1)
--
-- Para que esto ocurra, el número r (de (x-r)) tiene que ser un divisor del
-- término independiente del polinomio original.
--
-- Si se continúa el proceso con el cociente de la división anterior y probando
-- con los valores r divisores de su término independiente, podemos llegar a
-- factorizar completamente el polinomio original en factores de la forma (x-r)
-- y, posiblemente, un último factor que es un polinomio sin raices enteras.
--
-- El objetivo de los siguientes ejercicios es implementar en Haskell este
-- proceso de factorización de polinomios.
-- ----------------------------------------------------------------------------

-- ----------------------------------------------------------------------------
-- Ejercicio 23. Definir la función
--   reglaRuffini :: Int -> [Int] -> [Int]
-- tal que '(reglaRuffini r cs)' es la lista que resulta de aplicar la regla de
-- Ruffini al número entero 'r' y a la lista de coeficientes 'cs'. Por ejemplo,
--   reglaRuffini 2 [1,2,-1,-2]  ==  [1,4,7,12]
--   reglaRuffini 1 [1,2,-1,-2]  ==  [1,3,2,0]
-- ya que
--      | 1  2  -1  -2           | 1  2  -1  -2
--    2 |    2   8  14         1 |    1   3   2
--    --+--------------        --+-------------
--      | 1  4   7  12           | 1  3   2   0
-- ----------------------------------------------------------------------------
--Daniel Cebrián Castillo
reglaRuffini :: Int -> [Int] -> [Int]
reglaRuffini r cs = ([ array  A.! j | j<-[1..(length cs)]])
  where array = (A.listArray (0,(length cs)) ([0]++[putElem i | i<-[1..(length cs)]]))
        putElem i = (array A.! (i-1))*r + (cs!!(i-1))
--Álvaro Abellán García 
reglaRuffini' :: Int -> [Int] -> [Int]
reglaRuffini' r cs = [head cs] ++ reglaRuffiniac cs r (length cs -1)

 
reglaRuffiniac cs r ac | ac == 0 = []
                       | tail cs == [] = [head cs*r]
                       | otherwise = [pr] ++ reglaRuffiniac ((pr):(drop 2 (cs))) r (ac-1)
  where pr = (r* head cs) + (head (tail cs))



-- Álvaro Galisteo: 


reglaRuffini :: Int -> [Int] -> [Int]
reglaRuffini r (c:cs) = aux r (c:cs) [c]
                      where aux n (x:xs) ys | length ys == length (x:xs) = ys
                                            | otherwise = aux n (x:xs) (zipWith (+) (x:xs) (0:(map (*n) ys)))


-- ----------------------------------------------------------------------------
-- Ejercicio 24. Definir la función
--   cocienteRuffini :: Int -> Polinomio Int -> Polinomio Int
-- tal que '(cocienteRuffini r p)' es el cociente de dividir el polinomio 'p'
-- por el polinomio 'x-r' usando la regla de Ruffini. Por ejemplo:
--   cocienteRuffini 2 (creaPolDispersa [1,-3,3,-1])     =>  x^2 - x + 1
--   cocienteRuffini (-2) (creaPolDispersa [1,-3,3,-1])  =>  x^2 - 5*x + 13
--   cocienteRuffini 3 (creaPolDispersa [1,-3,3,-1])     =>  x^2 + 3
-- ----------------------------------------------------------------------------
--Daniel Cebrián Castillo
cocienteRuffini :: Int -> Polinomio Int -> Polinomio Int
cocienteRuffini r p = creaPolDispersa (reverse(tail(reverse(reglaRuffini r (dispersa p)))))

--Álvaro Abellán García
cocienteRuffini' :: Int -> Polinomio Int -> Polinomio Int
cocienteRuffini' r p = creaPolDispersa (reglaRuffini r (init (dispersa p)))


-- Álvaro Galisteo:

cocienteRuffini :: Int -> Polinomio Int -> Polinomio Int
cocienteRuffini r p = creaPolDispersa (init(reglaRuffini r (dispersa p)))


-- ----------------------------------------------------------------------------
-- Ejercicio 25. Definir la función
--   restoRuffini :: Int -> Polinomio Int -> Int
-- tal que '(restoRuffini r p)' es el resto de dividir el polinomio 'p' por el
-- polinomio 'x-r' usando la regla de Ruffini. Por ejemplo,
--   restoRuffini 2 (creaPolDispersa [1,-3,3,-1])     ==  1
--   restoRuffini (-2) (creaPolDispersa [1,-3,3,-1])  ==  -27
--   restoRuffini 3 (creaPolDispersa [1,-3,3,-1])     ==  8
-- ----------------------------------------------------------------------------
--Daniel Cebrián Castillo
restoRuffini :: Int -> Polinomio Int -> Int
restoRuffini r p = head(reverse(reglaRuffini r (dispersa p)))


--Álvaro Abellán García, Álvaro Galisteo:

restoRuffini :: Int -> Polinomio Int -> Int
restoRuffini r p = last (reglaRuffini r (dispersa p))


-- ----------------------------------------------------------------------------
-- Ejercicio 26. Comprobar con QuickCheck que, dado un polinomio 'p' no nulo y
-- un número entero 'r', las funciones anteriores verifican la propiedad de la
-- división euclídea.
-- ----------------------------------------------------------------------------


-- Álvaro Galisteo: 

-- La propiedad es
prop_diviEuclidea :: Int -> Polinomio Int -> Property
prop_diviEuclidea r p = p /= polCero ==> sumaPol (multPol (cocienteRuffini r p) (creaPolDispersa [1,-r])) (creaTermino 0 (restoRuffini r p)) == p

-- La comprobación es
--   > quickCheck prop_diviEuclidea
--     *Main> quickCheck prop_diviEuclidea
--      +++ OK, passed 100 tests; 11 discarded.


-- ----------------------------------------------------------------------------
-- Ejercicio 27. Definir la función
--   esRaizRuffini :: Int -> Polinomio Int -> Bool
-- tal que '(esRaizRuffini r p)' se verifica si 'r' es una raíz de 'p', usando
-- para ello la regla de Ruffini. Por ejemplo,
--   esRaizRuffini 0 (creaPolDispersa [1,-3,3,-1])  ==  False
--   esRaizRuffini 1 (creaPolDispersa [1,-3,3,-1])  ==  True
-- ----------------------------------------------------------------------------

--Daniel Cebrián Castillo, Álvaro Galisteo: 

esRaizRuffini :: Int -> Polinomio Int -> Bool
esRaizRuffini r p = restoRuffini r p == 0


-- ----------------------------------------------------------------------------
-- Ejercicio 28. Definir la función
--   divisores :: Int -> [Int]
-- tal que '(divisores n)' es la lista de todos los divisores enteros del
-- número 'n'. Por ejemplo,
--   divisores 0  ==  [0]
--   divisores 1  ==  [1,-1]
--   divisores 4  ==  [4,-4,2,-2,1,-1]
-- ----------------------------------------------------------------------------
--Daniel Cebrián Castillo
divisores :: Int -> [Int]
divisores 0 = [0]
divisores 1 = [1,-1]
divisores n  | n<0 = divisores (-n)
             | otherwise = [n,-n] ++ divisores t
  where t = head (candidatos)
        candidatos = [ x | x<-[(n-1),(n-2)..1], x/=n, rem n x == 0] 


-- Álvaro Galisteo: 

divisores :: Int -> [Int]
divisores 0 = [0]
divisores n = xs ++ map (*(-1)) xs
            where xs = [x | x <- [1..(abs n)], mod (abs n) x == 0]

-- ----------------------------------------------------------------------------
-- Ejercicio 29. Definir la función
--   raicesRuffini :: Polinomio Int -> [Int]
-- tal que '(raicesRuffini p)' es la lista de las raices enteras de 'p',
-- calculadas usando la regla de Ruffini. Por ejemplo,
--   raicesRuffini (creaPolDispersa [1,0,0,5,4,0])  ==  [0,-1]
--   raicesRuffini (creaPolDispersa [3,1])          ==  []
--   raicesRuffini (creaPolDispersa [1,2,-1,-2])    ==  [-2,1,-1]
--   raicesRuffini (creaPolDispersa [1,-3,3,-1])    ==  [1,1,1]
-- ----------------------------------------------------------------------------
--Daniel Cebrián Castillo
raicesRuffini :: Polinomio Int -> [Int]
raicesRuffini p | esPolCero p = []
                | grado p == 0 = []
                | null ([ h|h<- (divisores(head (reverse(dispersa p)))), esRaizRuffini h p]) = []
                | otherwise = he:  (raicesRuffini (cocienteRuffini he p)) 
                where he = head ([ h|h<- (divisores(head (reverse(dispersa p)))), esRaizRuffini h p])


-- Álvaro Galisteo: 

raicesRuffini :: Polinomio Int -> [Int]
raicesRuffini p | null r = []
                | otherwise = [head r] ++ raicesRuffini (cocienteRuffini (head r) p)
                where r = [x | x <- (divisores (last(dispersa p))), esRaizRuffini x p]


-- ----------------------------------------------------------------------------
-- Ejercicio 30. Definir la función
--   factorizacion :: Polinomio Int -> [Polinomio Int]
-- tal que '(factorizacion p)' es la lista de la descomposición del polinomio
-- 'p' en factores obtenida mediante la regla de Ruffini. Por ejemplo,
--   factorizacion (creaPolDispersa [1,0,0,5,4,0])  =>
--     [x^3 - x^2 + x + 4,x,x + 1]
--   factorizacion (creaPolDispersa [3,1])          =>  [3*x + 1]
--   factorizacion (creaPolDispersa [1,2,-1,-2])    =>  [x + 2,x - 1,x + 1]
--   factorizacion (creaPolDispersa [1,-3,3,-1])    =>  [x - 1,x - 1,x - 1]
-- ----------------------------------------------------------------------------
--Daniel Cebrián Castillo
factorizacion :: Polinomio Int -> [Polinomio Int]
factorizacion p | esPolCero p = [polCero]
                | grado p == 0 = []
                | null (raicesRuffini p) = [p]
                | otherwise = (consPol 1 1 (consPol 0 (-r) polCero)):factorizacion (cocienteRuffini r p)
                  where r = head (raicesRuffini p)

--Álvaro Abellán García 
factorizacion' :: Polinomio Int -> [Polinomio Int]
factorizacion' p | grado p == 1 = [p]
                 | grado p == 0 = []
                 | esPolCero p = [polCero]
                 | otherwise = [consPol 1 1 (consPol 0 (-c) polCero) | c <- raicesRuffini p]



-- Álvaro Galisteo: 

factorizacion :: Polinomio Int -> [Polinomio Int]
factorizacion p | null (raicesRuffini p) = [p]
                | otherwise = [consPol 1 1 (consPol 0 (-x) (polCero)) |x <- raicesRuffini p]
      
                           
-- ----------------------------------------------------------------------------
-- Generador de polinomios
-- ----------------------------------------------------------------------------

-- (genPol n) es un generador de polinomios. Por ejemplo,
--   ghci> sample (genPol 1)
--   0
--   x^9 + 4*x^5 - 2*x^2
--   - 5*x^10 + 4*x^9 + 3*x^7 - x^3 + 2
--   - 4*x^8 - 4*x^3 - 2*x
--   - 6*x^8 - 3
--   - 9*x^10 + 2*x^9 - 7*x^8 + 2*x^7 - 2*x^6 - 3*x^5 - 4*x^3 - 10
--   - 7
--   - 2*x^8 + 8*x^4 + x^2 + 12*x
--   5*x^5 - 15*x^2 - 8
--   11
--   16*x^9 + 9*x^7 + 8*x^5 - 14*x^4 - 19*x^2 + 5

genPol :: (Arbitrary a, Num a, Eq a, Ord a) => Int -> Gen (Polinomio a)
genPol 0 = return polCero
genPol n = do
  n <- choose (0,10)
  b <- arbitrary
  p <- genPol (div n 2)
  return (consPol n b p)

instance (Arbitrary a, Num a, Eq a, Ord a) => Arbitrary (Polinomio a) where
  arbitrary = sized genPol

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