Polinomios

El tipo abstracto de datos de los polinomios

PorJosé A. Alonso 17-abril-20232-mayo-2023

1. El tipo abstracto de datos de los polinomios

Un polinomio es una expresión matemática compuesta por una suma de términos, donde cada término es el producto de un coeficiente y una variable elevada a una potencia. Por ejemplo, el polinomio 3x^2+2x-1 tiene un término de segundo grado (3x^2), un término de primer grado (2x) y un término constante (-1).

Las operaciones que definen al tipo abstracto de datos (TAD) de los polinomios (cuyos coeficientes son del tipo a) son las siguientes:

   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

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

tales que

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.

Por ejemplo, el polinomio

   3*x^4 + -5*x^2 + 3

1	3x^4 + -5x^2 + 3

se representa por

   consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))

1	consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))

Las operaciones tienen que verificar las siguientes propiedades:

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

2. Los polinomios en Haskell

2.1. El tipo abstracto de datos de los polinomios en Haskell

El TAD de los polinomios se encuentra en el módulo Polinomio.hs cuyo contenido es el siguiente:

module TAD.Polinomio
  ( 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

import TAD.PolRepTDA
-- import TAD.PolRepDensa
-- import TAD.PolRepDispersa

module TAD.Polinomio

( 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

import TAD.PolRepTDA

-- import TAD.PolRepDensa

-- import TAD.PolRepDispersa

Para usar el TAD hay que usar una implementación concreta. En principio, consideraremos las siguientes:

mediante tipo de dato algebraico,
mediante listas densas y
mediante listas dispersas.

Hay que elegir la que se desee utilizar, descomentándola y comentando las otras.

2.2. Implementación de los polinomios mediante tipos de datos algebraicos

Representamos un polinomio mediante los constructores ConsPol y
PolCero. Por ejemplo, el polinomio

   6x^4 -5x^2 + 4x -7

1	6x^4 -5x^2 + 4x -7

se representa por

   ConsPol 4 6 (ConsPol 2 (-5) (ConsPol 1 4 (ConsPol 0 (-7) PolCero)))

1	ConsPol 4 6 (ConsPol 2 (-5) (ConsPol 1 4 (ConsPol 0 (-7) PolCero)))

La implementación se encuentra en el módulo PolRepTDA.hs cuyo contenido es el siguiente:

{-# LANGUAGE TemplateHaskell #-}
{-# OPTIONS_GHC -fno-warn-unused-top-binds #-}

module TAD.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

import Test.QuickCheck

-- Polinomio como tipo de dato algebra
data Polinomio a = PolCero
                 | ConsPol Int a (Polinomio a)
  deriving Eq

-- (escribePol p) es la cadena correspondiente al polinomio p. Por
-- ejemplo,
--    λ> escribePol (consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero)))
--    "3*x^4 + -5*x^2 + 3"
escribePol :: (Num a, Show a, Eq a) => Polinomio a -> String
escribePol PolCero               = "0"
escribePol (ConsPol 0 b PolCero) = show b
escribePol (ConsPol 0 b p)       = concat [show b, " + ", escribePol p]
escribePol (ConsPol 1 b PolCero) = show b ++ "*x"
escribePol (ConsPol 1 b p)       = concat [show b, "*x + ", escribePol p]
escribePol (ConsPol n 1 PolCero) = "x^" ++ show n
escribePol (ConsPol n b PolCero) = concat [show b, "*x^", show n]
escribePol (ConsPol n 1 p)       = concat ["x^", show n, " + ", escribePol p]
escribePol (ConsPol n b p)       = concat [show b, "*x^", show n, " + ", escribePol p]

-- Procedimiento de escritura de polinomios.
instance (Num a, Show a, Eq a) => Show (Polinomio a) where
  show = escribePol

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

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

-- Generador de polinomios                                          --
-- =======================

-- genPolinomio es un generador de polinomios. Por ejemplo,
--    λ> 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 :: (Num a, Arbitrary 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 (Num a, Arbitrary a, Eq a) => Arbitrary (Polinomio a) where
  arbitrary = sized genPol

-- Propiedades de los polinomios
-- =============================

-- polCero es el polinomio cero.
prop_polCero_es_cero :: Bool
prop_polCero_es_cero =
  esPolCero polCero

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

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

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

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

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

-- Verificación
-- ============

return []

verificaPol :: IO Bool
verificaPol = $quickCheckAll

-- La verificación es
--    λ> verificaPol
--    === prop_polCero_es_cero from PolPropiedades.hs:53 ===
--    +++ OK, passed 1 test.
--
--    === prop_consPol_no_cero from PolPropiedades.hs:63 ===
--    +++ OK, passed 100 tests; 251 discarded.
--
--    === prop_consPol from PolPropiedades.hs:73 ===
--    +++ OK, passed 100 tests.
--
--    === prop_grado from PolPropiedades.hs:83 ===
--    +++ OK, passed 100 tests; 321 discarded.
--
--    === prop_coefLider from PolPropiedades.hs:94 ===
--    +++ OK, passed 100 tests; 340 discarded.
--
--    === prop_restoPol from PolPropiedades.hs:105 ===
--    +++ OK, passed 100 tests; 268 discarded.
--
--    True

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

{-# LANGUAGE TemplateHaskell #-}

{-# OPTIONS_GHC -fno-warn-unused-top-binds #-}

module TAD.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

import Test.QuickCheck

-- Polinomio como tipo de dato algebra

data Polinomio a = PolCero

| ConsPol Int a (Polinomio a)

deriving Eq

-- (escribePol p) es la cadena correspondiente al polinomio p. Por

-- ejemplo,

-- λ> escribePol (consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero)))

-- "3*x^4 + -5*x^2 + 3"

escribePol :: (Num a, Show a, Eq a) => Polinomio a -> String

escribePol PolCero = "0"

escribePol (ConsPol 0 b PolCero) = show b

escribePol (ConsPol 0 b p) = concat [show b, " + ", escribePol p]

escribePol (ConsPol 1 b PolCero) = show b ++ "*x"

escribePol (ConsPol 1 b p) = concat [show b, "*x + ", escribePol p]

escribePol (ConsPol n 1 PolCero) = "x^" ++ show n

escribePol (ConsPol n b PolCero) = concat [show b, "*x^", show n]

escribePol (ConsPol n 1 p) = concat ["x^", show n, " + ", escribePol p]

escribePol (ConsPol n b p) = concat [show b, "*x^", show n, " + ", escribePol p]

-- Procedimiento de escritura de polinomios.

instance (Num a, Show a, Eq a) => Show (Polinomio a) where

show = escribePol

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

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

-- Generador de polinomios --

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

-- genPolinomio es un generador de polinomios. Por ejemplo,

-- λ> 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 :: (Num a, Arbitrary 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 (Num a, Arbitrary a, Eq a) => Arbitrary (Polinomio a) where

arbitrary = sized genPol

-- Propiedades de los polinomios

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

-- polCero es el polinomio cero.

prop_polCero_es_cero :: Bool

prop_polCero_es_cero =

esPolCero polCero

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

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

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

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

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

-- Verificación

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

return []

verificaPol :: IO Bool

verificaPol = $quickCheckAll

-- La verificación es

-- λ> verificaPol

-- === prop_polCero_es_cero from PolPropiedades.hs:53 ===

-- +++ OK, passed 1 test.

-- === prop_consPol_no_cero from PolPropiedades.hs:63 ===

-- +++ OK, passed 100 tests; 251 discarded.

-- === prop_consPol from PolPropiedades.hs:73 ===

-- +++ OK, passed 100 tests.

-- === prop_grado from PolPropiedades.hs:83 ===

-- +++ OK, passed 100 tests; 321 discarded.

-- === prop_coefLider from PolPropiedades.hs:94 ===

-- +++ OK, passed 100 tests; 340 discarded.

-- === prop_restoPol from PolPropiedades.hs:105 ===

-- +++ OK, passed 100 tests; 268 discarded.

-- True

2.3. Implementación de polinomios mediante 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

1	6x^4 -5x^2 + 4x -7

se representa por

   [6,0,-2,4,-7]

1	[6,0,-2,4,-7]

En la representación se supone que, si la lista no es vacía, su primer elemento es distinto de cero.

La implementación se encuentra en el módulo PolRepDensa.hs cuyo contenido es el siguiente:

{-# LANGUAGE TemplateHaskell #-}
{-# OPTIONS_GHC -fno-warn-unused-top-binds #-}

module TAD.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

import Test.QuickCheck

newtype Polinomio a = Pol [a]
  deriving Eq

-- (escribePol p) es la cadena correspondiente al polinomio p. Por
-- ejemplo,
--    λ> escribePol (consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero)))
--    "3*x^4 + -5*x^2 + 3"
escribePol :: (Num a, Show a, Eq a) => Polinomio a -> String
escribePol pol
  | esPolCero pol         = "0"
  | n == 0 && esPolCero p = show a
  | n == 0                = concat [show a, " + ", escribePol p]
  | n == 1 && esPolCero p = show a ++ "*x"
  | n == 1                = concat [show a, "*x + ", escribePol p]
  | a == 1 && esPolCero p = "x^" ++ show n
  | esPolCero p           = concat [show a, "*x^", show n]
  | a == 1                = concat ["x^", show n, " + ", escribePol p]
  | otherwise             = concat [show a, "*x^", show n, " + ", escribePol p]
  where n = grado pol
        a = coefLider pol
        p = restoPol pol

-- Procedimiento de escritura de polinomios.
instance (Num a, Show a, Eq a) => Show (Polinomio a) where
  show = escribePol

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

-- polCero es el polinomio cero. Por ejemplo,
--    λ> 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)

-- Generador de polinomios
-- =======================

-- genPolinomio es un generador de polinomios. Por ejemplo,
--    λ> 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 :: (Num a, Arbitrary 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 (Num a, Arbitrary a, Eq a) => Arbitrary (Polinomio a) where
  arbitrary = sized genPol

-- Propiedades de los polinomios
-- =============================

-- polCero es el polinomio cero.
prop_polCero_es_cero :: Bool
prop_polCero_es_cero =
  esPolCero polCero

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

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

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

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

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

-- Verificación
-- ============

return []

verificaPol :: IO Bool
verificaPol = $quickCheckAll

-- La verificación es
--    λ> verificaPol
--    === prop_polCero_es_cero from /home/jalonso/alonso/estudio/Exercitium/Exercitium/src/TAD/PolRepDensa.hs:157 ===
--    +++ OK, passed 1 test.
--
--    === prop_consPol_no_cero from /home/jalonso/alonso/estudio/Exercitium/Exercitium/src/TAD/PolRepDensa.hs:163 ===
--    +++ OK, passed 100 tests; 274 discarded.
--
--    === prop_consPol from /home/jalonso/alonso/estudio/Exercitium/Exercitium/src/TAD/PolRepDensa.hs:169 ===
--    +++ OK, passed 100 tests.
--
--    === prop_grado from /home/jalonso/alonso/estudio/Exercitium/Exercitium/src/TAD/PolRepDensa.hs:175 ===
--    +++ OK, passed 100 tests; 297 discarded.
--
--    === prop_coefLider from /home/jalonso/alonso/estudio/Exercitium/Exercitium/src/TAD/PolRepDensa.hs:182 ===
--    +++ OK, passed 100 tests; 248 discarded.
--
--    === prop_restoPol from /home/jalonso/alonso/estudio/Exercitium/Exercitium/src/TAD/PolRepDensa.hs:189 ===
--    +++ OK, passed 100 tests; 322 discarded.
--
--    True

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

{-# LANGUAGE TemplateHaskell #-}

{-# OPTIONS_GHC -fno-warn-unused-top-binds #-}

module TAD.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

import Test.QuickCheck

newtype Polinomio a = Pol [a]

deriving Eq

-- (escribePol p) es la cadena correspondiente al polinomio p. Por

-- ejemplo,

-- λ> escribePol (consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero)))

-- "3*x^4 + -5*x^2 + 3"

escribePol :: (Num a, Show a, Eq a) => Polinomio a -> String

escribePol pol

| esPolCero pol = "0"

| n == 0 && esPolCero p = show a

| n == 0 = concat [show a, " + ", escribePol p]

| n == 1 && esPolCero p = show a ++ "*x"

| n == 1 = concat [show a, "*x + ", escribePol p]

| a == 1 && esPolCero p = "x^" ++ show n

| esPolCero p = concat [show a, "*x^", show n]

| a == 1 = concat ["x^", show n, " + ", escribePol p]

| otherwise = concat [show a, "*x^", show n, " + ", escribePol p]

where n = grado pol

a = coefLider pol

p = restoPol pol

-- Procedimiento de escritura de polinomios.

instance (Num a, Show a, Eq a) => Show (Polinomio a) where

show = escribePol

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

-- polCero es el polinomio cero. Por ejemplo,

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

-- Generador de polinomios

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

-- genPolinomio es un generador de polinomios. Por ejemplo,

-- λ> 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 :: (Num a, Arbitrary 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 (Num a, Arbitrary a, Eq a) => Arbitrary (Polinomio a) where

arbitrary = sized genPol

-- Propiedades de los polinomios

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

-- polCero es el polinomio cero.

prop_polCero_es_cero :: Bool

prop_polCero_es_cero =

esPolCero polCero

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

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

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

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

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

-- Verificación

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

return []

verificaPol :: IO Bool

verificaPol = $quickCheckAll

-- La verificación es

-- λ> verificaPol

-- === prop_polCero_es_cero from /home/jalonso/alonso/estudio/Exercitium/Exercitium/src/TAD/PolRepDensa.hs:157 ===

-- +++ OK, passed 1 test.

-- === prop_consPol_no_cero from /home/jalonso/alonso/estudio/Exercitium/Exercitium/src/TAD/PolRepDensa.hs:163 ===

-- +++ OK, passed 100 tests; 274 discarded.

-- === prop_consPol from /home/jalonso/alonso/estudio/Exercitium/Exercitium/src/TAD/PolRepDensa.hs:169 ===

-- +++ OK, passed 100 tests.

-- === prop_grado from /home/jalonso/alonso/estudio/Exercitium/Exercitium/src/TAD/PolRepDensa.hs:175 ===

-- +++ OK, passed 100 tests; 297 discarded.

-- === prop_coefLider from /home/jalonso/alonso/estudio/Exercitium/Exercitium/src/TAD/PolRepDensa.hs:182 ===

-- +++ OK, passed 100 tests; 248 discarded.

-- === prop_restoPol from /home/jalonso/alonso/estudio/Exercitium/Exercitium/src/TAD/PolRepDensa.hs:189 ===

-- +++ OK, passed 100 tests; 322 discarded.

-- True

2.4. Implementación de polinomios mediante 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

1	6x^4 -5x^2 + 4x -7

se representa por

   [(4,6),(2,-5),(1,4),(0,-7)]

1	[(4,6),(2,-5),(1,4),(0,-7)]

En la representación se supone que los primeros elementos de los pares forman una sucesión estrictamente decreciente y que los segundos elementos son distintos de cero.

La implementación se encuentra en el módulo PolRepDispersa.hs cuyo contenido es el siguiente:

{-# LANGUAGE TemplateHaskell #-}
{-# OPTIONS_GHC -fno-warn-unused-top-binds #-}

module TAD.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

import Test.QuickCheck

newtype Polinomio a = Pol [(Int,a)]
  deriving Eq

-- (escribePol p) es la cadena correspondiente al polinomio p. Por
-- ejemplo,
--    λ> escribePol (consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero)))
--    "3*x^4 + -5*x^2 + 3"
escribePol :: (Num a, Show a, Eq a) => Polinomio a -> String
escribePol pol
  | esPolCero pol         = "0"
  | n == 0 && esPolCero p = show a
  | n == 0                = concat [show a, " + ", escribePol p]
  | n == 1 && esPolCero p = show a ++ "*x"
  | n == 1                = concat [show a, "*x + ", escribePol p]
  | a == 1 && esPolCero p = "x^" ++ show n
  | esPolCero p           = concat [show a, "*x^", show n]
  | a == 1                = concat ["x^", show n, " + ", escribePol p]
  | otherwise             = concat [show a, "*x^", show n, " + ", escribePol p]
  where n = grado pol
        a = coefLider pol
        p = restoPol pol

-- Procedimiento de escritura de polinomios.
instance (Num a, Show a, Eq a) => Show (Polinomio a) where
  show = escribePol

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

-- polCero es el polinomio cero. Por ejemplo,
--    λ> 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

-- Generador de polinomios                                          --
-- =======================

-- genPolinomio es un generador de polinomios. Por ejemplo,
--    λ> 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 :: (Num a, Arbitrary 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 (Num a, Arbitrary a, Eq a) => Arbitrary (Polinomio a) where
  arbitrary = sized genPol

-- Propiedades de los polinomios
-- =============================

-- polCero es el polinomio cero.
prop_polCero_es_cero :: Bool
prop_polCero_es_cero =
  esPolCero polCero

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

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

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

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

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

-- Verificación
-- ============

return []

verificaPol :: IO Bool
verificaPol = $quickCheckAll

-- La verificación es
--    λ> verificaPol
--    === prop_polCero_es_cero from /home/jalonso/alonso/estudio/Exercitium/Exercitium/src/TAD/PolRepDispersa.hs:156 ===
--    +++ OK, passed 1 test.
--
--    === prop_consPol_no_cero from /home/jalonso/alonso/estudio/Exercitium/Exercitium/src/TAD/PolRepDispersa.hs:162 ===
--    +++ OK, passed 100 tests; 264 discarded.
--
--    === prop_consPol from /home/jalonso/alonso/estudio/Exercitium/Exercitium/src/TAD/PolRepDispersa.hs:168 ===
--    +++ OK, passed 100 tests.
--
--    === prop_grado from /home/jalonso/alonso/estudio/Exercitium/Exercitium/src/TAD/PolRepDispersa.hs:174 ===
--    +++ OK, passed 100 tests; 266 discarded.
--
--    === prop_coefLider from /home/jalonso/alonso/estudio/Exercitium/Exercitium/src/TAD/PolRepDispersa.hs:181 ===
--    +++ OK, passed 100 tests; 251 discarded.
--
--    === prop_restoPol from /home/jalonso/alonso/estudio/Exercitium/Exercitium/src/TAD/PolRepDispersa.hs:188 ===
--    +++ OK, passed 100 tests; 254 discarded.
--
--    True

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

{-# LANGUAGE TemplateHaskell #-}

{-# OPTIONS_GHC -fno-warn-unused-top-binds #-}

module TAD.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

import Test.QuickCheck

newtype Polinomio a = Pol [(Int,a)]

deriving Eq

-- (escribePol p) es la cadena correspondiente al polinomio p. Por

-- ejemplo,

-- λ> escribePol (consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero)))

-- "3*x^4 + -5*x^2 + 3"

escribePol :: (Num a, Show a, Eq a) => Polinomio a -> String

escribePol pol

| esPolCero pol = "0"

| n == 0 && esPolCero p = show a

| n == 0 = concat [show a, " + ", escribePol p]

| n == 1 && esPolCero p = show a ++ "*x"

| n == 1 = concat [show a, "*x + ", escribePol p]

| a == 1 && esPolCero p = "x^" ++ show n

| esPolCero p = concat [show a, "*x^", show n]

| a == 1 = concat ["x^", show n, " + ", escribePol p]

| otherwise = concat [show a, "*x^", show n, " + ", escribePol p]

where n = grado pol

a = coefLider pol

p = restoPol pol

-- Procedimiento de escritura de polinomios.

instance (Num a, Show a, Eq a) => Show (Polinomio a) where

show = escribePol

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

-- polCero es el polinomio cero. Por ejemplo,

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

-- Generador de polinomios --

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

-- genPolinomio es un generador de polinomios. Por ejemplo,

-- λ> 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 :: (Num a, Arbitrary 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 (Num a, Arbitrary a, Eq a) => Arbitrary (Polinomio a) where

arbitrary = sized genPol

-- Propiedades de los polinomios

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

-- polCero es el polinomio cero.

prop_polCero_es_cero :: Bool

prop_polCero_es_cero =

esPolCero polCero

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

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

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

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

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

-- Verificación

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

return []

verificaPol :: IO Bool

verificaPol = $quickCheckAll

-- La verificación es

-- λ> verificaPol

-- === prop_polCero_es_cero from /home/jalonso/alonso/estudio/Exercitium/Exercitium/src/TAD/PolRepDispersa.hs:156 ===

-- +++ OK, passed 1 test.

-- === prop_consPol_no_cero from /home/jalonso/alonso/estudio/Exercitium/Exercitium/src/TAD/PolRepDispersa.hs:162 ===

-- +++ OK, passed 100 tests; 264 discarded.

-- === prop_consPol from /home/jalonso/alonso/estudio/Exercitium/Exercitium/src/TAD/PolRepDispersa.hs:168 ===

-- +++ OK, passed 100 tests.

-- === prop_grado from /home/jalonso/alonso/estudio/Exercitium/Exercitium/src/TAD/PolRepDispersa.hs:174 ===

-- +++ OK, passed 100 tests; 266 discarded.

-- === prop_coefLider from /home/jalonso/alonso/estudio/Exercitium/Exercitium/src/TAD/PolRepDispersa.hs:181 ===

-- +++ OK, passed 100 tests; 251 discarded.

-- === prop_restoPol from /home/jalonso/alonso/estudio/Exercitium/Exercitium/src/TAD/PolRepDispersa.hs:188 ===

-- +++ OK, passed 100 tests; 254 discarded.

-- True

3. Los polinomios en Python

3.1. El tipo abstracto de los polinomios en Python

La implementación se encuentra en el módulo Polinomio.py cuyo contenido es el siguiente:

__all__ = [
    'Polinomio',
    'polCero',
    'esPolCero',
    'consPol',
    'grado',
    'coefLider',
    'restoPol',
    'polinomioAleatorio'
]

from src.TAD.PolRepDensa import (Polinomio, coefLider, consPol, esPolCero,
                                 grado, polCero, polinomioAleatorio, restoPol)

# from src.TAD.PolRepDispersa import (Polinomio, polCero, esPolCero,
#                                     consPol, grado, coefLider,
#                                     restoPol, polinomioAleatorio)

__all__ = [

'Polinomio',

'polCero',

'esPolCero',

'consPol',

'grado',

'coefLider',

'restoPol',

'polinomioAleatorio'

]

from src.TAD.PolRepDensa import (Polinomio, coefLider, consPol, esPolCero,

grado, polCero, polinomioAleatorio, restoPol)

# from src.TAD.PolRepDispersa import (Polinomio, polCero, esPolCero,

# consPol, grado, coefLider,

# restoPol, polinomioAleatorio)

Para usar el TAD hay que usar una implementación concreta. En principio, consideraremos las siguientes:

mediante listas densas y
mediante listas dispersas.

3.2. Implementación de los polinomios mediante 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

1	6x^4 -5x^2 + 4x -7

se representa por

   [6,0,-2,4,-7]

1	[6,0,-2,4,-7]

En la representación se supone que, si la lista no es vacía, su primer elemento es distinto de cero.

Se define la clase Polinomio con los siguientes métodos:

esPolCero() se verifica si es el polinomio cero.
consPol(n, b) es el polinomio obtenido añadiendo el térmiono bx^n
grado() es el grado del polinomio.
coefLider() es el coeficiente líder del polinomio.
restoPol() es el resto del polinomio.

Por ejemplo,

   >>> Polinomio()
   0
   >>> ejPol1 = Polinomio().consPol(0,3).consPol(2,-5).consPol(4,3)
   >>> ejPol1
   3*x^4 + -5*x^2 + 3
   >>> ejPol2 = Polinomio().consPol(1,4).consPol(2,5).consPol(5,1)
   >>> ejPol2
   x^5 + 5*x^2 + 4*x
   >>> ejPol3 = Polinomio().consPol(1,2).consPol(4,6)
   >>> ejPol3
   6*x^4 + 2*x
   >>> Polinomio().esPolCero()
   True
   >>> ejPol1.esPolCero()
   False
   >>> ejPol2
   x^5 + 5*x^2 + 4*x
   >>> ejPol2.consPol(3,0)
   x^5 + 5*x^2 + 4*x
   >>> Polinomio().consPol(3,2)
   2*x^3
   >>> ejPol2.consPol(6,7)
   7*x^6 + x^5 + 5*x^2 + 4*x
   >>> ejPol2.consPol(4,7)
   x^5 + 7*x^4 + 5*x^2 + 4*x
   >>> ejPol2.consPol(5,7)
   8*x^5 + 5*x^2 + 4*x
   >>> ejPol3
   6*x^4 + 2*x
   >>> ejPol3.grado()
   4
   >>> ejPol3.restoPol()
   2*x
   >>> ejPol2
   x^5 + 5*x^2 + 4*x
   >>> ejPol2.restoPol()
   5*x^2 + 4*x

>>> Polinomio()

>>> ejPol1 = Polinomio().consPol(0,3).consPol(2,-5).consPol(4,3)

>>> ejPol1

3*x^4 + -5*x^2 + 3

>>> ejPol2 = Polinomio().consPol(1,4).consPol(2,5).consPol(5,1)

>>> ejPol2

x^5 + 5*x^2 + 4*x

>>> ejPol3 = Polinomio().consPol(1,2).consPol(4,6)

>>> ejPol3

6*x^4 + 2*x

>>> Polinomio().esPolCero()

True

>>> ejPol1.esPolCero()

False

>>> ejPol2

x^5 + 5*x^2 + 4*x

>>> ejPol2.consPol(3,0)

x^5 + 5*x^2 + 4*x

>>> Polinomio().consPol(3,2)

2*x^3

>>> ejPol2.consPol(6,7)

7*x^6 + x^5 + 5*x^2 + 4*x

>>> ejPol2.consPol(4,7)

x^5 + 7*x^4 + 5*x^2 + 4*x

>>> ejPol2.consPol(5,7)

8*x^5 + 5*x^2 + 4*x

>>> ejPol3

6*x^4 + 2*x

>>> ejPol3.grado()

>>> ejPol3.restoPol()

2*x

>>> ejPol2

x^5 + 5*x^2 + 4*x

>>> ejPol2.restoPol()

5*x^2 + 4*x

Además se definen las correspondientes funciones. Por ejemplo,

   >>> polCero()
   0
   >>> ejPol1a = consPol(4,3,consPol(2,-5,consPol(0,3,polCero())))
   >>> ejPol1a
   3*x^4 + -5*x^2 + 3
   >>> ejPol2a = consPol(5,1,consPol(2,5,consPol(1,4,polCero())))
   >>> ejPol2a
   x^5 + 5*x^2 + 4*x
   >>> ejPol3a = consPol(4,6,consPol(1,2,polCero()))
   >>> ejPol3a
   6*x^4 + 2*x
   >>> esPolCero(polCero())
   True
   >>> esPolCero(ejPol1a)
   False
   >>> ejPol2a
   x^5 + 5*x^2 + 4*x
   >>> consPol(3,9,ejPol2a)
   x^5 + 9*x^3 + 5*x^2 + 4*x
   >>> consPol(3,2,polCero())
   2*x^3
   >>> consPol(6,7,ejPol2a)
   7*x^6 + x^5 + 5*x^2 + 4*x
   >>> consPol(4,7,ejPol2a)
   x^5 + 7*x^4 + 5*x^2 + 4*x
   >>> consPol(5,7,ejPol2a)
   8*x^5 + 5*x^2 + 4*x
   >>> ejPol3a
   6*x^4 + 2*x
   >>> grado(ejPol3a)
   4
   >>> restoPol(ejPol3a)
   2*x
   >>> ejPol2a
   x^5 + 5*x^2 + 4*x
   >>> restoPol(ejPol2a)
   5*x^2 + 4*x

>>> polCero()

>>> ejPol1a = consPol(4,3,consPol(2,-5,consPol(0,3,polCero())))

>>> ejPol1a

3*x^4 + -5*x^2 + 3

>>> ejPol2a = consPol(5,1,consPol(2,5,consPol(1,4,polCero())))

>>> ejPol2a

x^5 + 5*x^2 + 4*x

>>> ejPol3a = consPol(4,6,consPol(1,2,polCero()))

>>> ejPol3a

6*x^4 + 2*x

>>> esPolCero(polCero())

True

>>> esPolCero(ejPol1a)

False

>>> ejPol2a

x^5 + 5*x^2 + 4*x

>>> consPol(3,9,ejPol2a)

x^5 + 9*x^3 + 5*x^2 + 4*x

>>> consPol(3,2,polCero())

2*x^3

>>> consPol(6,7,ejPol2a)

7*x^6 + x^5 + 5*x^2 + 4*x

>>> consPol(4,7,ejPol2a)

x^5 + 7*x^4 + 5*x^2 + 4*x

>>> consPol(5,7,ejPol2a)

8*x^5 + 5*x^2 + 4*x

>>> ejPol3a

6*x^4 + 2*x

>>> grado(ejPol3a)

>>> restoPol(ejPol3a)

2*x

>>> ejPol2a

x^5 + 5*x^2 + 4*x

>>> restoPol(ejPol2a)

5*x^2 + 4*x

Finalmente, se define un generador aleatorio de polinomios y se comprueba que los polinomios cumplen las propiedades de su especificación.

La implementación se encuentra en el módulo PolRepDensa.py en el que se define la clase Conj con los siguientes métodos:

from __future__ import annotations

__all__ = [
    'Polinomio',
    'polCero',
    'esPolCero',
    'consPol',
    'grado',
    'coefLider',
    'restoPol',
    'polinomioAleatorio'
]

from dataclasses import dataclass, field
from itertools import dropwhile
from typing import Generic, TypeVar

from hypothesis import assume, given
from hypothesis import strategies as st

A = TypeVar('A', int, float, complex)

# Clase de los polinomios mediante listas densas
# ==============================================

@dataclass
class Polinomio(Generic[A]):
    _coeficientes: list[A] = field(default_factory=list)

    def esPolCero(self) -> bool:
        return not self._coeficientes

    def grado(self) -> int:
        if self.esPolCero():
            return 0
        return len(self._coeficientes) - 1

    def coefLider(self) -> A:
        if self.esPolCero():
            return 0
        return self._coeficientes[0]

    def restoPol(self) -> Polinomio[A]:
        xs = self._coeficientes
        if len(xs) <= 1:
            return Polinomio([])
        if xs[1] == 0:
            return Polinomio(list(dropwhile(lambda x: x == 0, xs[2:])))
        return Polinomio(xs[1:])

    def consPol(self, n: int, b: A) -> Polinomio[A]:
        m = self.grado()
        c = self.coefLider()
        xs = self._coeficientes
        if b == 0:
            return self
        if self.esPolCero():
            return Polinomio([b] + ([0] * n))
        if n > m:
            return Polinomio([b] + ([0] * (n-m-1)) + xs)
        if n < m:
            return self.restoPol().consPol(n, b).consPol(m, c)
        if b + c == 0:
            return Polinomio(list(dropwhile(lambda x: x == 0, xs[1:])))
        return Polinomio([b + c] + xs[1:])

    def __repr__(self) -> str:
        n = self.grado()
        a = self.coefLider()
        p = self.restoPol()
        if self.esPolCero():
            return "0"
        if n == 0 and p.esPolCero():
            return str(a)
        if n == 0:
            return str(a) + " + " + str(p)
        if n == 1 and p.esPolCero():
            return str(a) + "*x"
        if n == 1:
            return str(a) + "*x + " + str(p)
        if a == 1 and p.esPolCero():
            return "x^" + str(n)
        if p.esPolCero():
            return str(a) + "*x^" + str(n)
        if a == 1:
            return "x^" + str(n) + " + " + str(p)
        return str(a) + "*x^" + str(n) + " + " + str(p)

# Funciones del tipo polinomio
# ============================

def polCero() -> Polinomio[A]:
    return Polinomio([])

def esPolCero(p: Polinomio[A]) -> bool:
    return p.esPolCero()

def grado(p: Polinomio[A]) -> int:
    return p.grado()

def coefLider(p: Polinomio[A]) -> A:
    return p.coefLider()

def restoPol(p: Polinomio[A]) -> Polinomio[A]:
    return p.restoPol()

def consPol(n: int, b: A, p: Polinomio[A]) -> Polinomio[A]:
    return p.consPol(n, b)

# Generador de polinomios
# =======================

# normal(xs) es la lista obtenida eliminando los ceros iniciales de
# xs. Por ejmplo,
#    >>> normal([0,0,5,0])
#    [5, 0]
#    >>> normal([0,0,0,0])
#    []
def normal(xs: list[A]) -> list[A]:
    return list(dropwhile(lambda x: x == 0, xs))

# polinomioAleatorio() genera polinomios aleatorios. Por ejemplo,
#    >>> polinomioAleatorio().example()
#    9*x^6 + -7*x^5 + 7*x^3 + x^2 + 7
#    >>> polinomioAleatorio().example()
#    -3*x^7 + 8*x^6 + 2*x^5 + x^4 + -1*x^3 + -6*x^2 + 8*x + -6
#    >>> polinomioAleatorio().example()
#    x^2 + 7*x + -1
def polinomioAleatorio() -> st.SearchStrategy[Polinomio[int]]:
    return st.lists(st.integers(min_value=-9, max_value=9), max_size=10)\
             .map(lambda xs: normal(xs))\
             .map(Polinomio)

# Comprobación de las propiedades de los polinomios
# =================================================

# Las propiedades son
def test_esPolCero1() -> None:
    assert esPolCero(polCero())

@given(p=polinomioAleatorio(),
       n=st.integers(min_value=0, max_value=10),
       b=st.integers())
def test_esPolCero2(p: Polinomio[int], n: int, b: int) -> None:
    assume(n > grado(p) and b != 0)
    assert not esPolCero(consPol(n, b, p))

@given(p=polinomioAleatorio())
def test_consPol(p: Polinomio[int]) -> None:
    assume(not esPolCero(p))
    assert consPol(grado(p), coefLider(p), restoPol(p)) == p

@given(p=polinomioAleatorio(),
       n=st.integers(min_value=0, max_value=10),
       b=st.integers())
def test_grado(p: Polinomio[int], n: int, b: int) -> None:
    assume(n > grado(p) and b != 0)
    assert grado(consPol(n, b, p)) == n

@given(p=polinomioAleatorio(),
       n=st.integers(min_value=0, max_value=10),
       b=st.integers())
def test_coefLider(p: Polinomio[int], n: int, b: int) -> None:
    assume(n > grado(p) and b != 0)
    assert coefLider(consPol(n, b, p)) == b

@given(p=polinomioAleatorio(),
       n=st.integers(min_value=0, max_value=10),
       b=st.integers())
def test_restoPol(p: Polinomio[int], n: int, b: int) -> None:
    assume(n > grado(p) and b != 0)
    assert restoPol(consPol(n, b, p)) == p

# La comprobación es
#    > poetry run pytest -v PolRepDensa.py
#
#    PolRepDensa.py::test_esPolCero1 PASSED
#    PolRepDensa.py::test_esPolCero2 PASSED
#    PolRepDensa.py::test_consPol PASSED
#    PolRepDensa.py::test_grado PASSED
#    PolRepDensa.py::test_coefLider PASSED
#    PolRepDensa.py::test_restoPol PASSED
#
#    === 6 passed in 1.64s ===

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

from __future__ import annotations

__all__ = [

'Polinomio',

'polCero',

'esPolCero',

'consPol',

'grado',

'coefLider',

'restoPol',

'polinomioAleatorio'

]

from dataclasses import dataclass, field

from itertools import dropwhile

from typing import Generic, TypeVar

from hypothesis import assume, given

from hypothesis import strategies as st

A = TypeVar('A', int, float, complex)

# Clase de los polinomios mediante listas densas

# ==============================================

@dataclass

class Polinomio(Generic[A]):

_coeficientes: list[A] = field(default_factory=list)

def esPolCero(self) -> bool:

return not self._coeficientes

def grado(self) -> int:

if self.esPolCero():

return 0

return len(self._coeficientes) - 1

def coefLider(self) -> A:

if self.esPolCero():

return 0

return self._coeficientes[0]

def restoPol(self) -> Polinomio[A]:

xs = self._coeficientes

if len(xs) <= 1:

return Polinomio([])

if xs[1] == 0:

return Polinomio(list(dropwhile(lambda x: x == 0, xs[2:])))

return Polinomio(xs[1:])

def consPol(self, n: int, b: A) -> Polinomio[A]:

m = self.grado()

c = self.coefLider()

xs = self._coeficientes

if b == 0:

return self

if self.esPolCero():

return Polinomio([b] + ([0] * n))

if n > m:

return Polinomio([b] + ([0] * (n-m-1)) + xs)

if n < m:

return self.restoPol().consPol(n, b).consPol(m, c)

if b + c == 0:

return Polinomio(list(dropwhile(lambda x: x == 0, xs[1:])))

return Polinomio([b + c] + xs[1:])

def __repr__(self) -> str:

n = self.grado()

a = self.coefLider()

p = self.restoPol()

if self.esPolCero():

return "0"

if n == 0 and p.esPolCero():

return str(a)

if n == 0:

return str(a) + " + " + str(p)

if n == 1 and p.esPolCero():

return str(a) + "*x"

if n == 1:

return str(a) + "*x + " + str(p)

if a == 1 and p.esPolCero():

return "x^" + str(n)

if p.esPolCero():

return str(a) + "*x^" + str(n)

if a == 1:

return "x^" + str(n) + " + " + str(p)

return str(a) + "*x^" + str(n) + " + " + str(p)

# Funciones del tipo polinomio

# ============================

def polCero() -> Polinomio[A]:

return Polinomio([])

def esPolCero(p: Polinomio[A]) -> bool:

return p.esPolCero()

def grado(p: Polinomio[A]) -> int:

return p.grado()

def coefLider(p: Polinomio[A]) -> A:

return p.coefLider()

def restoPol(p: Polinomio[A]) -> Polinomio[A]:

return p.restoPol()

def consPol(n: int, b: A, p: Polinomio[A]) -> Polinomio[A]:

return p.consPol(n, b)

# Generador de polinomios

# =======================

# normal(xs) es la lista obtenida eliminando los ceros iniciales de

# xs. Por ejmplo,

# >>> normal([0,0,5,0])

# [5, 0]

# >>> normal([0,0,0,0])

# []

def normal(xs: list[A]) -> list[A]:

return list(dropwhile(lambda x: x == 0, xs))

# polinomioAleatorio() genera polinomios aleatorios. Por ejemplo,

# >>> polinomioAleatorio().example()

# 9*x^6 + -7*x^5 + 7*x^3 + x^2 + 7

# >>> polinomioAleatorio().example()

# -3*x^7 + 8*x^6 + 2*x^5 + x^4 + -1*x^3 + -6*x^2 + 8*x + -6

# >>> polinomioAleatorio().example()

# x^2 + 7*x + -1

def polinomioAleatorio() -> st.SearchStrategy[Polinomio[int]]:

return st.lists(st.integers(min_value=-9, max_value=9), max_size=10)\

.map(lambda xs: normal(xs))\

.map(Polinomio)

# Comprobación de las propiedades de los polinomios

# =================================================

# Las propiedades son

def test_esPolCero1() -> None:

assert esPolCero(polCero())

@given(p=polinomioAleatorio(),

n=st.integers(min_value=0, max_value=10),

b=st.integers())

def test_esPolCero2(p: Polinomio[int], n: int, b: int) -> None:

assume(n > grado(p) and b != 0)

assert not esPolCero(consPol(n, b, p))

@given(p=polinomioAleatorio())

def test_consPol(p: Polinomio[int]) -> None:

assume(not esPolCero(p))

assert consPol(grado(p), coefLider(p), restoPol(p)) == p

@given(p=polinomioAleatorio(),

n=st.integers(min_value=0, max_value=10),

b=st.integers())

def test_grado(p: Polinomio[int], n: int, b: int) -> None:

assume(n > grado(p) and b != 0)

assert grado(consPol(n, b, p)) == n

@given(p=polinomioAleatorio(),

n=st.integers(min_value=0, max_value=10),

b=st.integers())

def test_coefLider(p: Polinomio[int], n: int, b: int) -> None:

assume(n > grado(p) and b != 0)

assert coefLider(consPol(n, b, p)) == b

@given(p=polinomioAleatorio(),

n=st.integers(min_value=0, max_value=10),

b=st.integers())

def test_restoPol(p: Polinomio[int], n: int, b: int) -> None:

assume(n > grado(p) and b != 0)

assert restoPol(consPol(n, b, p)) == p

# La comprobación es

# > poetry run pytest -v PolRepDensa.py

# PolRepDensa.py::test_esPolCero1 PASSED

# PolRepDensa.py::test_esPolCero2 PASSED

# PolRepDensa.py::test_consPol PASSED

# PolRepDensa.py::test_grado PASSED

# PolRepDensa.py::test_coefLider PASSED

# PolRepDensa.py::test_restoPol PASSED

# === 6 passed in 1.64s ===

3.3. Implementación de los polinomios mediante 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

1	6x^4 -5x^2 + 4x -7

se representa por

   [(4,6),(2,-5),(1,4),(0,-7)]

1	[(4,6),(2,-5),(1,4),(0,-7)]

En la representación se supone que los primeros elementos de los pares forman una sucesión estrictamente decreciente y que los segundos elementos son distintos de cero.

La implementación se encuentra en el módulo PolRepDispersa.py cuyo contenido es

from __future__ import annotations

__all__ = [
    'Polinomio',
    'polCero',
    'esPolCero',
    'consPol',
    'grado',
    'coefLider',
    'restoPol',
    'polinomioAleatorio'
]

from dataclasses import dataclass, field
from typing import Generic, TypeVar

from hypothesis import assume, given
from hypothesis import strategies as st

A = TypeVar('A', int, float, complex)

# Clase de los polinomios mediante listas densas
# ==============================================

@dataclass
class Polinomio(Generic[A]):
    _terminos: list[tuple[int, A]] = field(default_factory=list)

    def esPolCero(self) -> bool:
        return not self._terminos

    def grado(self) -> int:
        if self.esPolCero():
            return 0
        return self._terminos[0][0]

    def coefLider(self) -> A:
        if self.esPolCero():
            return 0
        return self._terminos[0][1]

    def restoPol(self) -> Polinomio[A]:
        xs = self._terminos
        if len(xs) <= 1:
            return Polinomio([])
        return Polinomio(xs[1:])

    def consPol(self, n: int, b: A) -> Polinomio[A]:
        m = self.grado()
        c = self.coefLider()
        xs = self._terminos
        if b == 0:
            return self
        if self.esPolCero():
            return Polinomio([(n, b)])
        if n > m:
            return Polinomio([(n, b)] + xs)
        if n < m:
            return Polinomio(xs[1:]).consPol(n, b).consPol(m, c)
        if b + c == 0:
            return Polinomio(xs[1:])
        return Polinomio([(n, b + c)] + xs[1:])

    def __repr__(self) -> str:
        n = self.grado()
        a = self.coefLider()
        p = self.restoPol()
        if self.esPolCero():
            return "0"
        if n == 0 and p.esPolCero():
            return str(a)
        if n == 0:
            return str(a) + " + " + str(p)
        if n == 1 and p.esPolCero():
            return str(a) + "*x"
        if n == 1:
            return str(a) + "*x + " + str(p)
        if a == 1 and p.esPolCero():
            return "x^" + str(n)
        if p.esPolCero():
            return str(a) + "*x^" + str(n)
        if a == 1:
            return "x^" + str(n) + " + " + str(p)
        return str(a) + "*x^" + str(n) + " + " + str(p)

# Funciones del tipo polinomio
# ============================

def polCero() -> Polinomio[A]:
    return Polinomio([])

def esPolCero(p: Polinomio[A]) -> bool:
    return p.esPolCero()

def grado(p: Polinomio[A]) -> int:
    return p.grado()

def coefLider(p: Polinomio[A]) -> A:
    return p.coefLider()

def restoPol(p: Polinomio[A]) -> Polinomio[A]:
    return p.restoPol()

def consPol(n: int, b: A, p: Polinomio[A]) -> Polinomio[A]:
    return p.consPol(n, b)

# Generador de polinomios
# =======================

# normal(ps) es la representación dispersa de un polinomio.
def normal(ps: list[tuple[int, A]]) -> list[tuple[int, A]]:
    xs = sorted(list({p[0] for p in ps}), reverse=True)
    ys = [p[1] for p in ps]
    return [(x, y) for (x, y) in zip(xs, ys) if y != 0]

# polinomioAleatorio() genera polinomios aleatorios. Por ejemplo,
#    >>> polinomioAleatorio().example()
#    -4*x^8 + -5*x^7 + -4*x^6 + -4*x^5 + -8*x^3
#    >>> polinomioAleatorio().example()
#    -7*x^9 + -8*x^6 + -8*x^3 + 2*x^2 + -1*x + 4
def polinomioAleatorio() -> st.SearchStrategy[Polinomio[int]]:
    return st.lists(st.tuples(st.integers(min_value=0, max_value=9),
                              st.integers(min_value=-9, max_value=9)))\
             .map(lambda ps: normal(ps))\
             .map(Polinomio)

# Comprobación de las propiedades de los polinomios
# =================================================

# Las propiedades son
def test_esPolCero1() -> None:
    assert esPolCero(polCero())

@given(p=polinomioAleatorio(),
       n=st.integers(min_value=0, max_value=10),
       b=st.integers())
def test_esPolCero2(p: Polinomio[int], n: int, b: int) -> None:
    assume(n > grado(p) and b != 0)
    assert not esPolCero(consPol(n, b, p))

@given(p=polinomioAleatorio())
def test_consPol(p: Polinomio[int]) -> None:
    assume(not esPolCero(p))
    assert consPol(grado(p), coefLider(p), restoPol(p)) == p

@given(p=polinomioAleatorio(),
       n=st.integers(min_value=0, max_value=10),
       b=st.integers())
def test_grado(p: Polinomio[int], n: int, b: int) -> None:
    assume(n > grado(p) and b != 0)
    assert grado(consPol(n, b, p)) == n

@given(p=polinomioAleatorio(),
       n=st.integers(min_value=0, max_value=10),
       b=st.integers())
def test_coefLider(p: Polinomio[int], n: int, b: int) -> None:
    assume(n > grado(p) and b != 0)
    assert coefLider(consPol(n, b, p)) == b

@given(p=polinomioAleatorio(),
       n=st.integers(min_value=0, max_value=10),
       b=st.integers())
def test_restoPol(p: Polinomio[int], n: int, b: int) -> None:
    assume(n > grado(p) and b != 0)
    assert restoPol(consPol(n, b, p)) == p

# La comprobación es
#    > poetry run pytest -v PolRepDispersa.py
#
#    PolRepDispersa.py::test_esPolCero1 PASSED
#    PolRepDispersa.py::test_esPolCero2 PASSED
#    PolRepDispersa.py::test_consPol PASSED
#    PolRepDispersa.py::test_grado PASSED
#    PolRepDispersa.py::test_coefLider PASSED
#    PolRepDispersa.py::test_restoPol PASSED
#
#    === 6 passed in 1.74s ===

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

from __future__ import annotations

__all__ = [

'Polinomio',

'polCero',

'esPolCero',

'consPol',

'grado',

'coefLider',

'restoPol',

'polinomioAleatorio'

]

from dataclasses import dataclass, field

from typing import Generic, TypeVar

from hypothesis import assume, given

from hypothesis import strategies as st

A = TypeVar('A', int, float, complex)

# Clase de los polinomios mediante listas densas

# ==============================================

@dataclass

class Polinomio(Generic[A]):

_terminos: list[tuple[int, A]] = field(default_factory=list)

def esPolCero(self) -> bool:

return not self._terminos

def grado(self) -> int:

if self.esPolCero():

return 0

return self._terminos[0][0]

def coefLider(self) -> A:

if self.esPolCero():

return 0

return self._terminos[0][1]

def restoPol(self) -> Polinomio[A]:

xs = self._terminos

if len(xs) <= 1:

return Polinomio([])

return Polinomio(xs[1:])

def consPol(self, n: int, b: A) -> Polinomio[A]:

m = self.grado()

c = self.coefLider()

xs = self._terminos

if b == 0:

return self

if self.esPolCero():

return Polinomio([(n, b)])

if n > m:

return Polinomio([(n, b)] + xs)

if n < m:

return Polinomio(xs[1:]).consPol(n, b).consPol(m, c)

if b + c == 0:

return Polinomio(xs[1:])

return Polinomio([(n, b + c)] + xs[1:])

def __repr__(self) -> str:

n = self.grado()

a = self.coefLider()

p = self.restoPol()

if self.esPolCero():

return "0"

if n == 0 and p.esPolCero():

return str(a)

if n == 0:

return str(a) + " + " + str(p)

if n == 1 and p.esPolCero():

return str(a) + "*x"

if n == 1:

return str(a) + "*x + " + str(p)

if a == 1 and p.esPolCero():

return "x^" + str(n)

if p.esPolCero():

return str(a) + "*x^" + str(n)

if a == 1:

return "x^" + str(n) + " + " + str(p)

return str(a) + "*x^" + str(n) + " + " + str(p)

# Funciones del tipo polinomio

# ============================

def polCero() -> Polinomio[A]:

return Polinomio([])

def esPolCero(p: Polinomio[A]) -> bool:

return p.esPolCero()

def grado(p: Polinomio[A]) -> int:

return p.grado()

def coefLider(p: Polinomio[A]) -> A:

return p.coefLider()

def restoPol(p: Polinomio[A]) -> Polinomio[A]:

return p.restoPol()

def consPol(n: int, b: A, p: Polinomio[A]) -> Polinomio[A]:

return p.consPol(n, b)

# Generador de polinomios

# =======================

# normal(ps) es la representación dispersa de un polinomio.

def normal(ps: list[tuple[int, A]]) -> list[tuple[int, A]]:

xs = sorted(list({p[0] for p in ps}), reverse=True)

ys = [p[1] for p in ps]

return [(x, y) for (x, y) in zip(xs, ys) if y != 0]

# polinomioAleatorio() genera polinomios aleatorios. Por ejemplo,

# >>> polinomioAleatorio().example()

# -4*x^8 + -5*x^7 + -4*x^6 + -4*x^5 + -8*x^3

# >>> polinomioAleatorio().example()

# -7*x^9 + -8*x^6 + -8*x^3 + 2*x^2 + -1*x + 4

def polinomioAleatorio() -> st.SearchStrategy[Polinomio[int]]:

return st.lists(st.tuples(st.integers(min_value=0, max_value=9),

st.integers(min_value=-9, max_value=9)))\

.map(lambda ps: normal(ps))\

.map(Polinomio)

# Comprobación de las propiedades de los polinomios

# =================================================

# Las propiedades son

def test_esPolCero1() -> None:

assert esPolCero(polCero())

@given(p=polinomioAleatorio(),

n=st.integers(min_value=0, max_value=10),

b=st.integers())

def test_esPolCero2(p: Polinomio[int], n: int, b: int) -> None:

assume(n > grado(p) and b != 0)

assert not esPolCero(consPol(n, b, p))

@given(p=polinomioAleatorio())

def test_consPol(p: Polinomio[int]) -> None:

assume(not esPolCero(p))

assert consPol(grado(p), coefLider(p), restoPol(p)) == p

@given(p=polinomioAleatorio(),

n=st.integers(min_value=0, max_value=10),

b=st.integers())

def test_grado(p: Polinomio[int], n: int, b: int) -> None:

assume(n > grado(p) and b != 0)

assert grado(consPol(n, b, p)) == n

@given(p=polinomioAleatorio(),

n=st.integers(min_value=0, max_value=10),

b=st.integers())

def test_coefLider(p: Polinomio[int], n: int, b: int) -> None:

assume(n > grado(p) and b != 0)

assert coefLider(consPol(n, b, p)) == b

@given(p=polinomioAleatorio(),

n=st.integers(min_value=0, max_value=10),

b=st.integers())

def test_restoPol(p: Polinomio[int], n: int, b: int) -> None:

assume(n > grado(p) and b != 0)

assert restoPol(consPol(n, b, p)) == p

# La comprobación es

# > poetry run pytest -v PolRepDispersa.py

# PolRepDispersa.py::test_esPolCero1 PASSED

# PolRepDispersa.py::test_esPolCero2 PASSED

# PolRepDispersa.py::test_consPol PASSED

# PolRepDispersa.py::test_grado PASSED

# PolRepDispersa.py::test_coefLider PASSED

# PolRepDispersa.py::test_restoPol PASSED

# === 6 passed in 1.74s ===

Valores de polinomios representados con vectores

PorJosé A. Alonso 14-marzo-202215-abril-2022

Los polinomios se pueden representar mediante vectores usando la librería Data.Array. En primer lugar, se define el tipo de los polinomios (con coeficientes de tipo a) mediante

   type Polinomio a = Array Int a

1	type Polinomio a = Array Int a

Como ejemplos, definimos el polinomio

   ej_pol1 :: Array Int Int
   ej_pol1 = array (0,4) [(0,6),(1,2),(2,-5),(3,0),(4,7)]

1 2	ej_pol1 :: Array Int Int ej_pol1 = array (0,4) [(0,6),(1,2),(2,-5),(3,0),(4,7)]

que representa a 6 + 2x – 5x^2 + 7x^4 y el polinomio

   ej_pol2 :: Array Int Double
   ej_pol2 = array (0,4) [(0,6.5),(1,2),(2,-5.2),(3,0),(4,7)]

1 2	ej_pol2 :: Array Int Double ej_pol2 = array (0,4) [(0,6.5),(1,2),(2,-5.2),(3,0),(4,7)]

que representa a 6.5 + 2x – 5.2x^2 + 7x^4

Definir la función

   valor :: Num a => Polinomio a -> a -> a

1	valor :: Num a => Polinomio a -> a -> a

tal que (valor p b) es el valor del polinomio p en el punto b. Por ejemplo,

   valor ej_pol1 0  ==  6
   valor ej_pol1 1  ==  10
   valor ej_pol1 2  ==  102
   valor ej_pol2 0  ==  6.5
   valor ej_pol2 1  ==  10.3
   valor ej_pol2 3  ==  532.7
   length (show (valor (listArray (0,5*10^5) (repeat 1)) 2)) == 150516

valor ej_pol1 0 == 6

valor ej_pol1 1 == 10

valor ej_pol1 2 == 102

valor ej_pol2 0 == 6.5

valor ej_pol2 1 == 10.3

valor ej_pol2 3 == 532.7

length (show (valor (listArray (0,5*10^5) (repeat 1)) 2)) == 150516

Soluciones

import Data.List (foldl')
import Data.Array (Array, (!), array, assocs, bounds, elems, listArray)
import Test.QuickCheck

type Polinomio a = Array Int a

ej_pol1 :: Array Int Int
ej_pol1 = array (0,4) [(1,2),(2,-5),(4,7),(0,6),(3,0)]

ej_pol2 :: Array Int Double
ej_pol2 = array (0,4) [(1,2),(2,-5.2),(4,7),(0,6.5),(3,0)]

-- 1ª solución
-- ===========

valor1 :: Num a => Polinomio a -> a -> a
valor1 p b = sum [(p!i)*b^i | i <- [0..n]]
  where (_,n) = bounds p

-- 2ª solución
-- ===========

valor2 :: Num a => Polinomio a -> a -> a
valor2 p b = sum [(p!i)*b^i | i <- [0..length p - 1]]

-- 3ª solución
-- ===========

valor3 :: Num a => Polinomio a -> a -> a
valor3 p b = sum [v*b^i | (i,v) <- assocs p]

-- 4ª solución
-- ===========

valor4 :: Num a => Polinomio a -> a -> a
valor4 = valorLista4 . elems

valorLista4 :: Num a => [a] -> a -> a
valorLista4 xs b =
  sum [(xs !! i) * b^i | i <- [0..length xs - 1]]

-- 5ª solución
-- ===========

valor5 :: Num a => Polinomio a -> a -> a
valor5 = valorLista5 . elems

valorLista5 :: Num a => [a] -> a -> a
valorLista5 []     _ = 0
valorLista5 (x:xs) b = x + b * valorLista5 xs b

-- 6ª solución
-- ===========

valor6 :: Num a => Polinomio a -> a -> a
valor6 = valorLista6 . elems

valorLista6 :: Num a => [a] -> a -> a
valorLista6 xs b = aux xs
  where aux []     = 0
        aux (y:ys) = y + b * aux ys

-- 7ª solución
-- ===========

valor7 :: Num a => Polinomio a -> a -> a
valor7 = valorLista7 . elems

valorLista7 :: Num a => [a] -> a -> a
valorLista7 xs b = foldr (\y r -> y + b * r) 0 xs

-- 8ª solución
-- ===========

valor8 :: Num a => Polinomio a -> a -> a
valor8 = valorLista8 . elems

valorLista8 :: Num a => [a] -> a -> a
valorLista8 xs b = aux 0 (reverse xs)
  where aux r []     = r
        aux r (y:ys) = aux (y + r * b) ys

-- 9ª solución
-- ===========

valor9 :: Num a => Polinomio a -> a -> a
valor9 = valorLista9 . elems

valorLista9 :: Num a => [a] -> a -> a
valorLista9 xs b = aux 0 (reverse xs)
  where aux = foldl (\ r y -> y + r * b)

-- 10ª solución
-- ============

valor10 :: Num a => Polinomio a -> a -> a
valor10 p b =
  foldl (\ r y -> y + r * b) 0 (reverse (elems p))

-- 11ª solución
-- ============

valor11 :: Num a => Polinomio a -> a -> a
valor11 p b =
  foldl' (\ r y -> y + r * b) 0 (reverse (elems p))

-- 12ª solución
-- ============

valor12 :: Num a => Polinomio a -> a -> a
valor12 p b =
  sum (zipWith (*) (elems p) (iterate (* b) 1))

-- 13ª solución
-- ============

valor13 :: Num a => Polinomio a -> a -> a
valor13 p b =
  foldl' (+) 0 (zipWith (*) (elems p) (iterate (* b) 1))

-- Equivalencia de las definiciones
-- ================================

-- La propiedad es
prop_valor :: [Integer] -> Integer -> Bool
prop_valor xs b =
  all (== valor1 p b)
      [f p b | f <- [valor2,
                     valor3,
                     valor4,
                     valor5,
                     valor6,
                     valor7,
                     valor8,
                     valor9,
                     valor10,
                     valor11,
                     valor12,
                     valor13]]
  where p = listArray (0, length xs - 1) xs

-- La comprobación es
--    λ> quickCheck prop_valor
--    +++ OK, passed 100 tests.

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> length (show (valor1 (listArray (0,10^5) (repeat 1)) 2))
--    30104
--    (7.62 secs, 2,953,933,864 bytes)
--    λ> length (show (valor2 (listArray (0,10^5) (repeat 1)) 2))
--    30104
--    (8.26 secs, 2,953,933,264 bytes)
--    λ> length (show (valor3 (listArray (0,10^5) (repeat 1)) 2))
--    30104
--    (7.49 secs, 2,954,733,184 bytes)
--    λ> length (show (valor4 (listArray (0,10^5) (repeat 1)) 2))
--    30104
--    (84.80 secs, 2,956,333,712 bytes)
--    λ> length (show (valor5 (listArray (0,10^5) (repeat 1)) 2))
--    30104
--    (1.34 secs, 1,307,347,416 bytes)
--    λ> length (show (valor6 (listArray (0,10^5) (repeat 1)) 2))
--    30104
--    (1.26 secs, 1,308,114,752 bytes)
--    λ> length (show (valor7 (listArray (0,10^5) (repeat 1)) 2))
--    30104
--    (1.21 secs, 1,296,843,456 bytes)
--    λ> length (show (valor8 (listArray (0,10^5) (repeat 1)) 2))
--    30104
--    (1.28 secs, 1,309,591,744 bytes)
--    λ> length (show (valor9 (listArray (0,10^5) (repeat 1)) 2))
--    30104
--    (1.27 secs, 1,299,191,672 bytes)
--    λ> length (show (valor10 (listArray (0,10^5) (repeat 1)) 2))
--    30104
--    (1.30 secs, 1,299,191,432 bytes)
--    λ> length (show (valor11 (listArray (0,10^5) (repeat 1)) 2))
--    30104
--    (0.23 secs, 1,287,654,752 bytes)
--    λ> length (show (valor12 (listArray (0,10^5) (repeat 1)) 2))
--    30104
--    (0.75 secs, 1,309,506,968 bytes)

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

import Data.List (foldl')

import Data.Array (Array, (!), array, assocs, bounds, elems, listArray)

import Test.QuickCheck

type Polinomio a = Array Int a

ej_pol1 :: Array Int Int

ej_pol1 = array (0,4) [(1,2),(2,-5),(4,7),(0,6),(3,0)]

ej_pol2 :: Array Int Double

ej_pol2 = array (0,4) [(1,2),(2,-5.2),(4,7),(0,6.5),(3,0)]

-- 1ª solución

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

valor1 :: Num a => Polinomio a -> a -> a

valor1 p b = sum [(p!i)*b^i | i <- [0..n]]

where (_,n) = bounds p

-- 2ª solución

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

valor2 :: Num a => Polinomio a -> a -> a

valor2 p b = sum [(p!i)*b^i | i <- [0..length p - 1]]

-- 3ª solución

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

valor3 :: Num a => Polinomio a -> a -> a

valor3 p b = sum [v*b^i | (i,v) <- assocs p]

-- 4ª solución

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

valor4 :: Num a => Polinomio a -> a -> a

valor4 = valorLista4 . elems

valorLista4 :: Num a => [a] -> a -> a

valorLista4 xs b =

sum [(xs !! i) * b^i | i <- [0..length xs - 1]]

-- 5ª solución

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

valor5 :: Num a => Polinomio a -> a -> a

valor5 = valorLista5 . elems

valorLista5 :: Num a => [a] -> a -> a

valorLista5 [] _ = 0

valorLista5 (x:xs) b = x + b * valorLista5 xs b

-- 6ª solución

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

valor6 :: Num a => Polinomio a -> a -> a

valor6 = valorLista6 . elems

valorLista6 :: Num a => [a] -> a -> a

valorLista6 xs b = aux xs

where aux [] = 0

aux (y:ys) = y + b * aux ys

-- 7ª solución

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

valor7 :: Num a => Polinomio a -> a -> a

valor7 = valorLista7 . elems

valorLista7 :: Num a => [a] -> a -> a

valorLista7 xs b = foldr (\y r -> y + b * r) 0 xs

-- 8ª solución

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

valor8 :: Num a => Polinomio a -> a -> a

valor8 = valorLista8 . elems

valorLista8 :: Num a => [a] -> a -> a

valorLista8 xs b = aux 0 (reverse xs)

where aux r [] = r

aux r (y:ys) = aux (y + r * b) ys

-- 9ª solución

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

valor9 :: Num a => Polinomio a -> a -> a

valor9 = valorLista9 . elems

valorLista9 :: Num a => [a] -> a -> a

valorLista9 xs b = aux 0 (reverse xs)

where aux = foldl (\ r y -> y + r * b)

-- 10ª solución

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

valor10 :: Num a => Polinomio a -> a -> a

valor10 p b =

foldl (\ r y -> y + r * b) 0 (reverse (elems p))

-- 11ª solución

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

valor11 :: Num a => Polinomio a -> a -> a

valor11 p b =

foldl' (\ r y -> y + r * b) 0 (reverse (elems p))

-- 12ª solución

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

valor12 :: Num a => Polinomio a -> a -> a

valor12 p b =

sum (zipWith (*) (elems p) (iterate (* b) 1))

-- 13ª solución

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

valor13 :: Num a => Polinomio a -> a -> a

valor13 p b =

foldl' (+) 0 (zipWith (*) (elems p) (iterate (* b) 1))

-- Equivalencia de las definiciones

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

-- La propiedad es

prop_valor :: [Integer] -> Integer -> Bool

prop_valor xs b =

all (== valor1 p b)

[f p b | f <- [valor2,

valor3,

valor4,

valor5,

valor6,

valor7,

valor8,

valor9,

valor10,

valor11,

valor12,

valor13]]

where p = listArray (0, length xs - 1) xs

-- La comprobación es

-- λ> quickCheck prop_valor

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- La comparación es

-- λ> length (show (valor1 (listArray (0,10^5) (repeat 1)) 2))

-- 30104

-- (7.62 secs, 2,953,933,864 bytes)

-- λ> length (show (valor2 (listArray (0,10^5) (repeat 1)) 2))

-- 30104

-- (8.26 secs, 2,953,933,264 bytes)

-- λ> length (show (valor3 (listArray (0,10^5) (repeat 1)) 2))

-- 30104

-- (7.49 secs, 2,954,733,184 bytes)

-- λ> length (show (valor4 (listArray (0,10^5) (repeat 1)) 2))

-- 30104

-- (84.80 secs, 2,956,333,712 bytes)

-- λ> length (show (valor5 (listArray (0,10^5) (repeat 1)) 2))

-- 30104

-- (1.34 secs, 1,307,347,416 bytes)

-- λ> length (show (valor6 (listArray (0,10^5) (repeat 1)) 2))

-- 30104

-- (1.26 secs, 1,308,114,752 bytes)

-- λ> length (show (valor7 (listArray (0,10^5) (repeat 1)) 2))

-- 30104

-- (1.21 secs, 1,296,843,456 bytes)

-- λ> length (show (valor8 (listArray (0,10^5) (repeat 1)) 2))

-- 30104

-- (1.28 secs, 1,309,591,744 bytes)

-- λ> length (show (valor9 (listArray (0,10^5) (repeat 1)) 2))

-- 30104

-- (1.27 secs, 1,299,191,672 bytes)

-- λ> length (show (valor10 (listArray (0,10^5) (repeat 1)) 2))

-- 30104

-- (1.30 secs, 1,299,191,432 bytes)

-- λ> length (show (valor11 (listArray (0,10^5) (repeat 1)) 2))

-- 30104

-- (0.23 secs, 1,287,654,752 bytes)

-- λ> length (show (valor12 (listArray (0,10^5) (repeat 1)) 2))

-- 30104

-- (0.75 secs, 1,309,506,968 bytes)

El código se encuentra en GitHub.

La elaboración de las soluciones se encuentran en el siguiente vídeo

Polinomios de Fibonacci

PorJosé A. Alonso 21-mayo-201828-mayo-2018

La sucesión de polinomios de Fibonacci se define por

   p(0) = 0
   p(1) = 1
   p(n) = x*p(n-1) + p(n-2)

p(0) = 0

p(1) = 1

p(n) = x*p(n-1) + p(n-2)

Los primeros términos de la sucesión son

   p(2) = x
   p(3) = x^2 + 1
   p(4) = x^3 + 2*x
   p(5) = x^4 + 3*x^2 + 1

p(2) = x

p(3) = x^2 + 1

p(4) = x^3 + 2*x

p(5) = x^4 + 3*x^2 + 1

Definir la lista

   sucPolFib :: [Polinomio Integer]

1	sucPolFib :: [Polinomio Integer]

tal que sus elementos son los polinomios de Fibonacci. Por ejemplo,

   λ> take 7 sucPolFib
   [0,1,1*x,x^2 + 1,x^3 + 2*x,x^4 + 3*x^2 + 1,x^5 + 4*x^3 + 3*x]
   λ> sum (map grado (take 3000 sucPolFib2))
   4495501

λ> take 7 sucPolFib

[0,1,1*x,x^2 + 1,x^3 + 2*x,x^4 + 3*x^2 + 1,x^5 + 4*x^3 + 3*x]

λ> sum (map grado (take 3000 sucPolFib2))

4495501

Comprobar con QuickCheck que el valor del n-ésimo término de sucPolFib para x=1 es el n-ésimo término de la sucesión de Fibonacci 0, 1, 1, 2, 3, 5, 8, …

Nota. Limitar la búsqueda a ejemplos pequeños usando

   quickCheckWith (stdArgs {maxSize=5}) prop_polFib

1	quickCheckWith (stdArgs {maxSize=5}) prop_polFib

Soluciones

import Data.List (genericIndex)
import I1M.PolOperaciones
import Test.QuickCheck

-- 1ª solución
-- ===========

sucPolFib :: [Polinomio Integer]
sucPolFib = [polFibR n | n <- [0..]]

polFibR :: Integer -> Polinomio Integer
polFibR 0 = polCero
polFibR 1 = polUnidad
polFibR n = 
  sumaPol (multPol (consPol 1 1 polCero) (polFibR (n-1)))
          (polFibR (n-2))

-- 2ª definición (dinámica)
-- ========================

sucPolFib2 :: [Polinomio Integer]
sucPolFib2 = 
  polCero : polUnidad : zipWith f (tail sucPolFib2) sucPolFib2
  where f p = sumaPol (multPol (consPol 1 1 polCero) p)

-- La propiedad es
prop_polFib :: Integer -> Property
prop_polFib n = 
    n >= 0 ==> valor (polFib n) 1 == fib n
    where polFib n = sucPolFib2 `genericIndex` n
          fib n    = fibs `genericIndex` n

fibs :: [Integer]
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

-- La comprobación es
--    ghci> quickCheckWith (stdArgs {maxSize=5}) prop_polFib
--    +++ OK, passed 100 tests.

import Data.List (genericIndex)

import I1M.PolOperaciones

import Test.QuickCheck

-- 1ª solución

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

sucPolFib :: [Polinomio Integer]

sucPolFib = [polFibR n | n <- [0..]]

polFibR :: Integer -> Polinomio Integer

polFibR 0 = polCero

polFibR 1 = polUnidad

polFibR n =

sumaPol (multPol (consPol 1 1 polCero) (polFibR (n-1)))

(polFibR (n-2))

-- 2ª definición (dinámica)

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

sucPolFib2 :: [Polinomio Integer]

sucPolFib2 =

polCero : polUnidad : zipWith f (tail sucPolFib2) sucPolFib2

where f p = sumaPol (multPol (consPol 1 1 polCero) p)

-- La propiedad es

prop_polFib :: Integer -> Property

prop_polFib n =

n >= 0 ==> valor (polFib n) 1 == fib n

where polFib n = sucPolFib2 `genericIndex` n

fib n = fibs `genericIndex` n

fibs :: [Integer]

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

-- La comprobación es

-- ghci> quickCheckWith (stdArgs {maxSize=5}) prop_polFib

-- +++ OK, passed 100 tests.

Polinomio digital

PorJosé A. Alonso 1-mayo-20188-mayo-2018

Definir la función

   polinomioDigital :: Int -> Polinomio Int

1	polinomioDigital :: Int -> Polinomio Int

tal que (polinomioDigital n) es el polinomio cuyos coeficientes son los dígitos de n. Por ejemplo,

   λ> polinomioDigital 5703 
   5*x^3 + 7*x^2 + 3

1 2	λ> polinomioDigital 5703 5x^3 + 7x^2 + 3

Nota: Este ejercicio debe realizarse usando únicamente las funciones de la librería I1M.Pol que se encuentra aquí y se describe aquí.

Soluciones

import I1M.Pol

polinomioDigital :: Int -> Polinomio Int
polinomioDigital = creaPolDensa . digitos

-- (digitos n) es la lista de las dígitos de n. Por ejemplo,        
--    dígitos 142857  ==  [1,4,2,8,5,7]
digitos :: Int -> [Int]
digitos n = [read [x]| x <- show n]

-- (creaPolDensa xs) es el polinomio cuya representación densa es
-- xs. Por ejemplo, 
--    creaPolDensa [7,0,0,4,0,3]  ==  7*x^5 + 4*x^2 + 3
creaPolDensa :: (Num a, Eq a) => [a] -> Polinomio a
creaPolDensa []     = polCero
creaPolDensa (x:xs) = consPol (length xs) x (creaPolDensa xs)

import I1M.Pol

polinomioDigital :: Int -> Polinomio Int

polinomioDigital = creaPolDensa . digitos

-- (digitos n) es la lista de las dígitos de n. Por ejemplo,

-- dígitos 142857 == [1,4,2,8,5,7]

digitos :: Int -> [Int]

digitos n = [read [x]| x <- show n]

-- (creaPolDensa xs) es el polinomio cuya representación densa es

-- xs. Por ejemplo,

-- creaPolDensa [7,0,0,4,0,3] == 7*x^5 + 4*x^2 + 3

creaPolDensa :: (Num a, Eq a) => [a] -> Polinomio a

creaPolDensa [] = polCero

creaPolDensa (x:xs) = consPol (length xs) x (creaPolDensa xs)

Polinomios de Fibonacci

PorJosé A. Alonso 23-mayo-201726-marzo-2022

La sucesión de polinomios de Fibonacci se define por

   p(0) = 0
   p(1) = 1
   p(n) = x*p(n-1) + p(n-2)

p(0) = 0

p(1) = 1

p(n) = x*p(n-1) + p(n-2)

Los primeros términos de la sucesión son

   p(2) = x
   p(3) = x^2 + 1
   p(4) = x^3 + 2*x
   p(5) = x^4 + 3*x^2 + 1

p(2) = x

p(3) = x^2 + 1

p(4) = x^3 + 2*x

p(5) = x^4 + 3*x^2 + 1

Definir la lista

   sucPolFib :: [Polinomio Integer]

1	sucPolFib :: [Polinomio Integer]

tal que sus elementos son los polinomios de Fibonacci. Por ejemplo,

   λ> take 7 sucPolFib
   [0,1,1*x,x^2 + 1,x^3 + 2*x,x^4 + 3*x^2 + 1,x^5 + 4*x^3 + 3*x]
   λ> sum (map grado (take 3000 sucPolFib2))
   4495501

λ> take 7 sucPolFib

[0,1,1*x,x^2 + 1,x^3 + 2*x,x^4 + 3*x^2 + 1,x^5 + 4*x^3 + 3*x]

λ> sum (map grado (take 3000 sucPolFib2))

4495501

Comprobar con QuickCheck que el valor del n-ésimo término de sucPolFib para x=1 es el n-ésimo término de la sucesión de Fibonacci 0, 1, 1, 2, 3, 5, 8, …

Nota. Limitar la búsqueda a ejemplos pequeños usando

   quickCheckWith (stdArgs {maxSize=5}) prop_polFib

1	quickCheckWith (stdArgs {maxSize=5}) prop_polFib

Soluciones

[schedule expon=’2017-05-30′ expat=»06:00″]

Las soluciones se pueden escribir en los comentarios hasta el 30 de mayo.
El código se debe escribir entre una línea con <pre lang=»haskell»> y otra con </pre>

[/schedule]

[schedule on=’2017-05-30′ at=»06:00″]

import Data.List (genericIndex)
import I1M.PolOperaciones
import Test.QuickCheck

-- 1ª solución
-- ===========

sucPolFib :: [Polinomio Integer]
sucPolFib = [polFibR n | n <- [0..]]

polFibR :: Integer -> Polinomio Integer
polFibR 0 = polCero
polFibR 1 = polUnidad
polFibR n = 
  sumaPol (multPol (consPol 1 1 polCero) (polFibR (n-1)))
          (polFibR (n-2))

-- 2ª definición (dinámica)
-- ========================

sucPolFib2 :: [Polinomio Integer]
sucPolFib2 = 
  polCero : polUnidad : zipWith f (tail sucPolFib2) sucPolFib2
  where f p = sumaPol (multPol (consPol 1 1 polCero) p)

-- La propiedad es
prop_polFib :: Integer -> Property
prop_polFib n = 
    n >= 0 ==> valor (polFib n) 1 == fib n
    where polFib n = sucPolFib2 `genericIndex` n
          fib n    = fibs `genericIndex` n

fibs :: [Integer]
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

-- La comprobación es
--    ghci> quickCheckWith (stdArgs {maxSize=5}) prop_polFib
--    +++ OK, passed 100 tests.

import Data.List (genericIndex)

import I1M.PolOperaciones

import Test.QuickCheck

-- 1ª solución

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

sucPolFib :: [Polinomio Integer]

sucPolFib = [polFibR n | n <- [0..]]

polFibR :: Integer -> Polinomio Integer

polFibR 0 = polCero

polFibR 1 = polUnidad

polFibR n =

sumaPol (multPol (consPol 1 1 polCero) (polFibR (n-1)))

(polFibR (n-2))

-- 2ª definición (dinámica)

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

sucPolFib2 :: [Polinomio Integer]

sucPolFib2 =

polCero : polUnidad : zipWith f (tail sucPolFib2) sucPolFib2

where f p = sumaPol (multPol (consPol 1 1 polCero) p)

-- La propiedad es

prop_polFib :: Integer -> Property

prop_polFib n =

n >= 0 ==> valor (polFib n) 1 == fib n

where polFib n = sucPolFib2 `genericIndex` n

fib n = fibs `genericIndex` n

fibs :: [Integer]

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

-- La comprobación es

-- ghci> quickCheckWith (stdArgs {maxSize=5}) prop_polFib

-- +++ OK, passed 100 tests.

[/schedule]

El tipo abstracto de datos de los polinomios

1. El tipo abstracto de datos de los polinomios

2. Los polinomios en Haskell

2.1. El tipo abstracto de datos de los polinomios en Haskell

2.2. Implementación de los polinomios mediante tipos de datos algebraicos

2.3. Implementación de polinomios mediante listas densas

2.4. Implementación de polinomios mediante listas dispersas

3. Los polinomios en Python

3.1. El tipo abstracto de los polinomios en Python

3.2. Implementación de los polinomios mediante listas densas

3.3. Implementación de los polinomios mediante listas dispersas

Valores de polinomios representados con vectores

Soluciones

Polinomios de Fibonacci

Soluciones

Polinomio digital

Soluciones

Polinomios de Fibonacci

Soluciones

Entradas recientes

Buscar

Correo electrónico