I1M2013: El TAD de los polinomios en Haskell
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 mediantes listas dispersas.
Las transparencias usadas en la clase son las páginas 1-41 del tema 21
El código del TAD de polinomios mediante tipo algebraico 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 |
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 |
El código del TAD de polinomios mediante listas dispersas 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 |
module PolRepDispersa ( Polinomio, polCero, -- Polinomio a esPolCero, -- Num a => Polinomio a -> Bool consPol, -- (Num a) => Int -> a -> Polinomio a -> Polinomio a grado, -- Polinomio a -> Int coefLider, -- Num a => Polinomio a -> a restoPol -- Polinomio a -> Polinomio a ) where -- --------------------------------------------------------------------- -- TAD de los polinomios mediante listas dispersas -- -- --------------------------------------------------------------------- -- Representaremos un polinomio por la lista de sus coeficientes ordenados -- en orden decreciente según el grado. Por ejemplo, el polinomio -- 6x^4 -5x^2 + 4x -7 se representa por [6,0,-2,4,-7]. data Polinomio a = Pol [a] deriving Eq -- --------------------------------------------------------------------- -- Escritura de los polinomios -- -- --------------------------------------------------------------------- instance Num a => Show (Polinomio a) where show pol | esPolCero pol = "0" | n == 0 && esPolCero p = show a | n == 0 = concat [show a, " + ", show p] | n == 1 && esPolCero p = 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 :: 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 => 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) |
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 |