{"id":668,"date":"2010-09-26T14:35:51","date_gmt":"2010-09-26T14:35:51","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=668"},"modified":"2011-06-25T05:49:32","modified_gmt":"2011-06-25T05:49:32","slug":"el-tipo-abstracto-de-datos-de-los-polinomios-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/el-tipo-abstracto-de-datos-de-los-polinomios-en-haskell\/","title":{"rendered":"El tipo abstracto de datos de los polinomios en Haskell"},"content":{"rendered":"<p>\nComo coment\u00e9 en la entrada anterior, estoy elaborando los apuntes de los temas del curso <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m\/\">Inform\u00e1tica del Grado en Matem\u00e1ticas (2010-11)<\/a> no incluidos a\u00fan en el libro     <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m\/temas\/2010-11-IM-temas-PF.pdf\">Temas de programaci\u00f3n funcional (2010-11)<\/a>.<\/p>\n<p>\nUno de los temas en los que he estado trabajando \u00faltimamente es en el de los tipos abstractos de datos (TAD). Adem\u00e1s de los habituales (pilas, colas, colas de prioridad, conjuntos, tablas, \u00e1rboles binarios de b\u00fasqueda, mont\u00edculos y \u00e1rboles AVL), un TAD especialmente adecuado para los estudiantes de matem\u00e1ticas es el de polinomios. A continuaci\u00f3n muestro la implementaci\u00f3n que estoy dise\u00f1ando en Haskell para incluirla en el tema. <\/p>\n<p>\nDel c\u00f3digo deseo resaltar las siguientes caracter\u00edsticas:<\/p>\n<ul>\n<li>Independizaci\u00f3n de los resultados de las implementaciones mediante las funciones de escritura.\n<li>Comprobaci\u00f3n de las implementaciones con QuickCheck mediante las funciones generadoras de polinomios.\n<\/ul>\n<p>\nA continuaci\u00f3n muestro los ficheros con los c\u00f3digos desarrollados.<br \/>\n<!--more--><\/p>\n<h3><i>PolRepTDA.hs<\/i>: Implementaci\u00f3n de los polinomios mediante tipos de datos algebraicos<\/h3>\n<pre lang=\"haskell\">\r\nmodule PolRepTDA\r\n  ( Polinomio,\r\n    polCero,\r\n    esPolCero,\r\n    consPol,\r\n    grado,\r\n    coefLider,\r\n    restoPol\r\n  ) where\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Importaciones                                                      --\r\n-- ---------------------------------------------------------------------\r\n\r\nimport Data.Char\r\nimport Data.List\r\nimport Test.QuickCheck\r\n\r\n-- ---------------------------------------------------------------------\r\n-- TAD de los polinomios mediante un tipo de dato algebraico.         --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- Representamos un polinomio mediante los constructores ConsPol y\r\n-- PolCero. Por ejemplo, el polinomio \r\n--    6x^4 -5x^2 + 4x -7 \r\n-- se representa por \r\n--    ConsPol 4 6 (ConsPol 2 (-5) (ConsPol 1 4 (ConsPol 0 (-7) PolCero)))\r\n\r\ndata Polinomio a = PolCero \r\n                 | ConsPol Int a (Polinomio a)\r\n                 deriving Eq\r\n             \r\n-- ---------------------------------------------------------------------\r\n-- Implementaci\u00f3n de la especificaci\u00f3n                                --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- polCero es el polinomio cero. Por ejemplo,\r\n--    > polCero\r\n--    0\r\npolCero :: Polinomio a\r\npolCero = PolCero\r\n\r\n-- (esPolCero p) se verifica si p es el polinomio cero. Por ejemplo,\r\n--    esPolCero polCero  ==  True\r\n--    esPolCero ejPol1   ==  False\r\nesPolCero :: Polinomio a -> Bool\r\nesPolCero PolCero = True\r\nesPolCero _       = False\r\n\r\n-- (consPol n b p) es el polinomio bx^n+p. Por ejemplo,\r\n--    ejPol2                 ==  x^5 + 5*x^2 + 4*x\r\n--    consPol 3 0 ejPol2     ==  x^5 + 5*x^2 + 4*x\r\n--    consPol 3 2 polCero    ==  2*x^3\r\n--    consPol 6 7 ejPol2     ==  7*x^6 + x^5 + 5*x^2 + 4*x\r\n--    consPol 4 7 ejPol2     ==  x^5 + 7*x^4 + 5*x^2 + 4*x\r\n--    consPol 5 (-1) ejPol2  ==  5*x^2 + 4*x\r\n--    consPol 5 7 ejPol2     ==  8*x^5 + 5*x^2 + 4*x\r\nconsPol :: Num a => Int -> a -> Polinomio a -> Polinomio a  \r\nconsPol _ 0 p = p\r\nconsPol n b PolCero = ConsPol n b PolCero\r\nconsPol n b (ConsPol m c p) \r\n    | n > m      = ConsPol n b (ConsPol m c p)\r\n    | n < m      = ConsPol m c (consPol n b p)\r\n    | b+c == 0   = p\r\n    | otherwise  = ConsPol n (b+c) p\r\n\r\n-- (grado p) es el grado del polinomio p. Por ejemplo,\r\n--    ejPol3        ==  6*x^4 + 2*x\r\n--    grado ejPol3  ==  4\r\ngrado:: Polinomio a -> Int\r\ngrado PolCero         = 0\r\ngrado (ConsPol n _ _) = n\r\n\r\n-- (coefLider p) es el coeficiente l\u00edder del polinomio p. Por ejemplo,\r\n--    ejPol3            ==  6*x^4 + 2*x\r\n--    coefLider ejPol3  ==  6\r\ncoefLider:: Num t => Polinomio t -> t\r\ncoefLider PolCero         = 0\r\ncoefLider (ConsPol _ b _) = b\r\n\r\n-- (restoPol p) es el resto del polinomio p. Por ejemplo,\r\n--    ejPol3           ==  6*x^4 + 2*x\r\n--    restoPol ejPol3  ==  2*x\r\n--    ejPol2           ==  x^5 + 5*x^2 + 4*x\r\n--    restoPol ejPol2  ==  5*x^2 + 4*x\r\nrestoPol :: Polinomio t -> Polinomio t\r\nrestoPol PolCero         = PolCero\r\nrestoPol (ConsPol _ _ p) = p\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Propiedades                                                        --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- Propiedad de constructores y destructores de polinomios\r\nprop_polinomios :: Polinomio Int -> Bool\r\nprop_polinomios p =\r\n    consPol (grado p) (coefLider p) (restoPol p) == p\r\n\r\n-- Comprobaci\u00f3n\r\n--    > quickCheck prop_polinomios\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Escritura de los polinomios                                        --\r\n-- ---------------------------------------------------------------------\r\n\r\ninstance Num a => Show (Polinomio a) where\r\n    show PolCero               = \"0\"\r\n    show (ConsPol 0 b PolCero) = show b\r\n    show (ConsPol 0 b p)       = concat [show b, \" + \", show p] \r\n    show (ConsPol 1 b PolCero) = concat [show b, \"*x\"]\r\n    show (ConsPol 1 b p)       = concat [show b, \"*x + \", show p] \r\n    show (ConsPol n 1 PolCero) = concat [\"x^\", show n] \r\n    show (ConsPol n b PolCero) = concat [show b, \"*x^\", show n] \r\n    show (ConsPol n 1 p)       = concat [\"x^\", show n, \" + \", show p] \r\n    show (ConsPol n b p)       = concat [show b, \"*x^\", show n, \" + \", show p] \r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejemplos de polinomios                                             --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- Ejemplos de polinomios con coeficientes enteros:\r\nejPol1, ejPol2, ejPol3:: Polinomio Int\r\nejPol1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))\r\nejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))\r\nejPol3 = consPol 4 6 (consPol 1 2 polCero)\r\n\r\n-- Comprobaci\u00f3n de escritura:\r\n--    > ejPol1\r\n--    3*x^4 + -5*x^2 + 3\r\n--    > ejPol2\r\n--    x^5 + 5*x^2 + 4*x\r\n--    > ejPol3\r\n--    6*x^4 + 2*x\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Generador de polinomios                                            --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- Generador de polinomios\r\n--    > sample (arbitrary :: Gen (Polinomio Int))\r\n--    0\r\n--    0\r\n--    0\r\n--    0\r\n--    -5*x^2\r\n--    10*x\r\n--    11*x^16 + x^15 + -15*x^13 + 8*x^10 + -17*x^9 + 15*x^8 + -3*x^4\r\n--    -5*x^23 + -2*x^15\r\n--    35*x^39\r\n--    0\r\n--    -231*x^69 + 200*x^43\r\ngenPol :: (Arbitrary a, Num a) => Int -> Gen (Polinomio a)\r\ngenPol 0 = return polCero\r\ngenPol n = oneof [return polCero,\r\n                  do n <- arbitrary :: Gen Int   \r\n                     a <- arbitrary\r\n                     p <- genPol (div n 2)\r\n                     return (consPol (abs n) a p)]\r\n\r\ninstance (Arbitrary a, Num a) => Arbitrary (Polinomio a) where\r\n    arbitrary = sized genPol\r\n<\/pre>\n<h3><i>EjemplosPol.hs<\/i>: Ejemplos de polinomios<\/h3>\n<pre lang=\"haskell\">\r\nmodule EjemplosPol where\r\n\r\n-- Elegir una de las representaciones\r\nimport PolRepTDA\r\n-- import PolRepDispersa\r\n-- import PolRepDensa\r\n\r\n-- Ejemplos de polinomios con coeficientes enteros:\r\nejPol1, ejPol2, ejPol3, ejTerm:: Polinomio Int\r\nejPol1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))\r\nejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))\r\nejPol3 = consPol 4 6 (consPol 1 2 polCero)\r\nejTerm = consPol 1 4 polCero\r\n<\/pre>\n<h3><i>PolOperaciones.hs<\/i>: Operaciones con polinomios.<\/h3>\n<pre lang=\"haskell\">\r\nmodule PolOperaciones where\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Importaci\u00f3n de librer\u00edas                                           --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- Nota: Para usarlo, \r\n-- 1. Elegir una de las representaciones (PolRep*).\r\n-- 2. Elegir la misma representaci\u00f3n en EjemplosPol.hs\r\n\r\nimport PolRepTDA\r\n-- import PolRepDispersa\r\n-- import PolRepDensa\r\nimport EjemplosPol\r\nimport Test.QuickCheck\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Funciones sobre t\u00e9rminos                                           --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- (creaTermino n a) es el t\u00e9rmino a*x^n. Por ejemplo, \r\n--    creaTermino 2 5  ==  5*x^2\r\ncreaTermino:: Num t => Int -> t -> Polinomio t\r\ncreaTermino n a = consPol n a polCero\r\n\r\n-- (termLider p) es el t\u00e9rmino l\u00edder del polinomio p.\r\n--    ejPol2            ==  x^5 + 5*x^2 + 4*x\r\n--    termLider ejPol2  ==  x^5\r\ntermLider:: Num t => Polinomio t -> Polinomio t\r\ntermLider p = creaTermino (grado p) (coefLider p)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Suma de polinomios                                                 --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- (sumaPol p q) es la suma de los polinomios p y q. Por ejemplo, \r\n--    ejPol1                 ==  3*x^4 + -5*x^2 + 3\r\n--    ejPol2                 ==  x^5 + 5*x^2 + 4*x\r\n--    sumaPol ejPol1 ejPol2  ==  x^5 + 3*x^4 + 4*x + 3\r\nsumaPol:: Num a => Polinomio a -> Polinomio a -> Polinomio a\r\nsumaPol p q \r\n    | esPolCero p  = q\r\n    | esPolCero q  = p\r\n    | n1 > n2      = consPol n1 a1 (sumaPol r1 q)\r\n    | n1 < n2      = consPol n2 a2 (sumaPol p r2)\r\n    | a1+a2 \/= 0   = consPol n1 (a1+a2) (sumaPol r1 r2)\r\n    | otherwise    = sumaPol r1 r2\r\n    where n1 = grado p\r\n          a1 = coefLider p\r\n          r1 = restoPol p\r\n          n2 = grado q\r\n          a2 = coefLider q\r\n          r2 = restoPol q\r\n\r\n-- Elemento neutro de la suma:\r\nprop_neutroSumaPol p = \r\n    sumaPol polCero p == p\r\n\r\n-- Comprobaci\u00f3n con QuickCheck.\r\n--    Main> quickCheck prop_neutroSumaPol\r\n--    OK, passed 100 tests.\r\n\r\n-- Propiedad conmutativa:\r\nprop_conmutativaSuma p q = \r\n    sumaPol p q == sumaPol q p\r\n\r\n-- Comprobaci\u00f3n:\r\n--    *Main> quickCheck prop_conmutativaSuma\r\n--    OK, passed 100 tests.\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Producto de polinomios                                             --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- (multPorTerm t p) es el producto del t\u00e9rmino t por el polinomio\r\n-- p. Por ejemplo,\r\n--    ejTerm                     ==  4*x\r\n--    ejPol2                     ==  x^5 + 5*x^2 + 4*x\r\n--    multPorTerm ejTerm ejPol2  ==  4*x^6 + 20*x^3 + 16*x^2\r\nmultPorTerm :: Num t => Polinomio t -> Polinomio t -> Polinomio t\r\nmultPorTerm term pol \r\n    | esPolCero pol = polCero\r\n    | otherwise     = consPol (n+m) (a*b) (multPorTerm term r)\r\n    where n = grado term\r\n          a = coefLider term\r\n          m = grado pol\r\n          b = coefLider pol\r\n          r = restoPol pol    \r\n\r\n-- (multPol p q) es el producto de los polinomios p y q. Por\r\n-- ejemplo,\r\n--    *Main> ejPol1\r\n--    3*x^4 + -5*x^2 + 3\r\n--    *Main> ejPol2\r\n--    x^5 + 5*x^2 + 4*x\r\n--    *Main> multPol ejPol1 ejPol2\r\n--    3*x^9 + -5*x^7 + 15*x^6 + 15*x^5 + -25*x^4 + -20*x^3 + 15*x^2 + 12*x\r\nmultPol :: Num a => Polinomio a -> Polinomio a -> Polinomio a\r\nmultPol p q\r\n    | esPolCero p = polCero\r\n    | otherwise    = sumaPol (multPorTerm (termLider p) q)\r\n                             (multPol (restoPol p) q)\r\n\r\n-- Propiedad conmutativa del producto:\r\nprop_conmutativaProducto p q = \r\n    multPol p q == multPol q p\r\n\r\n-- La comprobaci\u00f3n es\r\n--    *Main> quickCheck prop_conmutativaProducto\r\n--    OK, passed 100 tests.\r\n\r\n-- Proopiedad distributiva del producto respecto de la suma:\r\nprop_distributivaProductoSuma p q r =\r\n    multPol p (sumaPol q r) == sumaPol (multPol p q) (multPol p r)\r\n\r\n-- Comprobaci\u00f3n:\r\n--    *Main> quickCheck prop_distributivaProductoSuma\r\n--    OK, passed 100 tests.\r\n\r\n-- polUnidad es el polinomio unidad. Por ejemplo, \r\n--    *Main> polUnidad\r\n--    1\r\npolUnidad:: Num t => Polinomio t\r\npolUnidad = consPol 0 1 polCero\r\n\r\n-- Propiedad: El polinomio unidad es el elemento neutro del producto.\r\nprop_polUnidad p = \r\n    multPol p polUnidad == p\r\n\r\n-- Comprobaci\u00f3n:\r\n--    *Main> quickCheck prop_polUnidad\r\n--    OK, passed 100 tests.\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Valor de un polinomio en un punto                                  --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- (valor p c) es el valor del polinomio x al sustituir su variable por\r\n-- c. Por ejemplo, \r\n--    ejPol1             ==  3*x^4 + -5*x^2 + 3\r\n--    valor ejPol1 0     ==  3\r\n--    valor ejPol1 1     ==  1\r\n--    valor ejPol1 (-2)  ==  31\r\nvalor:: Num a => Polinomio a -> a -> a\r\nvalor p c \r\n    | esPolCero p = 0\r\n    | otherwise   =  b*c^n + valor r c\r\n    where n = grado p\r\n          b = coefLider p\r\n          r = restoPol p\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Verificaci\u00f3n de raices de polinomios                               --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- (esRaiz c p) se verifica si c es una raiz del polinomio p. por\r\n-- ejemplo, \r\n--    ejPol3           ==  6*x^4 + 2*x\r\n--    esRaiz 1 ejPol3  ==  False\r\n--    esRaiz 0 ejPol3  ==  True\r\nesRaiz:: Num a => a -> Polinomio a -> Bool\r\nesRaiz c p = valor p c == 0\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Derivaci\u00f3n de polinomios                                           --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- (derivaPol p) es la derivada del polinomio p. Por ejemplo, \r\n--    ejPol2            ==  x^5 + 5*x^2 + 4*x\r\n--    derivaPol ejPol2  ==  5*x^4 + 10*x + 4\r\nderivaPol :: Polinomio Int -> Polinomio Int\r\nderivaPol p \r\n    | n == 0     = polCero\r\n    | otherwise  = consPol (n-1) (n*b) (derivaPol r)\r\n    where n = grado p\r\n          b = coefLider p\r\n          r = restoPol p\r\n\r\n-- Propiedad: La derivada de la suma es la suma de las derivadas.\r\nprop_derivaPol p q =\r\n    derivaPol (sumaPol p q) == sumaPol (derivaPol p) (derivaPol q)\r\n\r\n-- Comprobaci\u00f3n\r\n--    *Main> quickCheck prop_derivaPol\r\n--    OK, passed 100 tests. \r\n\r\n-- ---------------------------------------------------------------------\r\n-- Resta de polinomio                                                 --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- (resta p q) es la el polinomio obtenido rest\u00e1ndole a p el q. Por\r\n-- ejemplo, \r\n--    ejPol1                  ==  3*x^4 + -5*x^2 + 3\r\n--    ejPol2                  ==  x^5 + 5*x^2 + 4*x\r\n--    restaPol ejPol1 ejPol2  ==  -1*x^5 + 3*x^4 + -10*x^2 + -4*x + 3\r\nrestaPol :: (Num a) => Polinomio a -> Polinomio a -> Polinomio a\r\nrestaPol p q  = \r\n    sumaPol p (multPorTerm (creaTermino 0 (-1)) q)\r\n<\/pre>\n<h3><i>PolRepDispersa.hs<\/i>: Implementaci\u00f3n de polinomios mediante listas dispersas.<\/h3>\n<pre lang=\"haskell\">\r\nmodule PolRepDispersa\r\n  ( Polinomio,\r\n    polCero,\r\n    esPolCero,\r\n    consPol,\r\n    grado,\r\n    coefLider,\r\n    restoPol,\r\n  ) where\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Importaciones                                                      --\r\n-- ---------------------------------------------------------------------\r\n\r\nimport Data.Char\r\nimport Data.List\r\nimport Test.QuickCheck\r\n\r\n-- ---------------------------------------------------------------------\r\n-- TAD de los polinomios mediante listas dispersas                    --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- Representamos un polinomio por la lista de sus coeficientes ordenados\r\n-- en orden decreciente seg\u00fan el grado. Por ejemplo, el polinomio \r\n-- 6x^4 -5x^2 + 4x -7 se representa por [6,0,-2,4,-7]. \r\n\r\ndata Polinomio a = Pol [a] \r\n                   deriving Eq\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Implementaci\u00f3n de la especificaci\u00f3n                                --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- polCero es el polinomio cero. Por ejemplo,\r\n--    > polCero\r\n--    0\r\npolCero :: Polinomio a\r\npolCero = Pol []\r\n\r\n-- (esPolCero p) se verifica si p es el polinomio cero. Por ejemplo,\r\n--    esPolCero polCero  ==  True\r\n--    esPolCero ejPol1   ==  False\r\nesPolCero :: Polinomio a -> Bool\r\nesPolCero (Pol []) = True\r\nesPolCero _        = False\r\n\r\n-- (consPol n b p) es el polinomio bx^n+p. Por ejemplo,\r\n--    ejPol2               ==  x^5 + 5*x^2 + 4*x\r\n--    consPol 3 0 ejPol2   ==  x^5 + 5*x^2 + 4*x\r\n--    consPol 3 2 polCero  ==  2*x^3\r\n--    consPol 6 7 ejPol2   ==  7*x^6 + x^5 + 5*x^2 + 4*x\r\n--    consPol 4 7 ejPol2   ==  x^5 + 7*x^4 + 5*x^2 + 4*x\r\n--    consPol 5 (-1) ejPol2  ==  5*x^2 + 4*x\r\n--    consPol 5 7 ejPol2   ==  8*x^5 + 5*x^2 + 4*x\r\nconsPol :: (Num a) => Int -> a -> Polinomio a -> Polinomio a\r\nconsPol _ 0 p = p\r\nconsPol n b p@(Pol xs) \r\n    | esPolCero p = Pol (b:replicate n 0)\r\n    | n > m       = Pol (b:(replicate (n-m-1) 0)++xs)\r\n    | n < m       = consPol m c (consPol n b (restoPol p))\r\n    | b+c == 0    = Pol (dropWhile (==0) (tail xs))\r\n    | otherwise   = Pol ((b+c):tail xs)\r\n    where \r\n      c = coefLider p\r\n      m = grado p\r\n   \r\n-- (grado p) es el grado del polinomio p. Por ejemplo,\r\n--    ejPol3        ==  6*x^4 + 2*x\r\n--    grado ejPol3  ==  4\r\ngrado:: Polinomio a -> Int\r\ngrado (Pol []) = 0\r\ngrado (Pol xs) = length xs - 1\r\n\r\n-- (coefLider p) es el coeficiente l\u00edder del polinomio p. Por ejemplo,\r\n--    ejPol3            ==  6*x^4 + 2*x\r\n--    coefLider ejPol3  ==  6\r\ncoefLider:: Num t => Polinomio t -> t\r\ncoefLider (Pol [])    = 0\r\ncoefLider (Pol (a:_)) = a \r\n\r\n-- (restoPol p) es el resto del polinomio p. Por ejemplo,\r\n--    ejPol3           ==  6*x^4 + 2*x\r\n--    restoPol ejPol3  ==  2*x\r\n--    ejPol2           ==  x^5 + 5*x^2 + 4*x\r\n--    restoPol ejPol2  ==  5*x^2 + 4*x\r\nrestoPol :: Num t => Polinomio t -> Polinomio t\r\nrestoPol (Pol [])     = polCero\r\nrestoPol (Pol [_])    = polCero\r\nrestoPol (Pol (_:b:as)) \r\n    | b == 0    = Pol (dropWhile (==0) as)\r\n    | otherwise = Pol (b:as)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Propiedades                                                        --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- Propiedad de constructores y destructores de polinomios\r\nprop_polinomios :: Polinomio Int -> Bool\r\nprop_polinomios p =\r\n    consPol (grado p) (coefLider p) (restoPol p) == p\r\n\r\n-- Comprobaci\u00f3n\r\n--    > quickCheck prop_polinomios\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Escritura de los polinomios                                        --\r\n-- ---------------------------------------------------------------------\r\n\r\ninstance Num t => Show (Polinomio t) where\r\n  show pol \r\n      | esPolCero pol         = \"0\"\r\n      | n == 0 && esPolCero p = show a \r\n      | n == 0                = concat [show a, \" + \", show p] \r\n      | n == 1 && esPolCero p = concat [show a, \"*x\"]\r\n      | n == 1                = concat [show a, \"*x + \", show p] \r\n      | a == 1 && esPolCero p = concat [\"x^\", show n] \r\n      | esPolCero p           = concat [show a, \"*x^\", show n] \r\n      | a == 1                = concat [\"x^\", show n, \" + \", show p] \r\n      | otherwise             = concat [show a, \"*x^\", show n, \" + \", show p] \r\n     where n = grado pol\r\n           a = coefLider pol\r\n           p = restoPol pol\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejemplos de polinomios                                             --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- Ejemplos de polinomios con coeficientes enteros:\r\nejPol1, ejPol2, ejPol3:: Polinomio Int\r\nejPol1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))\r\nejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))\r\nejPol3 = consPol 4 6 (consPol 1 2 polCero)\r\n\r\n-- Comprobaci\u00f3n de escritura:\r\n--    > ejPol1\r\n--    3*x^4 + -5*x^2 + 3\r\n--    > ejPol2\r\n--    x^5 + 5*x^2 + 4*x\r\n--    > ejPol3\r\n--    6*x^4 + 2*x\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Generador de polinomios                                            --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- Generador de polinomios\r\n--    > sample (arbitrary :: Gen (Polinomio Int))\r\n--    0\r\n--    0\r\n--    0\r\n--    0\r\n--    -5*x^2\r\n--    10*x\r\n--    11*x^16 + x^15 + -15*x^13 + 8*x^10 + -17*x^9 + 15*x^8 + -3*x^4\r\n--    -5*x^23 + -2*x^15\r\n--    35*x^39\r\n--    0\r\n--    -231*x^69 + 200*x^43\r\ngenPol :: (Arbitrary a, Num a) => Int -> Gen (Polinomio a)\r\ngenPol 0 = return polCero\r\ngenPol n = oneof [return polCero,\r\n                  do n <- arbitrary :: Gen Int   \r\n                     a <- arbitrary\r\n                     p <- genPol (div n 2)\r\n                     return (consPol (mod (abs n) 100) a p)]\r\n\r\ninstance (Arbitrary a, Num a) => Arbitrary (Polinomio a) where\r\n    arbitrary = sized genPol\r\n<\/pre>\n<h3><i>PolRepDensa.hs<\/i>: Implementaci\u00f3n de polinomios mediante listas densas.<\/h3>\n<pre lang=\"haskell\">\r\nmodule PolRepDensa\r\n  ( Polinomio,\r\n    polCero,\r\n    esPolCero,\r\n    consPol,\r\n    grado,\r\n    coefLider,\r\n    restoPol,\r\n  ) where\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Importaciones                                                      --\r\n-- ---------------------------------------------------------------------\r\n\r\nimport Data.Char\r\nimport Data.List\r\nimport Test.QuickCheck\r\n\r\n-- ---------------------------------------------------------------------\r\n-- TAD de los polinomios mediante listas densas.                      --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- Representamos un polinomio mediante una lista de pares (grado,coef),\r\n-- ordenados en orden decreciente seg\u00fan el grado. Por ejemplo, el\r\n-- polinomio \r\n--    6x^4 -5x^2 + 4x -7 \r\n-- se representa por\r\n--    [(4,6),(2,-5),(1,4),(0,-7)]. \r\n\r\ndata Polinomio a = Pol [(Int,a)] \r\n                   deriving Eq\r\n    \r\n-- ---------------------------------------------------------------------\r\n-- Implementaci\u00f3n de la especificaci\u00f3n                                --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- polCero es el polinomio cero. Por ejemplo,\r\n--    > polCero\r\n--    0\r\npolCero :: Num a => Polinomio a\r\npolCero = Pol []\r\n\r\n-- (esPolCero p) se verifica si p es el polinomio cero. Por ejemplo,\r\n--    esPolCero polCero  ==  True\r\n--    esPolCero ejPol1   ==  False\r\nesPolCero :: Num a => Polinomio a -> Bool\r\nesPolCero (Pol []) = True\r\nesPolCero _        = False\r\n\r\n-- (consPol n b p) es el polinomio bx^n+p. Por ejemplo,\r\n--    ejPol2               ==  x^5 + 5*x^2 + 4*x\r\n--    consPol 3 0 ejPol2   ==  x^5 + 5*x^2 + 4*x\r\n--    consPol 3 2 polCero  ==  2*x^3\r\n--    consPol 6 7 ejPol2   ==  7*x^6 + x^5 + 5*x^2 + 4*x\r\n--    consPol 4 7 ejPol2   ==  x^5 + 7*x^4 + 5*x^2 + 4*x\r\n--    consPol 5 (-1) ejPol2  ==  5*x^2 + 4*x\r\n--    consPol 5 7 ejPol2   ==  8*x^5 + 5*x^2 + 4*x\r\nconsPol :: (Num a) => Int -> a -> Polinomio a -> Polinomio a\r\nconsPol _ 0 p = p\r\nconsPol n b p@(Pol xs) \r\n    | esPolCero p = Pol [(n,b)]\r\n    | n > m       = Pol ((n,b):xs)\r\n    | n < m       = consPol m c (consPol n b (Pol (tail xs)))\r\n    | b+c == 0    = Pol (tail xs)\r\n    | otherwise   = Pol ((n,b+c):(tail xs))\r\n    where \r\n      c = coefLider p\r\n      m = grado p\r\n\r\n-- (grado p) es el grado del polinomio p. Por ejemplo,\r\n--    ejPol3        ==  6*x^4 + 2*x\r\n--    grado ejPol3  ==  4\r\ngrado:: Polinomio a -> Int\r\ngrado (Pol [])        = 0\r\ngrado (Pol ((n,_):_)) = n\r\n\r\n-- (coefLider p) es el coeficiente l\u00edder del polinomio p. Por ejemplo,\r\n--    ejPol3            ==  6*x^4 + 2*x\r\n--    coefLider ejPol3  ==  6\r\ncoefLider:: Num t => Polinomio t -> t\r\ncoefLider (Pol [])        = 0\r\ncoefLider (Pol ((_,b):_)) = b\r\n\r\n-- (restoPol p) es el resto del polinomio p. Por ejemplo,\r\n--    ejPol3           ==  6*x^4 + 2*x\r\n--    restoPol ejPol3  ==  2*x\r\n--    ejPol2           ==  x^5 + 5*x^2 + 4*x\r\n--    restoPol ejPol2  ==  5*x^2 + 4*x\r\nrestoPol :: Num t => Polinomio t -> Polinomio t\r\nrestoPol (Pol [])     = polCero\r\nrestoPol (Pol [_])    = polCero\r\nrestoPol (Pol (_:xs)) = Pol xs\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Propiedades                                                        --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- Propiedad de constructores y destructores de polinomios\r\nprop_polinomios :: Polinomio Int -> Bool\r\nprop_polinomios p =\r\n    consPol (grado p) (coefLider p) (restoPol p) == p\r\n\r\n-- Comprobaci\u00f3n\r\n--    > quickCheck prop_polinomios\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Escritura de los polinomios                                        --\r\n-- ---------------------------------------------------------------------\r\n\r\ninstance Num t => Show (Polinomio t) where\r\n  show pol \r\n      | esPolCero pol         = \"0\"\r\n      | n == 0 && esPolCero p = show a \r\n      | n == 0                = concat [show a, \" + \", show p] \r\n      | n == 1 && esPolCero p = concat [show a, \"*x\"]\r\n      | n == 1                = concat [show a, \"*x + \", show p] \r\n      | a == 1 && esPolCero p = concat [\"x^\", show n] \r\n      | esPolCero p           = concat [show a, \"*x^\", show n] \r\n      | a == 1                = concat [\"x^\", show n, \" + \", show p] \r\n      | otherwise             = concat [show a, \"*x^\", show n, \" + \", show p] \r\n     where n = grado pol\r\n           a = coefLider pol\r\n           p = restoPol pol\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejemplos de polinomios                                             --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- Ejemplos de polinomios con coeficientes enteros:\r\nejPol1, ejPol2, ejPol3:: Polinomio Int\r\nejPol1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))\r\nejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))\r\nejPol3 = consPol 4 6 (consPol 1 2 polCero)\r\n\r\n-- Comprobaci\u00f3n de escritura:\r\n--    > ejPol1\r\n--    3*x^4 + -5*x^2 + 3\r\n--    > ejPol2\r\n--    x^5 + 5*x^2 + 4*x\r\n--    > ejPol3\r\n--    6*x^4 + 2*x\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Generador de polinomios                                            --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- Generador de polinomios\r\n--    > sample (arbitrary :: Gen (Polinomio Int))\r\n--    0\r\n--    0\r\n--    0\r\n--    0\r\n--    -5*x^2\r\n--    10*x\r\n--    11*x^16 + x^15 + -15*x^13 + 8*x^10 + -17*x^9 + 15*x^8 + -3*x^4\r\n--    -5*x^23 + -2*x^15\r\n--    35*x^39\r\n--    0\r\n--    -231*x^69 + 200*x^43\r\ngenPol :: (Arbitrary a, Num a) => Int -> Gen (Polinomio a)\r\ngenPol 0 = return polCero\r\ngenPol n = oneof [return polCero,\r\n                  do n <- arbitrary :: Gen Int   \r\n                     a <- arbitrary\r\n                     p <- genPol (div n 2)\r\n                     return (consPol (abs n) a p)]\r\n\r\ninstance (Arbitrary a, Num a) => Arbitrary (Polinomio a) where\r\n    arbitrary = sized genPol\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Como coment\u00e9 en la entrada anterior, estoy elaborando los apuntes de los temas del curso Inform\u00e1tica del Grado en Matem\u00e1ticas (2010-11) no incluidos a\u00fan en el libro Temas de programaci\u00f3n funcional (2010-11). Uno de los temas en los que he estado trabajando \u00faltimamente es en el de los tipos abstractos de datos (TAD). Adem\u00e1s de&#8230;<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[5],"tags":[279,287,125,126,124],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_likes_enabled":false,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/668"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/comments?post=668"}],"version-history":[{"count":10,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/668\/revisions"}],"predecessor-version":[{"id":1426,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/668\/revisions\/1426"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=668"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=668"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=668"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}