I1M2012: El TAD de los polinomios en Haskell (2)
En la clase de hoy de Informática de 1º del Grado en Matemáticas hemos continuado el estudio del tipo abstracto de los polinomios y su implementación en Haskell que comenzamos en la clase anterior. Concretamente, hemos estudiado la implementaciones en Haskell del TAD de los polinomios mediante listas densas y las operaciones con los polinomios usando el TAD.
Las transparencias usadas en la clase son las páginas 24-55 del tema 21
El código de la representación densa del TAD de los polinomios es
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 |
module PolRepDensa ( Polinomio, polCero, -- Polinomio a esPolCero, -- Num a => Polinomio a -> Bool consPol, -- Num a => Int -> a -> Polinomio a -> Polinomio a grado, -- Polinomio a -> Int coefLider, -- Num a => Polinomio a -> a restoPol -- Polinomio a -> Polinomio a ) where -- --------------------------------------------------------------------- -- TAD de los polinomios mediante listas densas. -- -- --------------------------------------------------------------------- -- Representaremos un polinomio mediante una lista de pares (grado,coef), -- ordenados en orden decreciente según el grado. Por ejemplo, el -- polinomio -- 6x^4 -5x^2 + 4x -7 -- se representa por -- [(4,6),(2,-5),(1,4),(0,-7)]. data Polinomio a = Pol [(Int,a)] deriving Eq -- --------------------------------------------------------------------- -- Escritura de los polinomios -- -- --------------------------------------------------------------------- instance (Num t, Show t, Eq t) => Show (Polinomio t) where show pol | esPolCero pol = "0" | n == 0 && esPolCero p = show a | n == 0 = concat [show a, " + ", show p] | n == 1 && esPolCero p = concat [show a, "*x"] | n == 1 = concat [show a, "*x + ", show p] | a == 1 && esPolCero p = concat ["x^", show n] | esPolCero p = concat [show a, "*x^", show n] | a == 1 = concat ["x^", show n, " + ", show p] | otherwise = concat [show a, "*x^", show n, " + ", show p] where n = grado pol a = coefLider pol p = restoPol pol -- --------------------------------------------------------------------- -- Ejemplos de polinomios -- -- --------------------------------------------------------------------- -- Ejemplos de polinomios con coeficientes enteros: ejPol1, ejPol2, ejPol3:: Polinomio Int ejPol1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero)) ejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero)) ejPol3 = consPol 4 6 (consPol 1 2 polCero) -- Comprobación de escritura: -- > ejPol1 -- 3*x^4 + -5*x^2 + 3 -- > ejPol2 -- x^5 + 5*x^2 + 4*x -- > ejPol3 -- 6*x^4 + 2*x -- --------------------------------------------------------------------- -- Implementación de la especificación -- -- --------------------------------------------------------------------- -- polCero es el polinomio cero. Por ejemplo, -- ghci> polCero -- 0 polCero :: Num a => Polinomio a polCero = Pol [] -- (esPolCero p) se verifica si p es el polinomio cero. Por ejemplo, -- esPolCero polCero == True -- esPolCero ejPol1 == False esPolCero :: Num a => Polinomio a -> Bool esPolCero (Pol []) = True esPolCero _ = False -- (consPol n b p) es el polinomio bx^n+p. Por ejemplo, -- ejPol2 == x^5 + 5*x^2 + 4*x -- consPol 3 0 ejPol2 == x^5 + 5*x^2 + 4*x -- consPol 3 2 polCero == 2*x^3 -- consPol 6 7 ejPol2 == 7*x^6 + x^5 + 5*x^2 + 4*x -- consPol 4 7 ejPol2 == x^5 + 7*x^4 + 5*x^2 + 4*x -- consPol 5 7 ejPol2 == 8*x^5 + 5*x^2 + 4*x consPol :: (Num a, Eq a) => Int -> a -> Polinomio a -> Polinomio a consPol _ 0 p = p consPol n b p@(Pol xs) | esPolCero p = Pol [(n,b)] | n > m = Pol ((n,b):xs) | n < m = consPol m c (consPol n b (Pol (tail xs))) | b+c == 0 = Pol (tail xs) | otherwise = Pol ((n,b+c):(tail xs)) where c = coefLider p m = grado p -- (grado p) es el grado del polinomio p. Por ejemplo, -- ejPol3 == 6*x^4 + 2*x -- grado ejPol3 == 4 grado:: Polinomio a -> Int grado (Pol []) = 0 grado (Pol ((n,_):_)) = n -- (coefLider p) es el coeficiente líder del polinomio p. Por ejemplo, -- ejPol3 == 6*x^4 + 2*x -- coefLider ejPol3 == 6 coefLider:: Num t => Polinomio t -> t coefLider (Pol []) = 0 coefLider (Pol ((_,b):_)) = b -- (restoPol p) es el resto del polinomio p. Por ejemplo, -- ejPol3 == 6*x^4 + 2*x -- restoPol ejPol3 == 2*x -- ejPol2 == x^5 + 5*x^2 + 4*x -- restoPol ejPol2 == 5*x^2 + 4*x restoPol :: Num t => Polinomio t -> Polinomio t restoPol (Pol []) = polCero restoPol (Pol [_]) = polCero restoPol (Pol (_:xs)) = Pol xs |
El código de las operaciones con el TAD de los polinomios es
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 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 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 |
module PolOperaciones (module Pol, module PolOperaciones) where -- --------------------------------------------------------------------- -- Importación de librerías -- -- --------------------------------------------------------------------- -- Nota: Hay que elegir una implementación del TAD de los polinomios. import PolRepTDA as Pol -- import PolRepDispersa as Pol -- import PolRepDensa as Pol import Test.QuickCheck -- --------------------------------------------------------------------- -- Ejemplos -- -- --------------------------------------------------------------------- -- Ejemplos de polinomios con coeficientes enteros: ejPol1, ejPol2, ejPol3, ejTerm:: Polinomio Int ejPol1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero)) ejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero)) ejPol3 = consPol 4 6 (consPol 1 2 polCero) ejTerm = consPol 1 4 polCero -- --------------------------------------------------------------------- -- Generador de polinomios -- -- --------------------------------------------------------------------- -- (genPol n) es un generador de polinomios. Por ejemplo, -- ghci> sample (genPol 1) -- 7*x^9 + 9*x^8 + 10*x^7 + -14*x^5 + -15*x^2 + -10 -- -4*x^8 + 2*x -- -8*x^9 + 4*x^8 + 2*x^6 + 4*x^5 + -6*x^4 + 5*x^2 + -8*x -- -9*x^9 + x^5 + -7 -- 8*x^10 + -9*x^7 + 7*x^6 + 9*x^5 + 10*x^3 + -1*x^2 -- 7*x^10 + 5*x^9 + -5 -- -8*x^10 + -7 -- -5*x -- 5*x^10 + 4*x^4 + -3 -- 3*x^3 + -4 -- 10*x genPol :: (Arbitrary a, Num a, Eq a) => Int -> Gen (Polinomio a) genPol 0 = return polCero genPol n = do n <- choose (0,10) b <- arbitrary p <- genPol (div n 2) return (consPol n b p) instance (Arbitrary a, Num a, Eq a) => Arbitrary (Polinomio a) where arbitrary = sized genPol -- --------------------------------------------------------------------- -- Funciones sobre términos -- -- --------------------------------------------------------------------- -- (creaTermino n a) es el término a*x^n. Por ejemplo, -- creaTermino 2 5 == 5*x^2 creaTermino:: (Num t, Eq t) => Int -> t -> Polinomio t creaTermino n a = consPol n a polCero -- (termLider p) es el término líder del polinomio p. Por ejemplo, -- ejPol2 == x^5 + 5*x^2 + 4*x -- termLider ejPol2 == x^5 termLider:: (Num t, Eq t) => Polinomio t -> Polinomio t termLider p = creaTermino (grado p) (coefLider p) -- --------------------------------------------------------------------- -- Suma de polinomios -- -- --------------------------------------------------------------------- -- (sumaPol p q) es la suma de los polinomios p y q. Por ejemplo, -- ejPol1 == 3*x^4 + -5*x^2 + 3 -- ejPol2 == x^5 + 5*x^2 + 4*x -- sumaPol ejPol1 ejPol2 == x^5 + 3*x^4 + 4*x + 3 sumaPol:: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a sumaPol p q | esPolCero p = q | esPolCero q = p | n1 > n2 = consPol n1 a1 (sumaPol r1 q) | n1 < n2 = consPol n2 a2 (sumaPol p r2) | a1+a2 /= 0 = consPol n1 (a1+a2) (sumaPol r1 r2) | otherwise = sumaPol r1 r2 where n1 = grado p a1 = coefLider p r1 = restoPol p n2 = grado q a2 = coefLider q r2 = restoPol q -- Propiedad. El polinomio cero es el elemento neutro de la suma. prop_neutroSumaPol :: Polinomio Int -> Bool prop_neutroSumaPol p = sumaPol polCero p == p -- Comprobación con QuickCheck. -- ghci> quickCheck prop_neutroSumaPol -- OK, passed 100 tests. -- Propiedad. La suma es conmutativa. prop_conmutativaSuma :: Polinomio Int -> Polinomio Int -> Bool prop_conmutativaSuma p q = sumaPol p q == sumaPol q p -- Comprobación: -- ghci> quickCheck prop_conmutativaSuma -- OK, passed 100 tests. -- --------------------------------------------------------------------- -- Producto de polinomios -- -- --------------------------------------------------------------------- -- (multPorTerm t p) es el producto del término t por el polinomio -- p. Por ejemplo, -- ejTerm == 4*x -- ejPol2 == x^5 + 5*x^2 + 4*x -- multPorTerm ejTerm ejPol2 == 4*x^6 + 20*x^3 + 16*x^2 multPorTerm :: (Num t, Eq t) => Polinomio t -> Polinomio t -> Polinomio t multPorTerm term pol | esPolCero pol = polCero | otherwise = consPol (n+m) (a*b) (multPorTerm term r) where n = grado term a = coefLider term m = grado pol b = coefLider pol r = restoPol pol -- (multPol p q) es el producto de los polinomios p y q. Por -- ejemplo, -- ghci> ejPol1 -- 3*x^4 + -5*x^2 + 3 -- ghci> ejPol2 -- x^5 + 5*x^2 + 4*x -- ghci> multPol ejPol1 ejPol2 -- 3*x^9 + -5*x^7 + 15*x^6 + 15*x^5 + -25*x^4 + -20*x^3 + 15*x^2 + 12*x multPol :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a multPol p q | esPolCero p = polCero | otherwise = sumaPol (multPorTerm (termLider p) q) (multPol (restoPol p) q) -- Propiedad. El producto de polinomios es conmutativo. prop_conmutativaProducto :: Polinomio Int -> Polinomio Int -> Bool prop_conmutativaProducto p q = multPol p q == multPol q p -- La comprobación es -- ghci> quickCheck prop_conmutativaProducto -- OK, passed 100 tests. -- El producto es distributivo respecto de la suma. prop_distributivaProductoSuma :: Polinomio Int -> Polinomio Int -> Polinomio Int -> Bool prop_distributivaProductoSuma p q r = multPol p (sumaPol q r) == sumaPol (multPol p q) (multPol p r) -- Comprobación: -- ghci> quickCheck prop_distributivaProductoSuma -- OK, passed 100 tests. -- polUnidad es el polinomio unidad. Por ejemplo, -- ghci> polUnidad -- 1 polUnidad:: (Num t, Eq t) => Polinomio t polUnidad = consPol 0 1 polCero -- Propiedad. El polinomio unidad es el elemento neutro del producto. prop_polUnidad :: Polinomio Int -> Bool prop_polUnidad p = multPol p polUnidad == p -- Comprobación: -- ghci> quickCheck prop_polUnidad -- OK, passed 100 tests. -- --------------------------------------------------------------------- -- Valor de un polinomio en un punto -- -- --------------------------------------------------------------------- -- (valor p c) es el valor del polinomio p al sustituir su variable por -- c. Por ejemplo, -- ejPol1 == 3*x^4 + -5*x^2 + 3 -- valor ejPol1 0 == 3 -- valor ejPol1 1 == 1 -- valor ejPol1 (-2) == 31 valor:: (Num a, Eq a) => Polinomio a -> a -> a valor p c | esPolCero p = 0 | otherwise = b*c^n + valor r c where n = grado p b = coefLider p r = restoPol p -- --------------------------------------------------------------------- -- Verificación de raices de polinomios -- -- --------------------------------------------------------------------- -- (esRaiz c p) se verifica si c es una raiz del polinomio p. por -- ejemplo, -- ejPol3 == 6*x^4 + 2*x -- esRaiz 1 ejPol3 == False -- esRaiz 0 ejPol3 == True esRaiz:: (Num a, Eq a) => a -> Polinomio a -> Bool esRaiz c p = valor p c == 0 -- --------------------------------------------------------------------- -- Derivación de polinomios -- -- --------------------------------------------------------------------- -- (derivada p) es la derivada del polinomio p. Por ejemplo, -- ejPol2 == x^5 + 5*x^2 + 4*x -- derivada ejPol2 == 5*x^4 + 10*x + 4 derivada :: Polinomio Int -> Polinomio Int derivada p | n == 0 = polCero | otherwise = consPol (n-1) (n*b) (derivada r) where n = grado p b = coefLider p r = restoPol p -- Propiedad. La derivada de la suma es la suma de las derivadas. prop_derivada :: Polinomio Int -> Polinomio Int -> Bool prop_derivada p q = derivada (sumaPol p q) == sumaPol (derivada p) (derivada q) -- Comprobación -- ghci> quickCheck prop_derivada -- OK, passed 100 tests. -- --------------------------------------------------------------------- -- Resta de polinomios -- -- --------------------------------------------------------------------- -- (resta p q) es la el polinomio obtenido restándole a p el q. Por -- ejemplo, -- ejPol1 == 3*x^4 + -5*x^2 + 3 -- ejPol2 == x^5 + 5*x^2 + 4*x -- restaPol ejPol1 ejPol2 == -1*x^5 + 3*x^4 + -10*x^2 + -4*x + 3 restaPol :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a restaPol p q = sumaPol p (multPorTerm (creaTermino 0 (-1)) q) |