I1M2011: El TAD de los polinomios en Haskell (1)
En la clase de hoy de Informática de 1º del Grado en Matemáticas hemos estudiado el tipo abstracto de los polinomios y su implementación en Haskell.
Comenzamos la clase analizando las posibles representaciones de los polinomios y, como consecuencia, establecer la signatura y las propiedades del TAD de los polinomios.
A continuación, estudiamos tres prosibles representaciones del TAD de los polinomios: mediante tipos algebraicos, mediantes listas dispersas y mediante listas densas.
Finalmente, estudiamos la implementación de los polinomios como tipo algebraico y dejamos las otras dos como ejercicio.
Las transparencias usadas en la clase son las páginas 1-15 del tema 21
El código del programa es el siguiente
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 |
module PolRepTDA ( 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 t => Polinomio t -> t restoPol -- Polinomio t -> Polinomio t ) where -- --------------------------------------------------------------------- -- TAD de los polinomios mediante un tipo de dato algebraico. -- -- --------------------------------------------------------------------- -- Representamos un polinomio mediante los constructores ConsPol y -- PolCero. Por ejemplo, el polinomio -- 6x^4 -5x^2 + 4x -7 -- se representa por -- ConsPol 4 6 (ConsPol 2 (-5) (ConsPol 1 4 (ConsPol 0 (-7) PolCero))) data Polinomio a = PolCero | ConsPol Int a (Polinomio a) deriving Eq -- --------------------------------------------------------------------- -- Escritura de los polinomios -- -- --------------------------------------------------------------------- instance Num a => Show (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 -- Ejemplos de polinomios con coeficientes reales: ejPol5, ejPol6, ejPol7:: Polinomio Float ejPol5 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero)) ejPol6 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero)) ejPol7 = consPol 1 2 (consPol 4 6 polCero) -- Comprobación de escritura: -- > ejPol5 -- 3.0*x^4 + -5.0*x^2 + 3.0 -- > ejPol6 -- x^5 + 5.0*x^2 + 4.0*x -- > ejPol7 -- 6.0*x^4 + 2.0*x -- --------------------------------------------------------------------- -- Implementación de la especificación -- -- --------------------------------------------------------------------- -- polCero es el polinomio cero. Por ejemplo, -- > polCero -- 0 polCero :: Polinomio a polCero = PolCero -- (esPolCero p) se verifica si p es el polinomio cero. Por ejemplo, -- esPolCero polCero == True -- esPolCero ejPol1 == False esPolCero :: Polinomio a -> Bool esPolCero PolCero = True esPolCero _ = False -- (consPol n b p) es el polinomio bx^n+p. Por ejemplo, -- ejPol2 == x^5 + 5*x^2 + 4*x -- consPol 3 0 ejPol2 == x^5 + 5*x^2 + 4*x -- consPol 3 2 polCero == 2*x^3 -- consPol 6 7 ejPol2 == 7*x^6 + x^5 + 5*x^2 + 4*x -- consPol 4 7 ejPol2 == x^5 + 7*x^4 + 5*x^2 + 4*x -- consPol 5 7 ejPol2 == 8*x^5 + 5*x^2 + 4*x consPol :: Num a => 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 |