Tema 21: El TAD de los polinomios


José A. Alonso
Departamento de Ciencias de la Computación e I.A.
Universidad de Sevilla
Sevilla, 17 de agosto de 2019

Notas:

In [1]:
:opt no-lint

Especificación del TAD de los polinomios

Signatura del TAD de los polinomios

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

  • Definición:
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
  • Evaluación:
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

Propiedades del TAD de los polinomios

  • 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

Implementación del TAD de los polinomios

Los polinomios como tipo de dato algebraico

In [2]:
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
  • Ejemplos
In [3]:
ejPol1 :: Polinomio Int
ejPol1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))
ejPol1
3*x^4 + -5*x^2 + 3
In [4]:
ejPol2 :: Polinomio Int
ejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))
ejPol2
x^5 + 5*x^2 + 4*x
In [5]:
ejPol3 :: Polinomio Int
ejPol3 = consPol 4 6 (consPol 1 2 polCero)
ejPol3
6*x^4 + 2*x
In [6]:
polCero
0
In [7]:
esPolCero polCero
True
In [8]:
esPolCero ejPol1
False
In [9]:
ejPol2               
consPol 3 0 ejPol2
x^5 + 5*x^2 + 4*x
x^5 + 5*x^2 + 4*x
In [10]:
consPol 3 2 polCero
2*x^3
In [11]:
consPol 6 7 ejPol2
7*x^6 + x^5 + 5*x^2 + 4*x
In [12]:
consPol 4 7 ejPol2
x^5 + 7*x^4 + 5*x^2 + 4*x
In [13]:
consPol 5 7 ejPol2
8*x^5 + 5*x^2 + 4*x
In [14]:
ejPol3        
grado ejPol3
6*x^4 + 2*x
4
In [15]:
coefLider ejPol3
6
In [16]:
restoPol ejPol3
2*x
In [17]:
ejPol2           
restoPol ejPol2
x^5 + 5*x^2 + 4*x
5*x^2 + 4*x
  • Se elimina la implementación.
In [18]:
:m - PolRepTDA

Los polinomios como listas densas

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]

In [19]:
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)
  • Ejemplos
In [20]:
ejPol1 :: Polinomio Int
ejPol1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))
ejPol1
3*x^4 + -5*x^2 + 3
In [21]:
ejPol2 :: Polinomio Int
ejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))
ejPol2
x^5 + 5*x^2 + 4*x
In [22]:
ejPol3 :: Polinomio Int
ejPol3 = consPol 4 6 (consPol 1 2 polCero)
ejPol3
6*x^4 + 2*x
In [23]:
polCero
0
In [24]:
esPolCero polCero
True
In [25]:
esPolCero ejPol1
False
In [26]:
ejPol2               
consPol 3 0 ejPol2
x^5 + 5*x^2 + 4*x
x^5 + 5*x^2 + 4*x
In [27]:
consPol 3 2 polCero
2*x^3
In [28]:
consPol 6 7 ejPol2
7*x^6 + x^5 + 5*x^2 + 4*x
In [29]:
consPol 4 7 ejPol2
x^5 + 7*x^4 + 5*x^2 + 4*x
In [30]:
consPol 5 7 ejPol2
8*x^5 + 5*x^2 + 4*x
In [31]:
ejPol3        
grado ejPol3
6*x^4 + 2*x
4
In [32]:
coefLider ejPol3
6
In [33]:
restoPol ejPol3
2*x
In [34]:
ejPol2           
restoPol ejPol2
x^5 + 5*x^2 + 4*x
5*x^2 + 4*x
  • Se elimina la implementación.
In [35]:
:m - PolRepDensa

Los polinomios como listas dispersas

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

In [36]:
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
  • Ejemplos
In [37]:
ejPol1 :: Polinomio Int
ejPol1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))
ejPol1
3*x^4 + -5*x^2 + 3
In [38]:
ejPol2 :: Polinomio Int
ejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))
ejPol2
x^5 + 5*x^2 + 4*x
In [39]:
ejPol3 :: Polinomio Int
ejPol3 = consPol 4 6 (consPol 1 2 polCero)
ejPol3
6*x^4 + 2*x
In [40]:
polCero
0
In [41]:
esPolCero polCero
True
In [42]:
esPolCero ejPol1
False
In [43]:
ejPol2               
consPol 3 0 ejPol2
x^5 + 5*x^2 + 4*x
x^5 + 5*x^2 + 4*x
In [44]:
consPol 3 2 polCero
2*x^3
In [45]:
consPol 6 7 ejPol2
7*x^6 + x^5 + 5*x^2 + 4*x
In [46]:
consPol 4 7 ejPol2
x^5 + 7*x^4 + 5*x^2 + 4*x
In [47]:
consPol 5 7 ejPol2
8*x^5 + 5*x^2 + 4*x
In [48]:
ejPol3        
grado ejPol3
6*x^4 + 2*x
4
In [49]:
coefLider ejPol3
6
In [50]:
restoPol ejPol3
2*x
In [51]:
ejPol2           
restoPol ejPol2
x^5 + 5*x^2 + 4*x
5*x^2 + 4*x
  • Se elimina la implementación.
In [52]:
:m - PolRepDispersa

Comprobación de las implementaciones con QuickCheck

In [53]:
{-# 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.
In [54]:
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.
  • Se elimina el módulo
In [55]:
:m - PolPropiedades

Operaciones con polinomios

In [56]:
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)
In [57]:
import Test.QuickCheck
In [58]:
creaTermino 2 5
5*x^2
In [59]:
ejPol2
termLider ejPol2
x^5 + 5*x^2 + 4*x
x^5
In [60]:
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
In [61]:
quickCheck prop_neutroSumaPol
+++ OK, passed 100 tests.
In [62]:
quickCheck prop_conmutativaSuma
+++ OK, passed 100 tests.
In [63]:
ejTerm                
ejPol2                
multPorTerm ejTerm ejPol2
4*x
x^5 + 5*x^2 + 4*x
4*x^6 + 20*x^3 + 16*x^2
In [64]:
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
In [65]:
quickCheck prop_conmutativaProducto
+++ OK, passed 100 tests.
In [66]:
quickCheck prop_distributivaProductoSuma
+++ OK, passed 100 tests.
In [67]:
polUnidad
1
In [68]:
quickCheck prop_polUnidad
+++ OK, passed 100 tests.
In [69]:
ejPol1             
valor ejPol1 0     
valor ejPol1 1     
valor ejPol1 (-2)
3*x^4 + -5*x^2 + 3
3
1
31
In [70]:
ejPol3           
esRaiz 1 ejPol3  
esRaiz 0 ejPol3
6*x^4 + 2*x
False
True
In [71]:
ejPol2           
derivada ejPol2
x^5 + 5*x^2 + 4*x
5*x^4 + 10*x + 4
In [72]:
quickCheck prop_derivada
+++ OK, passed 100 tests.

Nota Se borran los ficheros de los módulos usados

In [73]:
:! rm -f *.hs *.hi *.o *.dyn_*