José A. Alonso
Departamento de Ciencias de la Computación e I.A.
Universidad de Sevilla
Sevilla, 17 de agosto de 2019
Notas:
:opt no-lint
Signatura del TAD de los polinomios
sesion
polCero :: Polinomio a
esPolCero :: Polinomio a -> Bool
consPol :: (Num a, Eq a) => Int -> a -> Polinomio a -> Polinomio a
grado :: Polinomio a -> Int
coefLider :: Num a => Polinomio a -> a
restoPol :: (Num a, Eq a) => Polinomio a -> Polinomio a
Descripción de las operaciones:
polCero
es el polinomio cero.
(esPolCero p)
se verifica si p
es el polinomio cero.
(consPol n b p)
es el polinomio $bx^n+p$.
(grado p)
es el grado del polinomio p
.
(coefLider p)
es el coeficiente líder del polinomio p
.
(restoPol p)
es el resto del polinomio p
.
Ejemplos de polinomios
ejPol1, ejPol2, ejPol3, ejTerm:: Polinomio Int
ejPol1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))
ejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))
ejPol3 = consPol 4 6 (consPol 1 2 polCero)
ejTerm = consPol 1 4 polCero
sesion
ejPol1 == 3*x^4 + -5*x^2 + 3
ejPol2 == x^5 + 5*x^2 + 4*x
ejPol3 == 6*x^4 + 2*x
ejTerm == 4*x
esPolCero polCero
n > grado p && b /= 0 ==> not (esPolCero (consPol n b p))
consPol (grado p) (coefLider p) (restoPol p) == p
n > grado p && b /= 0 ==> grado (consPol n b p) == n
n > grado p && b /= 0 ==> coefLider (consPol n b p) == b
n > grado p && b /= 0 ==> restoPol (consPol n b p) == p
module PolRepTDA
( Polinomio,
polCero, -- Polinomio a
esPolCero, -- Polinomio a -> Bool
consPol, -- (Num a, Eq a)) => Int -> a -> Polinomio a -> Polinomio a
grado, -- Polinomio a -> Int
coefLider, -- Num t => Polinomio t -> t
restoPol -- Polinomio t -> Polinomio t
) where
-- ---------------------------------------------------------------------
-- TAD de los polinomios mediante un tipo de dato algebraico. --
-- ---------------------------------------------------------------------
-- Representamos un polinomio mediante los constructores ConsPol y
-- PolCero. Por ejemplo, el polinomio
-- 6x^4 -5x^2 + 4x -7
-- se representa por
-- ConsPol 4 6 (ConsPol 2 (-5) (ConsPol 1 4 (ConsPol 0 (-7) PolCero)))
data Polinomio a = PolCero
| ConsPol Int a (Polinomio a)
deriving Eq
-- ---------------------------------------------------------------------
-- Escritura de los polinomios --
-- ---------------------------------------------------------------------
instance (Num a, Show a, Eq a) => Show (Polinomio a) where
show PolCero = "0"
show (ConsPol 0 b PolCero) = show b
show (ConsPol 0 b p) = concat [show b, " + ", show p]
show (ConsPol 1 b PolCero) = show b ++ "*x"
show (ConsPol 1 b p) = concat [show b, "*x + ", show p]
show (ConsPol n 1 PolCero) = "x^" ++ show n
show (ConsPol n b PolCero) = concat [show b, "*x^", show n]
show (ConsPol n 1 p) = concat ["x^", show n, " + ", show p]
show (ConsPol n b p) = concat [show b, "*x^", show n, " + ", show p]
-- ---------------------------------------------------------------------
-- Ejemplos de polinomios --
-- ---------------------------------------------------------------------
-- Ejemplos de polinomios con coeficientes enteros:
ejPol1, ejPol2, ejPol3:: Polinomio Int
ejPol1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))
ejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))
ejPol3 = consPol 4 6 (consPol 1 2 polCero)
-- Comprobación de escritura:
-- > ejPol1
-- 3*x^4 + -5*x^2 + 3
-- > ejPol2
-- x^5 + 5*x^2 + 4*x
-- > ejPol3
-- 6*x^4 + 2*x
-- Ejemplos de polinomios con coeficientes reales:
ejPol5, ejPol6, ejPol7:: Polinomio Float
ejPol5 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))
ejPol6 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))
ejPol7 = consPol 1 2 (consPol 4 6 polCero)
-- Comprobación de escritura:
-- > ejPol5
-- 3.0*x^4 + -5.0*x^2 + 3.0
-- > ejPol6
-- x^5 + 5.0*x^2 + 4.0*x
-- > ejPol7
-- 6.0*x^4 + 2.0*x
-- ---------------------------------------------------------------------
-- Implementación de la especificación --
-- ---------------------------------------------------------------------
-- polCero es el polinomio cero. Por ejemplo,
-- > polCero
-- 0
polCero :: Polinomio a
polCero = PolCero
-- (esPolCero p) se verifica si p es el polinomio cero. Por ejemplo,
-- esPolCero polCero == True
-- esPolCero ejPol1 == False
esPolCero :: Polinomio a -> Bool
esPolCero PolCero = True
esPolCero _ = False
-- (consPol n b p) es el polinomio bx^n+p. Por ejemplo,
-- ejPol2 == x^5 + 5*x^2 + 4*x
-- consPol 3 0 ejPol2 == x^5 + 5*x^2 + 4*x
-- consPol 3 2 polCero == 2*x^3
-- consPol 6 7 ejPol2 == 7*x^6 + x^5 + 5*x^2 + 4*x
-- consPol 4 7 ejPol2 == x^5 + 7*x^4 + 5*x^2 + 4*x
-- consPol 5 7 ejPol2 == 8*x^5 + 5*x^2 + 4*x
consPol :: (Num a, Eq a) => Int -> a -> Polinomio a -> Polinomio a
consPol _ 0 p = p
consPol n b PolCero = ConsPol n b PolCero
consPol n b (ConsPol m c p)
| n > m = ConsPol n b (ConsPol m c p)
| n < m = ConsPol m c (consPol n b p)
| b+c == 0 = p
| otherwise = ConsPol n (b+c) p
-- (grado p) es el grado del polinomio p. Por ejemplo,
-- ejPol3 == 6*x^4 + 2*x
-- grado ejPol3 == 4
grado :: Polinomio a -> Int
grado PolCero = 0
grado (ConsPol n _ _) = n
-- (coefLider p) es el coeficiente líder del polinomio p. Por ejemplo,
-- ejPol3 == 6*x^4 + 2*x
-- coefLider ejPol3 == 6
coefLider :: Num t => Polinomio t -> t
coefLider PolCero = 0
coefLider (ConsPol _ b _) = b
-- (restoPol p) es el resto del polinomio p. Por ejemplo,
-- ejPol3 == 6*x^4 + 2*x
-- restoPol ejPol3 == 2*x
-- ejPol2 == x^5 + 5*x^2 + 4*x
-- restoPol ejPol2 == 5*x^2 + 4*x
restoPol :: Polinomio t -> Polinomio t
restoPol PolCero = PolCero
restoPol (ConsPol _ _ p) = p
ejPol1 :: Polinomio Int
ejPol1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))
ejPol1
3*x^4 + -5*x^2 + 3
ejPol2 :: Polinomio Int
ejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))
ejPol2
x^5 + 5*x^2 + 4*x
ejPol3 :: Polinomio Int
ejPol3 = consPol 4 6 (consPol 1 2 polCero)
ejPol3
6*x^4 + 2*x
polCero
0
esPolCero polCero
True
esPolCero ejPol1
False
ejPol2
consPol 3 0 ejPol2
x^5 + 5*x^2 + 4*x
x^5 + 5*x^2 + 4*x
consPol 3 2 polCero
2*x^3
consPol 6 7 ejPol2
7*x^6 + x^5 + 5*x^2 + 4*x
consPol 4 7 ejPol2
x^5 + 7*x^4 + 5*x^2 + 4*x
consPol 5 7 ejPol2
8*x^5 + 5*x^2 + 4*x
ejPol3
grado ejPol3
6*x^4 + 2*x
4
coefLider ejPol3
6
restoPol ejPol3
2*x
ejPol2
restoPol ejPol2
x^5 + 5*x^2 + 4*x
5*x^2 + 4*x
:m - PolRepTDA
Representaremos un polinomio por la lista de sus coeficientes ordenados en orden decreciente según el grado. Por ejemplo, el polinomio 6x^4 -5x^2 + 4x -7 se representa por [6,0,-2,4,-7]
module PolRepDensa
( Polinomio,
polCero, -- Polinomio a
esPolCero, -- Polinomio a -> Bool
consPol, -- (Num a, Eq a) => Int -> a -> Polinomio a -> Polinomio a
grado, -- Polinomio a -> Int
coefLider, -- Num a => Polinomio a -> a
restoPol -- (Num a, Eq a) => Polinomio a -> Polinomio a
) where
-- ---------------------------------------------------------------------
-- TAD de los polinomios mediante listas densas --
-- ---------------------------------------------------------------------
newtype Polinomio a = Pol [a]
deriving Eq
-- ---------------------------------------------------------------------
-- Escritura de los polinomios --
-- ---------------------------------------------------------------------
instance (Num a, Show a, Eq a) => Show (Polinomio a) where
show pol
| esPolCero pol = "0"
| n == 0 && esPolCero p = show a
| n == 0 = concat [show a, " + ", show p]
| n == 1 && esPolCero p = show a ++ "*x"
| n == 1 = concat [show a, "*x + ", show p]
| a == 1 && esPolCero p = "x^" ++ show n
| esPolCero p = concat [show a, "*x^", show n]
| a == 1 = concat ["x^", show n, " + ", show p]
| otherwise = concat [show a, "*x^", show n, " + ", show p]
where n = grado pol
a = coefLider pol
p = restoPol pol
-- ---------------------------------------------------------------------
-- Ejemplos de polinomios --
-- ---------------------------------------------------------------------
-- Ejemplos de polinomios con coeficientes enteros:
ejPol1, ejPol2, ejPol3:: Polinomio Int
ejPol1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))
ejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))
ejPol3 = consPol 4 6 (consPol 1 2 polCero)
-- Comprobación de escritura:
-- > ejPol1
-- 3*x^4 + -5*x^2 + 3
-- > ejPol2
-- x^5 + 5*x^2 + 4*x
-- > ejPol3
-- 6*x^4 + 2*x
-- ---------------------------------------------------------------------
-- Implementación de la especificación --
-- ---------------------------------------------------------------------
-- polCero es el polinomio cero. Por ejemplo,
-- ghci> polCero
-- 0
polCero :: Polinomio a
polCero = Pol []
-- (esPolCero p) se verifica si p es el polinomio cero. Por ejemplo,
-- esPolCero polCero == True
-- esPolCero ejPol1 == False
esPolCero :: Polinomio a -> Bool
esPolCero (Pol []) = True
esPolCero _ = False
-- (consPol n b p) es el polinomio bx^n+p. Por ejemplo,
-- ejPol2 == x^5 + 5*x^2 + 4*x
-- consPol 3 0 ejPol2 == x^5 + 5*x^2 + 4*x
-- consPol 3 2 polCero == 2*x^3
-- consPol 6 7 ejPol2 == 7*x^6 + x^5 + 5*x^2 + 4*x
-- consPol 4 7 ejPol2 == x^5 + 7*x^4 + 5*x^2 + 4*x
-- consPol 5 7 ejPol2 == 8*x^5 + 5*x^2 + 4*x
consPol :: (Num a, Eq a) => Int -> a -> Polinomio a -> Polinomio a
consPol _ 0 p = p
consPol n b p@(Pol xs)
| esPolCero p = Pol (b : replicate n 0)
| n > m = Pol (b : replicate (n-m-1) 0 ++ xs)
| n < m = consPol m c (consPol n b (restoPol p))
| b+c == 0 = Pol (dropWhile (==0) (tail xs))
| otherwise = Pol ((b+c):tail xs)
where
c = coefLider p
m = grado p
-- (grado p) es el grado del polinomio p. Por ejemplo,
-- ejPol3 == 6*x^4 + 2*x
-- grado ejPol3 == 4
grado:: Polinomio a -> Int
grado (Pol []) = 0
grado (Pol xs) = length xs - 1
-- (coefLider p) es el coeficiente líder del polinomio p. Por ejemplo,
-- ejPol3 == 6*x^4 + 2*x
-- coefLider ejPol3 == 6
coefLider:: Num t => Polinomio t -> t
coefLider (Pol []) = 0
coefLider (Pol (a:_)) = a
-- (restoPol p) es el resto del polinomio p. Por ejemplo,
-- ejPol3 == 6*x^4 + 2*x
-- restoPol ejPol3 == 2*x
-- ejPol2 == x^5 + 5*x^2 + 4*x
-- restoPol ejPol2 == 5*x^2 + 4*x
restoPol :: (Num t, Eq t) => Polinomio t -> Polinomio t
restoPol (Pol []) = polCero
restoPol (Pol [_]) = polCero
restoPol (Pol (_:b:as))
| b == 0 = Pol (dropWhile (==0) as)
| otherwise = Pol (b:as)
ejPol1 :: Polinomio Int
ejPol1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))
ejPol1
3*x^4 + -5*x^2 + 3
ejPol2 :: Polinomio Int
ejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))
ejPol2
x^5 + 5*x^2 + 4*x
ejPol3 :: Polinomio Int
ejPol3 = consPol 4 6 (consPol 1 2 polCero)
ejPol3
6*x^4 + 2*x
polCero
0
esPolCero polCero
True
esPolCero ejPol1
False
ejPol2
consPol 3 0 ejPol2
x^5 + 5*x^2 + 4*x
x^5 + 5*x^2 + 4*x
consPol 3 2 polCero
2*x^3
consPol 6 7 ejPol2
7*x^6 + x^5 + 5*x^2 + 4*x
consPol 4 7 ejPol2
x^5 + 7*x^4 + 5*x^2 + 4*x
consPol 5 7 ejPol2
8*x^5 + 5*x^2 + 4*x
ejPol3
grado ejPol3
6*x^4 + 2*x
4
coefLider ejPol3
6
restoPol ejPol3
2*x
ejPol2
restoPol ejPol2
x^5 + 5*x^2 + 4*x
5*x^2 + 4*x
:m - PolRepDensa
Representaremos un polinomio mediante una lista de pares (grado,coef), ordenados en orden decreciente según el grado. Por ejemplo, el polinomio 6x^4 -5x^2 + 4x -7 se representa por [(4,6),(2,-5),(1,4),(0,-7)].
module PolRepDispersa
( Polinomio,
polCero, -- Polinomio a
esPolCero, -- Num a => Polinomio a -> Bool
consPol, -- Num a => Int -> a -> Polinomio a -> Polinomio a
grado, -- Polinomio a -> Int
coefLider, -- Num a => Polinomio a -> a
restoPol -- Polinomio a -> Polinomio a
) where
-- ---------------------------------------------------------------------
-- TAD de los polinomios mediante listas dispersas. --
-- ---------------------------------------------------------------------
newtype Polinomio a = Pol [(Int,a)]
deriving Eq
-- ---------------------------------------------------------------------
-- Escritura de los polinomios --
-- ---------------------------------------------------------------------
instance (Num t, Show t, Eq t) => Show (Polinomio t) where
show pol
| esPolCero pol = "0"
| n == 0 && esPolCero p = show a
| n == 0 = concat [show a, " + ", show p]
| n == 1 && esPolCero p = show a ++ "*x"
| n == 1 = concat [show a, "*x + ", show p]
| a == 1 && esPolCero p = "x^" ++ show n
| esPolCero p = concat [show a, "*x^", show n]
| a == 1 = concat ["x^", show n, " + ", show p]
| otherwise = concat [show a, "*x^", show n, " + ", show p]
where n = grado pol
a = coefLider pol
p = restoPol pol
-- ---------------------------------------------------------------------
-- Ejemplos de polinomios --
-- ---------------------------------------------------------------------
-- Ejemplos de polinomios con coeficientes enteros:
ejPol1, ejPol2, ejPol3:: Polinomio Int
ejPol1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))
ejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))
ejPol3 = consPol 4 6 (consPol 1 2 polCero)
-- Comprobación de escritura:
-- > ejPol1
-- 3*x^4 + -5*x^2 + 3
-- > ejPol2
-- x^5 + 5*x^2 + 4*x
-- > ejPol3
-- 6*x^4 + 2*x
-- ---------------------------------------------------------------------
-- Implementación de la especificación --
-- ---------------------------------------------------------------------
-- polCero es el polinomio cero. Por ejemplo,
-- ghci> polCero
-- 0
polCero :: Num a => Polinomio a
polCero = Pol []
-- (esPolCero p) se verifica si p es el polinomio cero. Por ejemplo,
-- esPolCero polCero == True
-- esPolCero ejPol1 == False
esPolCero :: Num a => Polinomio a -> Bool
esPolCero (Pol []) = True
esPolCero _ = False
-- (consPol n b p) es el polinomio bx^n+p. Por ejemplo,
-- ejPol2 == x^5 + 5*x^2 + 4*x
-- consPol 3 0 ejPol2 == x^5 + 5*x^2 + 4*x
-- consPol 3 2 polCero == 2*x^3
-- consPol 6 7 ejPol2 == 7*x^6 + x^5 + 5*x^2 + 4*x
-- consPol 4 7 ejPol2 == x^5 + 7*x^4 + 5*x^2 + 4*x
-- consPol 5 7 ejPol2 == 8*x^5 + 5*x^2 + 4*x
consPol :: (Num a, Eq a) => Int -> a -> Polinomio a -> Polinomio a
consPol _ 0 p = p
consPol n b p@(Pol xs)
| esPolCero p = Pol [(n,b)]
| n > m = Pol ((n,b):xs)
| n < m = consPol m c (consPol n b (Pol (tail xs)))
| b+c == 0 = Pol (tail xs)
| otherwise = Pol ((n,b+c) : tail xs)
where
c = coefLider p
m = grado p
-- (grado p) es el grado del polinomio p. Por ejemplo,
-- ejPol3 == 6*x^4 + 2*x
-- grado ejPol3 == 4
grado:: Polinomio a -> Int
grado (Pol []) = 0
grado (Pol ((n,_):_)) = n
-- (coefLider p) es el coeficiente líder del polinomio p. Por ejemplo,
-- ejPol3 == 6*x^4 + 2*x
-- coefLider ejPol3 == 6
coefLider:: Num t => Polinomio t -> t
coefLider (Pol []) = 0
coefLider (Pol ((_,b):_)) = b
-- (restoPol p) es el resto del polinomio p. Por ejemplo,
-- ejPol3 == 6*x^4 + 2*x
-- restoPol ejPol3 == 2*x
-- ejPol2 == x^5 + 5*x^2 + 4*x
-- restoPol ejPol2 == 5*x^2 + 4*x
restoPol :: Num t => Polinomio t -> Polinomio t
restoPol (Pol []) = polCero
restoPol (Pol [_]) = polCero
restoPol (Pol (_:xs)) = Pol xs
ejPol1 :: Polinomio Int
ejPol1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))
ejPol1
3*x^4 + -5*x^2 + 3
ejPol2 :: Polinomio Int
ejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))
ejPol2
x^5 + 5*x^2 + 4*x
ejPol3 :: Polinomio Int
ejPol3 = consPol 4 6 (consPol 1 2 polCero)
ejPol3
6*x^4 + 2*x
polCero
0
esPolCero polCero
True
esPolCero ejPol1
False
ejPol2
consPol 3 0 ejPol2
x^5 + 5*x^2 + 4*x
x^5 + 5*x^2 + 4*x
consPol 3 2 polCero
2*x^3
consPol 6 7 ejPol2
7*x^6 + x^5 + 5*x^2 + 4*x
consPol 4 7 ejPol2
x^5 + 7*x^4 + 5*x^2 + 4*x
consPol 5 7 ejPol2
8*x^5 + 5*x^2 + 4*x
ejPol3
grado ejPol3
6*x^4 + 2*x
4
coefLider ejPol3
6
restoPol ejPol3
2*x
ejPol2
restoPol ejPol2
x^5 + 5*x^2 + 4*x
5*x^2 + 4*x
:m - PolRepDispersa
{-# LANGUAGE FlexibleInstances #-}
module PolPropiedades where
-- Nota: Hay que elegir una implementación del TAD de polinomios
import PolRepTDA
-- import PolRepDispersa
-- import PolRepDensa
import Test.QuickCheck
-- ---------------------------------------------------------------------
-- Generador de polinomios --
-- ---------------------------------------------------------------------
-- (genPol n) es un generador de polinomios. Por ejemplo,
-- ghci> sample (genPol 1)
-- 7*x^9 + 9*x^8 + 10*x^7 + -14*x^5 + -15*x^2 + -10
-- -4*x^8 + 2*x
-- -8*x^9 + 4*x^8 + 2*x^6 + 4*x^5 + -6*x^4 + 5*x^2 + -8*x
-- -9*x^9 + x^5 + -7
-- 8*x^10 + -9*x^7 + 7*x^6 + 9*x^5 + 10*x^3 + -1*x^2
-- 7*x^10 + 5*x^9 + -5
-- -8*x^10 + -7
-- -5*x
-- 5*x^10 + 4*x^4 + -3
-- 3*x^3 + -4
-- 10*x
genPol :: Int -> Gen (Polinomio Int)
genPol 0 = return polCero
genPol _ = do
n <- choose (0,10)
b <- choose (-10,10)
p <- genPol (div n 2)
return (consPol n b p)
instance Arbitrary (Polinomio Int) where
arbitrary = sized genPol
-- ---------------------------------------------------------------------
-- Propiedades --
-- ---------------------------------------------------------------------
-- Propiedad. polCero es el polinomio cero.
prop_polCero_es_cero :: Bool
prop_polCero_es_cero =
esPolCero polCero
-- Comprobación.
-- ghci> quickCheck prop_polCero_es_cero
-- +++ OK, passed 100 tests.
-- Propiedad. Si n es mayor que el grado de p y b no es cero, entonces
-- (consPol n b p) es un polinomio distinto del cero.
prop_consPol_no_cero :: Int -> Int -> Polinomio Int -> Property
prop_consPol_no_cero n b p =
n > grado p && b /= 0 ==>
not (esPolCero (consPol n b p))
-- Comprobación.
-- ghci> quickCheck prop_consPol_no_cero
-- +++ OK, passed 100 tests.
-- Propiedad. (consPol (grado p) (coefLider p) (restoPol p)) es igual a p.
prop_consPol :: Polinomio Int -> Bool
prop_consPol p =
consPol (grado p) (coefLider p) (restoPol p) == p
-- Comprobación
-- > quickCheck prop_consPol
-- +++ OK, passed 100 tests.
-- Propiedad. Si n es mayor que el grado de p y b no es cero, entonces
-- el grado de (consPol n b p) es n.
prop_grado :: Int -> Int -> Polinomio Int -> Property
prop_grado n b p =
n > grado p && b /= 0 ==>
grado (consPol n b p) == n
-- Comprobación.
-- ghci> quickCheck prop_grado
-- +++ OK, passed 100 tests.
-- Propiedad. Si n es mayor que el grado de p y b no es cero, entonces
-- el coeficiente líder de (consPol n b p) es b.
prop_coefLider :: Int -> Int -> Polinomio Int -> Property
prop_coefLider n b p =
n > grado p && b /= 0 ==>
coefLider (consPol n b p) == b
-- Comprobación.
-- ghci> quickCheck prop_coefLider
-- +++ OK, passed 100 tests.
-- Propiedad. Si n es mayor que el grado de p y b no es cero, entonces
-- el resto de (consPol n b p) es p.
prop_restoPol :: Int -> Int -> Polinomio Int -> Property
prop_restoPol n b p =
n > grado p && b /= 0 ==>
restoPol (consPol n b p) == p
-- Comprobación.
-- ghci> quickCheck prop_restoPol
-- +++ OK, passed 100 tests.
import Test.QuickCheck
quickCheck prop_polCero_es_cero
quickCheck prop_consPol_no_cero
quickCheck prop_consPol
quickCheck prop_grado
quickCheck prop_coefLider
quickCheck prop_restoPol
+++ OK, passed 1 test.
+++ OK, passed 100 tests; 264 discarded.
+++ OK, passed 100 tests.
+++ OK, passed 100 tests; 234 discarded.
+++ OK, passed 100 tests; 286 discarded.
+++ OK, passed 100 tests; 339 discarded.
:m - PolPropiedades
module PolOperaciones (module Pol, module PolOperaciones) where
-- ---------------------------------------------------------------------
-- Importación de librerías --
-- ---------------------------------------------------------------------
-- Nota: Hay que elegir una implementación del TAD de los polinomios.
import PolRepTDA as Pol
-- import PolRepDispersa as Pol
-- import PolRepDensa as Pol
import Test.QuickCheck
-- ---------------------------------------------------------------------
-- Ejemplos --
-- ---------------------------------------------------------------------
-- Ejemplos de polinomios con coeficientes enteros:
ejPol1, ejPol2, ejPol3, ejTerm :: Polinomio Int
ejPol1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))
ejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))
ejPol3 = consPol 4 6 (consPol 1 2 polCero)
ejTerm = consPol 1 4 polCero
-- ---------------------------------------------------------------------
-- Generador de polinomios --
-- ---------------------------------------------------------------------
-- (genPol n) es un generador de polinomios. Por ejemplo,
-- ghci> sample (genPol 1)
-- 7*x^9 + 9*x^8 + 10*x^7 + -14*x^5 + -15*x^2 + -10
-- -4*x^8 + 2*x
-- -8*x^9 + 4*x^8 + 2*x^6 + 4*x^5 + -6*x^4 + 5*x^2 + -8*x
-- -9*x^9 + x^5 + -7
-- 8*x^10 + -9*x^7 + 7*x^6 + 9*x^5 + 10*x^3 + -1*x^2
-- 7*x^10 + 5*x^9 + -5
-- -8*x^10 + -7
-- -5*x
-- 5*x^10 + 4*x^4 + -3
-- 3*x^3 + -4
-- 10*x
genPol :: (Arbitrary a, Num a, Eq a) => Int -> Gen (Polinomio a)
genPol 0 = return polCero
genPol _ = do
n <- choose (0,10)
b <- arbitrary
p <- genPol (div n 2)
return (consPol n b p)
instance (Arbitrary a, Num a, Eq a) => Arbitrary (Polinomio a) where
arbitrary = sized genPol
-- ---------------------------------------------------------------------
-- Funciones sobre términos --
-- ---------------------------------------------------------------------
-- (creaTermino n a) es el término a*x^n. Por ejemplo,
-- creaTermino 2 5 == 5*x^2
creaTermino :: (Num t, Eq t) => Int -> t -> Polinomio t
creaTermino n a = consPol n a polCero
-- (termLider p) es el término líder del polinomio p. Por ejemplo,
-- ejPol2 == x^5 + 5*x^2 + 4*x
-- termLider ejPol2 == x^5
termLider :: (Num t, Eq t) => Polinomio t -> Polinomio t
termLider p = creaTermino (grado p) (coefLider p)
-- ---------------------------------------------------------------------
-- Suma de polinomios --
-- ---------------------------------------------------------------------
-- (sumaPol p q) es la suma de los polinomios p y q. Por ejemplo,
-- ejPol1 == 3*x^4 + -5*x^2 + 3
-- ejPol2 == x^5 + 5*x^2 + 4*x
-- sumaPol ejPol1 ejPol2 == x^5 + 3*x^4 + 4*x + 3
sumaPol :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a
sumaPol p q
| esPolCero p = q
| esPolCero q = p
| n1 > n2 = consPol n1 a1 (sumaPol r1 q)
| n1 < n2 = consPol n2 a2 (sumaPol p r2)
| otherwise = consPol n1 (a1+a2) (sumaPol r1 r2)
where n1 = grado p
a1 = coefLider p
r1 = restoPol p
n2 = grado q
a2 = coefLider q
r2 = restoPol q
-- Propiedad. El polinomio cero es el elemento neutro de la suma.
prop_neutroSumaPol :: Polinomio Int -> Bool
prop_neutroSumaPol p =
sumaPol polCero p == p
-- Comprobación con QuickCheck.
-- ghci> quickCheck prop_neutroSumaPol
-- OK, passed 100 tests.
-- Propiedad. La suma es conmutativa.
prop_conmutativaSuma :: Polinomio Int -> Polinomio Int -> Bool
prop_conmutativaSuma p q =
sumaPol p q == sumaPol q p
-- Comprobación:
-- ghci> quickCheck prop_conmutativaSuma
-- OK, passed 100 tests.
-- ---------------------------------------------------------------------
-- Producto de polinomios --
-- ---------------------------------------------------------------------
-- (multPorTerm t p) es el producto del término t por el polinomio
-- p. Por ejemplo,
-- ejTerm == 4*x
-- ejPol2 == x^5 + 5*x^2 + 4*x
-- multPorTerm ejTerm ejPol2 == 4*x^6 + 20*x^3 + 16*x^2
multPorTerm :: (Num t, Eq t) => Polinomio t -> Polinomio t -> Polinomio t
multPorTerm term pol
| esPolCero pol = polCero
| otherwise = consPol (n+m) (a*b) (multPorTerm term r)
where n = grado term
a = coefLider term
m = grado pol
b = coefLider pol
r = restoPol pol
-- (multPol p q) es el producto de los polinomios p y q. Por
-- ejemplo,
-- ghci> ejPol1
-- 3*x^4 + -5*x^2 + 3
-- ghci> ejPol2
-- x^5 + 5*x^2 + 4*x
-- ghci> multPol ejPol1 ejPol2
-- 3*x^9 + -5*x^7 + 15*x^6 + 15*x^5 + -25*x^4 + -20*x^3 + 15*x^2 + 12*x
multPol :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a
multPol p q
| esPolCero p = polCero
| otherwise = sumaPol (multPorTerm (termLider p) q)
(multPol (restoPol p) q)
-- Propiedad. El producto de polinomios es conmutativo.
prop_conmutativaProducto :: Polinomio Int -> Polinomio Int -> Bool
prop_conmutativaProducto p q =
multPol p q == multPol q p
-- La comprobación es
-- ghci> quickCheck prop_conmutativaProducto
-- OK, passed 100 tests.
-- El producto es distributivo respecto de la suma.
prop_distributivaProductoSuma :: Polinomio Int -> Polinomio Int
-> Polinomio Int -> Bool
prop_distributivaProductoSuma p q r =
multPol p (sumaPol q r) == sumaPol (multPol p q) (multPol p r)
-- Comprobación:
-- ghci> quickCheck prop_distributivaProductoSuma
-- OK, passed 100 tests.
-- polUnidad es el polinomio unidad. Por ejemplo,
-- ghci> polUnidad
-- 1
polUnidad :: (Num t, Eq t) => Polinomio t
polUnidad = consPol 0 1 polCero
-- Propiedad. El polinomio unidad es el elemento neutro del producto.
prop_polUnidad :: Polinomio Int -> Bool
prop_polUnidad p =
multPol p polUnidad == p
-- Comprobación:
-- ghci> quickCheck prop_polUnidad
-- OK, passed 100 tests.
-- ---------------------------------------------------------------------
-- Valor de un polinomio en un punto --
-- ---------------------------------------------------------------------
-- (valor p c) es el valor del polinomio p al sustituir su variable por
-- c. Por ejemplo,
-- ejPol1 == 3*x^4 + -5*x^2 + 3
-- valor ejPol1 0 == 3
-- valor ejPol1 1 == 1
-- valor ejPol1 (-2) == 31
valor:: (Num a, Eq a) => Polinomio a -> a -> a
valor p c
| esPolCero p = 0
| otherwise = b*c^n + valor r c
where n = grado p
b = coefLider p
r = restoPol p
-- ---------------------------------------------------------------------
-- Verificación de raices de polinomios --
-- ---------------------------------------------------------------------
-- (esRaiz c p) se verifica si c es una raiz del polinomio p. por
-- ejemplo,
-- ejPol3 == 6*x^4 + 2*x
-- esRaiz 1 ejPol3 == False
-- esRaiz 0 ejPol3 == True
esRaiz :: (Num a, Eq a) => a -> Polinomio a -> Bool
esRaiz c p = valor p c == 0
-- ---------------------------------------------------------------------
-- Derivación de polinomios --
-- ---------------------------------------------------------------------
-- (derivada p) es la derivada del polinomio p. Por ejemplo,
-- ejPol2 == x^5 + 5*x^2 + 4*x
-- derivada ejPol2 == 5*x^4 + 10*x + 4
derivada :: (Eq a, Num a) => Polinomio a -> Polinomio a
derivada p
| n == 0 = polCero
| otherwise = consPol (n-1) (b * fromIntegral n) (derivada r)
where n = grado p
b = coefLider p
r = restoPol p
-- Propiedad. La derivada de la suma es la suma de las derivadas.
prop_derivada :: Polinomio Int -> Polinomio Int -> Bool
prop_derivada p q =
derivada (sumaPol p q) == sumaPol (derivada p) (derivada q)
-- Comprobación
-- ghci> quickCheck prop_derivada
-- OK, passed 100 tests.
-- ---------------------------------------------------------------------
-- Resta de polinomios --
-- ---------------------------------------------------------------------
-- (resta p q) es la el polinomio obtenido restándole a p el q. Por
-- ejemplo,
-- ejPol1 == 3*x^4 + -5*x^2 + 3
-- ejPol2 == x^5 + 5*x^2 + 4*x
-- restaPol ejPol1 ejPol2 == -1*x^5 + 3*x^4 + -10*x^2 + -4*x + 3
restaPol :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a
restaPol p q =
sumaPol p (multPorTerm (creaTermino 0 (-1)) q)
import Test.QuickCheck
creaTermino 2 5
5*x^2
ejPol2
termLider ejPol2
x^5 + 5*x^2 + 4*x
x^5
ejPol1
ejPol2
sumaPol ejPol1 ejPol2
3*x^4 + -5*x^2 + 3
x^5 + 5*x^2 + 4*x
x^5 + 3*x^4 + 4*x + 3
quickCheck prop_neutroSumaPol
+++ OK, passed 100 tests.
quickCheck prop_conmutativaSuma
+++ OK, passed 100 tests.
ejTerm
ejPol2
multPorTerm ejTerm ejPol2
4*x
x^5 + 5*x^2 + 4*x
4*x^6 + 20*x^3 + 16*x^2
ejPol1
ejPol2
multPol ejPol1 ejPol2
3*x^4 + -5*x^2 + 3
x^5 + 5*x^2 + 4*x
3*x^9 + -5*x^7 + 15*x^6 + 15*x^5 + -25*x^4 + -20*x^3 + 15*x^2 + 12*x
quickCheck prop_conmutativaProducto
+++ OK, passed 100 tests.
quickCheck prop_distributivaProductoSuma
+++ OK, passed 100 tests.
polUnidad
1
quickCheck prop_polUnidad
+++ OK, passed 100 tests.
ejPol1
valor ejPol1 0
valor ejPol1 1
valor ejPol1 (-2)
3*x^4 + -5*x^2 + 3
3
1
31
ejPol3
esRaiz 1 ejPol3
esRaiz 0 ejPol3
6*x^4 + 2*x
False
True
ejPol2
derivada ejPol2
x^5 + 5*x^2 + 4*x
5*x^4 + 10*x + 4
quickCheck prop_derivada
+++ OK, passed 100 tests.
Nota Se borran los ficheros de los módulos usados
:! rm -f *.hs *.hi *.o *.dyn_*