Tema 21: El TAD de los polinomios

1 Especificación del TAD de los polinomios

1.1 Signatura del TAD de los polinomios

Signatura del TAD de los polinomios

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:

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
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

1.2 Propiedades del TAD de los polinomios

2 Implementación del TAD de los polinomios

2.1 Los polinomios como tipo de dato algebraico

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 a => Polinomio a -> a                           
    restoPol   -- (Num a, Eq a) => Polinomio a -> Polinomio a
  ) where
ConsPol 4 6 
  (ConsPol 2 (-5) 
     (ConsPol 1 4 
        (ConsPol 0 (-7) PolCero)))
data Polinomio a = PolCero 
                 | ConsPol Int a (Polinomio a)
                 deriving Eq
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) = concat [show b,"*x"]
    show (ConsPol 1 b p)       = concat [show b,"*x + ",show p] 
    show (ConsPol n 1 PolCero) = concat ["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] 
ghci> polCero
0
polCero :: Polinomio a
polCero = PolCero
esPolCero polCero  ==  True
esPolCero ejPol1   ==  False
esPolCero :: Polinomio a -> Bool
esPolCero PolCero = True
esPolCero _       = False
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
ejPol3        ==  6*x^4 + 2*x
grado ejPol3  ==  4
grado:: Polinomio a -> Int
grado PolCero         = 0
grado (ConsPol n _ _) = n
coefLider ejPol3  ==  6
coefLider:: Num t => Polinomio t -> t
coefLider PolCero         = 0
coefLider (ConsPol _ b _) = b
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 a, Eq a) => Polinomio t -> Polinomio t
restoPol PolCero         = PolCero
restoPol (ConsPol _ _ p) = p

2.2 Los polinomios como listas dispersas

module PolRepDispersa
  ( 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
[6,0,-2,4,-7]
data Polinomio a = Pol [a] 
                   deriving Eq
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 = concat [show a,"*x"]
      | n == 1                = concat [show a,"*x + ",show p] 
      | a == 1 && esPolCero p = concat ["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
ghci> polCero
0
polCero :: Polinomio a
polCero = Pol []
esPolCero polCero  ==  True
esPolCero ejPol1   ==  False
esPolCero :: Polinomio a -> Bool
esPolCero (Pol []) = True
esPolCero _        = False
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
ejPol3        ==  6*x^4 + 2*x
grado ejPol3  ==  4
grado:: Polinomio a -> Int
grado (Pol []) = 0
grado (Pol xs) = length xs - 1
coefLider ejPol3  ==  6
coefLider:: Num t => Polinomio t -> t
coefLider (Pol [])    = 0
coefLider (Pol (a:_)) = a 
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)

2.3 Los polinomios como listas densas

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
[(4,6),(2,-5),(1,4),(0,-7)]. 
data Polinomio a = Pol [(Int,a)] 
                   deriving Eq
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 = concat [show a,"*x"]
      | n == 1                = concat [show a,"*x + ",show p] 
      | a == 1 && esPolCero p = concat ["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
ghci> polCero
0
polCero :: Polinomio a
polCero = Pol []
esPolCero polCero  ==  True
esPolCero ejPol1   ==  False
esPolCero :: Polinomio a -> Bool
esPolCero (Pol []) = True
esPolCero _        = False
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
ejPol3        ==  6*x^4 + 2*x
grado ejPol3  ==  4
grado:: Polinomio a -> Int
grado (Pol [])        = 0
grado (Pol ((n,_):_)) = n
coefLider ejPol3  ==  6
coefLider:: Num t => Polinomio t -> t
coefLider (Pol [])        = 0
coefLider (Pol ((_,b):_)) = b
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 (_:xs)) = Pol xs

3 Comprobación de las implementaciones con QuickCheck

3.1 Librerías auxiliares

import PolRepTDA
-- import PolRepDispersa
-- import PolRepDensa
import Test.QuickCheck
import Test.Framework
import Test.Framework.Providers.QuickCheck2

3.2 Generador de polinomios

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
genPol :: Int -> Gen (Polinomio Int)
genPol 0 = return polCero
genPol n = 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

3.3 Especificación de las propiedades de los polinomios

prop_polCero_es_cero :: Bool
prop_polCero_es_cero =
    esPolCero polCero
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))
prop_consPol :: Polinomio Int -> Bool
prop_consPol p =
    consPol (grado p) (coefLider p) (restoPol p) == p
prop_grado :: Int -> Int -> Polinomio Int -> Property
prop_grado n b p = 
    n > grado p && b /= 0 ==> 
      grado (consPol n b p) == n 
prop_coefLider :: Int -> Int -> Polinomio Int -> Property
prop_coefLider n b p = 
    n > grado p && b /= 0 ==> 
      coefLider (consPol n b p) == b 
prop_restoPol :: Int -> Int -> Polinomio Int -> Property
prop_restoPol n b p = 
    n > grado p && b /= 0 ==> 
      restoPol (consPol n b p) == p 

3.4 Comprobación de las propiedades

Procedimiento de comprobación

compruebaPropiedades = 
    defaultMain 
        [testGroup "Propiedades del TAD polinomio:"
          [testProperty "P1" prop_polCero_es_cero,
           testProperty "P2" prop_consPol_no_cero,
           testProperty "P3" prop_consPol,
           testProperty "P4" prop_grado,
           testProperty "P5" prop_coefLider,
           testProperty "P6" prop_restoPol]]

Comprobación de las propiedades de los polinomios

ghci> compruebaPropiedades 
Propiedades del TAD polinomio::
  P1: [OK, passed 100 tests]
  P2: [OK, passed 100 tests]
  P3: [OK, passed 100 tests]
  P4: [OK, passed 100 tests]
  P5: [OK, passed 100 tests]
  P6: [OK, passed 100 tests]

         Properties  Total      
 Passed  6           6          
 Failed  0           0          
 Total   6           6  

4 Operaciones con polinomios

import PolRepTDA
-- import PolRepDispersa
-- import PolRepDensa
import Test.QuickCheck
import Test.Framework
import Test.Framework.Providers.QuickCheck2

Funciones sobre términos

creaTermino:: (Num t, Eq t) => Int -> t -> Polinomio t
creaTermino n a = consPol n a polCero
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

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

Propiedades de la suma de polinomios

prop_neutroSumaPol :: Polinomio Int -> Bool
prop_neutroSumaPol p = 
    sumaPol polCero p == p
prop_conmutativaSuma :: Polinomio Int -> Polinomio Int 
                        -> Bool
prop_conmutativaSuma p q = 
    sumaPol p q == sumaPol q p

Producto de polinomios

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    
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)

Propiedades del producto polinomios

prop_conmutativaProducto :: Polinomio Int 
                            -> Polinomio Int -> Bool
prop_conmutativaProducto p q = 
    multPol p q == multPol q p
prop_distributiva :: Polinomio Int -> Polinomio Int 
                     -> Polinomio Int -> Bool
prop_distributiva p q r =
    multPol p (sumaPol q r) == 
    sumaPol (multPol p q) (multPol p r)

Polinomio unidad

ghci> polUnidad
1
polUnidad:: (Num t, Eq t) => Polinomio t
polUnidad = consPol 0 1 polCero
prop_polUnidad :: Polinomio Int -> Bool
prop_polUnidad p = 
    multPol p polUnidad == p

Valor de un polinomio en un punto

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

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

ejPol2           ==  x^5 + 5*x^2 + 4*x
derivada ejPol2  ==  5*x^4 + 10*x + 4
derivada :: Polinomio Int -> Polinomio Int
derivada p 
    | n == 0     = polCero
    | otherwise  = consPol (n-1) (n*b) (derivada r)
    where n = grado p
          b = coefLider p
          r = restoPol p

Propiedades de las derivadas de polinomios

prop_derivada :: Polinomio Int -> Polinomio Int -> Bool
prop_derivada p q =
    derivada (sumaPol p q) == 
    sumaPol (derivada p) (derivada q)


Universidad de Sevilla

José A. Alonso Jiménez
Grupo de Lógica Computacional
Dpto. de Ciencias de la Computación e I.A.
Universidad de Sevilla