El tipo abstracto de datos de los polinomios en Haskell
Como comenté en la entrada anterior, estoy elaborando los apuntes de los temas del curso Informática del Grado en Matemáticas (2010-11) no incluidos aún en el libro Temas de programación funcional (2010-11).
Uno de los temas en los que he estado trabajando últimamente es en el de los tipos abstractos de datos (TAD). Además de los habituales (pilas, colas, colas de prioridad, conjuntos, tablas, árboles binarios de búsqueda, montículos y árboles AVL), un TAD especialmente adecuado para los estudiantes de matemáticas es el de polinomios. A continuación muestro la implementación que estoy diseñando en Haskell para incluirla en el tema.
Del código deseo resaltar las siguientes características:
- Independización de los resultados de las implementaciones mediante las funciones de escritura.
- Comprobación de las implementaciones con QuickCheck mediante las funciones generadoras de polinomios.
A continuación muestro los ficheros con los códigos desarrollados.
PolRepTDA.hs: Implementación de los polinomios mediante tipos de datos algebraicos
|
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 |
module PolRepTDA ( Polinomio, polCero, esPolCero, consPol, grado, coefLider, restoPol ) where -- --------------------------------------------------------------------- -- Importaciones -- -- --------------------------------------------------------------------- import Data.Char import Data.List import Test.QuickCheck -- --------------------------------------------------------------------- -- TAD de los polinomios mediante un tipo de dato algebraico. -- -- --------------------------------------------------------------------- -- Representamos un polinomio mediante los constructores ConsPol y -- PolCero. Por ejemplo, el polinomio -- 6x^4 -5x^2 + 4x -7 -- se representa por -- ConsPol 4 6 (ConsPol 2 (-5) (ConsPol 1 4 (ConsPol 0 (-7) PolCero))) data Polinomio a = PolCero | ConsPol Int a (Polinomio a) deriving Eq -- --------------------------------------------------------------------- -- Implementación de la especificación -- -- --------------------------------------------------------------------- -- polCero es el polinomio cero. Por ejemplo, -- > polCero -- 0 polCero :: Polinomio a polCero = PolCero -- (esPolCero p) se verifica si p es el polinomio cero. Por ejemplo, -- esPolCero polCero == True -- esPolCero ejPol1 == False esPolCero :: Polinomio a -> Bool esPolCero PolCero = True esPolCero _ = False -- (consPol n b p) es el polinomio bx^n+p. Por ejemplo, -- ejPol2 == x^5 + 5*x^2 + 4*x -- consPol 3 0 ejPol2 == x^5 + 5*x^2 + 4*x -- consPol 3 2 polCero == 2*x^3 -- consPol 6 7 ejPol2 == 7*x^6 + x^5 + 5*x^2 + 4*x -- consPol 4 7 ejPol2 == x^5 + 7*x^4 + 5*x^2 + 4*x -- consPol 5 (-1) ejPol2 == 5*x^2 + 4*x -- consPol 5 7 ejPol2 == 8*x^5 + 5*x^2 + 4*x consPol :: Num 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 -- --------------------------------------------------------------------- -- Propiedades -- -- --------------------------------------------------------------------- -- Propiedad de constructores y destructores de polinomios prop_polinomios :: Polinomio Int -> Bool prop_polinomios p = consPol (grado p) (coefLider p) (restoPol p) == p -- Comprobación -- > quickCheck prop_polinomios -- +++ OK, passed 100 tests. -- --------------------------------------------------------------------- -- Escritura de los polinomios -- -- --------------------------------------------------------------------- instance Num a => Show (Polinomio a) where show PolCero = "0" show (ConsPol 0 b PolCero) = show b show (ConsPol 0 b p) = concat [show b, " + ", show p] show (ConsPol 1 b PolCero) = concat [show b, "*x"] show (ConsPol 1 b p) = concat [show b, "*x + ", show p] show (ConsPol n 1 PolCero) = concat ["x^", show n] show (ConsPol n b PolCero) = concat [show b, "*x^", show n] show (ConsPol n 1 p) = concat ["x^", show n, " + ", show p] show (ConsPol n b p) = concat [show b, "*x^", show n, " + ", show p] -- --------------------------------------------------------------------- -- 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 -- --------------------------------------------------------------------- -- Generador de polinomios -- -- --------------------------------------------------------------------- -- Generador de polinomios -- > sample (arbitrary :: Gen (Polinomio Int)) -- 0 -- 0 -- 0 -- 0 -- -5*x^2 -- 10*x -- 11*x^16 + x^15 + -15*x^13 + 8*x^10 + -17*x^9 + 15*x^8 + -3*x^4 -- -5*x^23 + -2*x^15 -- 35*x^39 -- 0 -- -231*x^69 + 200*x^43 genPol :: (Arbitrary a, Num a) => Int -> Gen (Polinomio a) genPol 0 = return polCero genPol n = oneof [return polCero, do n <- arbitrary :: Gen Int a <- arbitrary p <- genPol (div n 2) return (consPol (abs n) a p)] instance (Arbitrary a, Num a) => Arbitrary (Polinomio a) where arbitrary = sized genPol |
EjemplosPol.hs: Ejemplos de polinomios
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
module EjemplosPol where -- Elegir una de las representaciones import PolRepTDA -- import PolRepDispersa -- import PolRepDensa -- 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 |
PolOperaciones.hs: Operaciones con polinomios.
|
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 |
module PolOperaciones where -- --------------------------------------------------------------------- -- Importación de librerías -- -- --------------------------------------------------------------------- -- Nota: Para usarlo, -- 1. Elegir una de las representaciones (PolRep*). -- 2. Elegir la misma representación en EjemplosPol.hs import PolRepTDA -- import PolRepDispersa -- import PolRepDensa import EjemplosPol import Test.QuickCheck -- --------------------------------------------------------------------- -- 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 => Int -> t -> Polinomio t creaTermino n a = consPol n a polCero -- (termLider p) es el término líder del polinomio p. -- ejPol2 == x^5 + 5*x^2 + 4*x -- termLider ejPol2 == x^5 termLider:: Num 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 => 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 -- Elemento neutro de la suma: prop_neutroSumaPol p = sumaPol polCero p == p -- Comprobación con QuickCheck. -- Main> quickCheck prop_neutroSumaPol -- OK, passed 100 tests. -- Propiedad conmutativa: prop_conmutativaSuma p q = sumaPol p q == sumaPol q p -- Comprobación: -- *Main> 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 => 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, -- *Main> ejPol1 -- 3*x^4 + -5*x^2 + 3 -- *Main> ejPol2 -- x^5 + 5*x^2 + 4*x -- *Main> 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 => Polinomio a -> Polinomio a -> Polinomio a multPol p q | esPolCero p = polCero | otherwise = sumaPol (multPorTerm (termLider p) q) (multPol (restoPol p) q) -- Propiedad conmutativa del producto: prop_conmutativaProducto p q = multPol p q == multPol q p -- La comprobación es -- *Main> quickCheck prop_conmutativaProducto -- OK, passed 100 tests. -- Proopiedad distributiva del producto respecto de la suma: prop_distributivaProductoSuma p q r = multPol p (sumaPol q r) == sumaPol (multPol p q) (multPol p r) -- Comprobación: -- *Main> quickCheck prop_distributivaProductoSuma -- OK, passed 100 tests. -- polUnidad es el polinomio unidad. Por ejemplo, -- *Main> polUnidad -- 1 polUnidad:: Num t => Polinomio t polUnidad = consPol 0 1 polCero -- Propiedad: El polinomio unidad es el elemento neutro del producto. prop_polUnidad p = multPol p polUnidad == p -- Comprobación: -- *Main> quickCheck prop_polUnidad -- OK, passed 100 tests. -- --------------------------------------------------------------------- -- Valor de un polinomio en un punto -- -- --------------------------------------------------------------------- -- (valor p c) es el valor del polinomio x 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 => 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 => a -> Polinomio a -> Bool esRaiz c p = valor p c == 0 -- --------------------------------------------------------------------- -- Derivación de polinomios -- -- --------------------------------------------------------------------- -- (derivaPol p) es la derivada del polinomio p. Por ejemplo, -- ejPol2 == x^5 + 5*x^2 + 4*x -- derivaPol ejPol2 == 5*x^4 + 10*x + 4 derivaPol :: Polinomio Int -> Polinomio Int derivaPol p | n == 0 = polCero | otherwise = consPol (n-1) (n*b) (derivaPol r) where n = grado p b = coefLider p r = restoPol p -- Propiedad: La derivada de la suma es la suma de las derivadas. prop_derivaPol p q = derivaPol (sumaPol p q) == sumaPol (derivaPol p) (derivaPol q) -- Comprobación -- *Main> quickCheck prop_derivaPol -- OK, passed 100 tests. -- --------------------------------------------------------------------- -- Resta de polinomio -- -- --------------------------------------------------------------------- -- (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) => Polinomio a -> Polinomio a -> Polinomio a restaPol p q = sumaPol p (multPorTerm (creaTermino 0 (-1)) q) |
PolRepDispersa.hs: Implementación de polinomios mediante listas dispersas.
|
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 |
module PolRepDispersa ( Polinomio, polCero, esPolCero, consPol, grado, coefLider, restoPol, ) where -- --------------------------------------------------------------------- -- Importaciones -- -- --------------------------------------------------------------------- import Data.Char import Data.List import Test.QuickCheck -- --------------------------------------------------------------------- -- TAD de los polinomios mediante listas dispersas -- -- --------------------------------------------------------------------- -- Representamos un polinomio por la lista de sus coeficientes ordenados -- en orden decreciente según el grado. Por ejemplo, el polinomio -- 6x^4 -5x^2 + 4x -7 se representa por [6,0,-2,4,-7]. data Polinomio a = Pol [a] deriving Eq -- --------------------------------------------------------------------- -- Implementación de la especificación -- -- --------------------------------------------------------------------- -- 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 (-1) ejPol2 == 5*x^2 + 4*x -- consPol 5 7 ejPol2 == 8*x^5 + 5*x^2 + 4*x consPol :: (Num 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 => Polinomio t -> Polinomio t restoPol (Pol []) = polCero restoPol (Pol [_]) = polCero restoPol (Pol (_:b:as)) | b == 0 = Pol (dropWhile (==0) as) | otherwise = Pol (b:as) -- --------------------------------------------------------------------- -- Propiedades -- -- --------------------------------------------------------------------- -- Propiedad de constructores y destructores de polinomios prop_polinomios :: Polinomio Int -> Bool prop_polinomios p = consPol (grado p) (coefLider p) (restoPol p) == p -- Comprobación -- > quickCheck prop_polinomios -- +++ OK, passed 100 tests. -- --------------------------------------------------------------------- -- Escritura de los polinomios -- -- --------------------------------------------------------------------- instance Num 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 -- --------------------------------------------------------------------- -- Generador de polinomios -- -- --------------------------------------------------------------------- -- Generador de polinomios -- > sample (arbitrary :: Gen (Polinomio Int)) -- 0 -- 0 -- 0 -- 0 -- -5*x^2 -- 10*x -- 11*x^16 + x^15 + -15*x^13 + 8*x^10 + -17*x^9 + 15*x^8 + -3*x^4 -- -5*x^23 + -2*x^15 -- 35*x^39 -- 0 -- -231*x^69 + 200*x^43 genPol :: (Arbitrary a, Num a) => Int -> Gen (Polinomio a) genPol 0 = return polCero genPol n = oneof [return polCero, do n <- arbitrary :: Gen Int a <- arbitrary p <- genPol (div n 2) return (consPol (mod (abs n) 100) a p)] instance (Arbitrary a, Num a) => Arbitrary (Polinomio a) where arbitrary = sized genPol |
PolRepDensa.hs: Implementación de polinomios mediante listas densas.
|
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 |
module PolRepDensa ( Polinomio, polCero, esPolCero, consPol, grado, coefLider, restoPol, ) where -- --------------------------------------------------------------------- -- Importaciones -- -- --------------------------------------------------------------------- import Data.Char import Data.List import Test.QuickCheck -- --------------------------------------------------------------------- -- TAD de los polinomios mediante listas densas. -- -- --------------------------------------------------------------------- -- Representamos 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 -- --------------------------------------------------------------------- -- Implementación de la especificación -- -- --------------------------------------------------------------------- -- 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 (-1) ejPol2 == 5*x^2 + 4*x -- consPol 5 7 ejPol2 == 8*x^5 + 5*x^2 + 4*x consPol :: (Num 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 -- --------------------------------------------------------------------- -- Propiedades -- -- --------------------------------------------------------------------- -- Propiedad de constructores y destructores de polinomios prop_polinomios :: Polinomio Int -> Bool prop_polinomios p = consPol (grado p) (coefLider p) (restoPol p) == p -- Comprobación -- > quickCheck prop_polinomios -- +++ OK, passed 100 tests. -- --------------------------------------------------------------------- -- Escritura de los polinomios -- -- --------------------------------------------------------------------- instance Num 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 -- --------------------------------------------------------------------- -- Generador de polinomios -- -- --------------------------------------------------------------------- -- Generador de polinomios -- > sample (arbitrary :: Gen (Polinomio Int)) -- 0 -- 0 -- 0 -- 0 -- -5*x^2 -- 10*x -- 11*x^16 + x^15 + -15*x^13 + 8*x^10 + -17*x^9 + 15*x^8 + -3*x^4 -- -5*x^23 + -2*x^15 -- 35*x^39 -- 0 -- -231*x^69 + 200*x^43 genPol :: (Arbitrary a, Num a) => Int -> Gen (Polinomio a) genPol 0 = return polCero genPol n = oneof [return polCero, do n <- arbitrary :: Gen Int a <- arbitrary p <- genPol (div n 2) return (consPol (abs n) a p)] instance (Arbitrary a, Num a) => Arbitrary (Polinomio a) where arbitrary = sized genPol |