-- 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
-- ----------------------------------------------------------------------------
creaPolDensa :: (Num a, Eq a) => [(Int,a)] -> Polinomio a
creaPolDensa [] = polCero
creaPolDensa ((n,a):xs) = consPol n a (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
-- ----------------------------------------------------------------------------
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)]
-- ----------------------------------------------------------------------------
densa :: (Num a, Eq a) => Polinomio a -> [(Int,a)]
densa p | esPolCero p = []
| otherwise = (g,c):(densa r)
where g = grado p
c = coefLider p
r = 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]
-- ----------------------------------------------------------------------------
dispersa :: (Num a, Eq a) => Polinomio a -> [a]
dispersa p | esPolCero p = []
| otherwise = reverse (dispersaAux p 0)
dispersaAux :: (Num a, Eq a) => Polinomio a -> Int -> [a]
dispersaAux p i | grado p == i = [coefLider p]
| otherwise = (coeficiente i p):(dispersaAux p (i+1))
-- ----------------------------------------------------------------------------
-- 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
-- ----------------------------------------------------------------------------
coeficiente :: (Num a, Eq a) => Int -> Polinomio a -> a
coeficiente n p | grado p < n = 0
| grado p == n = coefLider p
| otherwise = coeficiente n (restoPol p)
-- ----------------------------------------------------------------------------
-- 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
-- ----------------------------------------------------------------------------
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
-- ----------------------------------------------------------------------------
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
-- ----------------------------------------------------------------------------
sumaPol :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a
sumaPol p q | esPolCero p = q
| otherwise = consPol (grado p) (coefLider p) (sumaPol (restoPol 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
-- ----------------------------------------------------------------------------
multTermPol :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a
multTermPol t p | esPolCero p = polCero
| otherwise = consPol (gt + gp) (ct * cp) (multTermPol t (restoPol p))
where gt = grado t
ct = coefLider t
gp = grado p
cp = coefLider 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
-- ----------------------------------------------------------------------------
restaPol :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a
restaPol p q = sumaPol p (multTermPol (creaTermino 0 (-1)) 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
-- ----------------------------------------------------------------------------
multPol :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a
multPol p q | esPolCero p = polCero
| otherwise = sumaPol (multTermPol t q) (multPol (restoPol p) q)
where gp = grado p
cp = coefLider p
t = creaTermino gp cp
-- ----------------------------------------------------------------------------
-- 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
-- ----------------------------------------------------------------------------
valor :: (Num a, Eq a) => Polinomio a -> a -> a
valor p v | esPolCero p = 0
| otherwise = cp * v ^ gp + valor (restoPol p) v
where gp = grado p
cp = coefLider p
-- ----------------------------------------------------------------------------
-- 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
-- ----------------------------------------------------------------------------
potencia :: (Num a, Eq a) => Polinomio a -> Int -> Polinomio a
potencia p n | n == 0 = creaTermino 0 1
| n == 1 = p
| otherwise = multPol p (potencia p (n-1))
-- ----------------------------------------------------------------------------
-- 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
-- ----------------------------------------------------------------------------
potenciaM :: (Num a, Eq a) => Polinomio a -> Int -> Polinomio a
potenciaM p n | n == 0 = creaTermino 0 1
| even n = potenciaM (multPol p p) (n `div` 2)
| otherwise = multPol p (potenciaM (multPol p p) (n `div` 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
-- ----------------------------------------------------------------------------
derivada :: Polinomio Int -> Polinomio Int
derivada p | esPolCero p = polCero
| otherwise = consPol (gp-1) (cp*gp) (derivada (restoPol p))
where gp = grado p
cp = coefLider 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
-- ----------------------------------------------------------------------------
integral :: (Fractional a, Eq a) => Polinomio a -> Polinomio a
integral p | esPolCero p = polCero
| otherwise = consPol (gp+1) (cp / (fromIntegral (gp+1))) (integral (restoPol p))
where gp = grado p
cp = coefLider 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
-- ----------------------------------------------------------------------------
integralDef :: (Fractional a, Eq a) => Polinomio a -> a -> a -> a
integralDef p a b = valor i b - valor i a
where i = integral p
-- ----------------------------------------------------------------------------
-- 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
-- ----------------------------------------------------------------------------
multEscalar :: (Num a, Eq a) => a -> Polinomio a -> Polinomio a
multEscalar c p | esPolCero p = polCero
| otherwise = consPol gp (c*cp) (multEscalar c (restoPol p))
where gp = grado p
cp = coefLider 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
-- ----------------------------------------------------------------------------
cociente :: (Fractional a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a
cociente p q | gp < gq = polCero
| otherwise = consPol rg dc (cociente (restaPol p (multTermPol (creaTermino rg dc) q)) q)
where gq = grado q
cq = coefLider q
gp = grado p
cp = coefLider p
rg = gp - gq
dc = cp / cq
-- ----------------------------------------------------------------------------
-- 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
-- ----------------------------------------------------------------------------
resto :: (Fractional a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a
resto p q = restaPol p (multPol q (cociente p 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
-- ----------------------------------------------------------------------------
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
-- ----------------------------------------------------------------------------
horner :: (Eq a, Num a) => Polinomio a -> a -> a
horner p v | esPolCero p = 0
| otherwise = coeficiente 0 p + v * (horner (reduce p) v)
reduce :: (Eq a, Num a) => Polinomio a -> Polinomio a
reduce p | esPolCero p || gp == 0 = polCero
| otherwise = consPol (gp - 1) cp (reduce (restoPol p))
where gp = grado p
cp = coefLider 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
-- ----------------------------------------------------------------------------
reglaRuffini :: Int -> [Int] -> [Int]
reglaRuffini r [] = []
reglaRuffini r (x:[]) = [x]
reglaRuffini r (x:y:cs) = x:(reglaRuffini r ((y+r*x):cs))
-- ----------------------------------------------------------------------------
-- 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
-- ----------------------------------------------------------------------------
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
-- ----------------------------------------------------------------------------
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.
-- ----------------------------------------------------------------------------
-- La propiedad es
prop_diviEuclidea :: Int -> Polinomio Int -> Property
prop_diviEuclidea raiz p = raiz /= 0 ==> p == sumaPol r (multPol c d)
where r = consPol 0 (restoRuffini raiz p) polCero
c = cocienteRuffini raiz p
d = consPol 1 1 (consPol 0 (-raiz) polCero)
-- La comprobación es
-- > quickCheck prop_diviEuclidea
-- ----------------------------------------------------------------------------
-- 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
-- ----------------------------------------------------------------------------
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]
-- ----------------------------------------------------------------------------
divisores :: Int -> [Int]
divisores 0 = [0]
divisores n = concat [[x,-x] | x <- [n,n-1..1], n `mod` 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]
-- ----------------------------------------------------------------------------
raicesRuffini :: Polinomio Int -> [Int]
raicesRuffini p | null raices = []
| otherwise = raiz:(raicesRuffini (cocienteRuffini raiz p))
where raices = (filter (\ x -> restoRuffini x p == 0) (divisores (abs (coeficiente 0 p))))
raiz = head raices
-- ----------------------------------------------------------------------------
-- 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]
-- ----------------------------------------------------------------------------
factorizacion :: Polinomio Int -> [Polinomio Int]
factorizacion p | null raices = [p]
| otherwise = (restoAux raices p):polinomios
where raices = raicesRuffini p
polinomios = map (\ x -> consPol 1 1 (consPol 0 (-x) polCero)) raices
restoAux [] p = p
restoAux (r:rs) p = restoAux rs (cocienteRuffini r 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
-- ============================================================================
![Informática de 1º de Matemáticas [Curso 2021-22, Grupo 3]](/WIKIS/I1M2021G3/resources/assets/logoUS.png)