{"id":3191,"date":"2013-04-08T14:10:22","date_gmt":"2013-04-08T14:10:22","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=3191"},"modified":"2013-04-08T14:10:22","modified_gmt":"2013-04-08T14:10:22","slug":"i1m2012-el-tad-de-los-polinomios-en-haskell-2","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2012-el-tad-de-los-polinomios-en-haskell-2\/","title":{"rendered":"I1M2012: El TAD de los polinomios en Haskell (2)"},"content":{"rendered":"<p>En la clase de hoy de <a  href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-12\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> hemos continuado el estudio del tipo abstracto de los polinomios y su implementaci\u00f3n en Haskell que comenzamos en la <a href=\"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2012-el-tad-de-los-polinomios-en-haskell-1\/\">clase anterior<\/a>. Concretamente, hemos estudiado la implementaciones en Haskell del TAD de los polinomios mediante listas densas y las operaciones con los polinomios usando el TAD.<\/p>\n<p>Las transparencias usadas en la clase son las p\u00e1ginas 24-55 del <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-12\/temas\/tema-21t.pdf\">tema 21<\/a><br \/>\n<!--more--><br \/>\n<div class=\"jetpack-video-wrapper\"><iframe src='https:\/\/www.slideshare.net\/slideshow\/embed_code\/12063179' width='1290' height='1057' sandbox=\"allow-popups allow-scripts allow-same-origin allow-presentation\" allowfullscreen webkitallowfullscreen mozallowfullscreen><\/iframe><\/div><\/p>\n<p>El c\u00f3digo de la representaci\u00f3n densa del TAD de los polinomios es<\/p>\n<pre lang=\"haskell\">\r\nmodule PolRepDensa\r\n  ( Polinomio,\r\n    polCero,   -- Polinomio a                                         \r\n    esPolCero, -- Num a =>  Polinomio a -> Bool                       \r\n    consPol,   -- Num a => Int -> a -> Polinomio a -> Polinomio a   \r\n    grado,     -- Polinomio a -> Int                                  \r\n    coefLider, -- Num a => Polinomio a -> a                           \r\n    restoPol   -- Polinomio a -> Polinomio a                          \r\n  ) where\r\n\r\n-- ---------------------------------------------------------------------\r\n-- TAD de los polinomios mediante listas densas.                      --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- Representaremos 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-- Escritura de los polinomios                                        --\r\n-- ---------------------------------------------------------------------\r\n\r\ninstance (Num t, Show t, Eq 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-- Implementaci\u00f3n de la especificaci\u00f3n                                --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- polCero es el polinomio cero. Por ejemplo,\r\n--    ghci> 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 7 ejPol2   ==  8*x^5 + 5*x^2 + 4*x\r\nconsPol :: (Num a, Eq 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<\/pre>\n<p>El c\u00f3digo de las operaciones con el TAD de los polinomios es<\/p>\n<pre lang=\"haskell\">\r\nmodule PolOperaciones (module Pol, module PolOperaciones) where\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Importaci\u00f3n de librer\u00edas                                           --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- Nota: Hay que elegir una implementaci\u00f3n del TAD de los polinomios.\r\nimport PolRepTDA as Pol\r\n-- import PolRepDispersa as Pol\r\n-- import PolRepDensa as Pol\r\n\r\nimport Test.QuickCheck\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejemplos                                                           --\r\n-- ---------------------------------------------------------------------\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\r\n-- ---------------------------------------------------------------------\r\n-- Generador de polinomios                                            --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- (genPol n) es un generador de polinomios. Por ejemplo,\r\n--    ghci> sample (genPol 1)\r\n--    7*x^9 + 9*x^8 + 10*x^7 + -14*x^5 + -15*x^2 + -10\r\n--    -4*x^8 + 2*x\r\n--    -8*x^9 + 4*x^8 + 2*x^6 + 4*x^5 + -6*x^4 + 5*x^2 + -8*x\r\n--    -9*x^9 + x^5 + -7\r\n--    8*x^10 + -9*x^7 + 7*x^6 + 9*x^5 + 10*x^3 + -1*x^2\r\n--    7*x^10 + 5*x^9 + -5\r\n--    -8*x^10 + -7\r\n--    -5*x\r\n--    5*x^10 + 4*x^4 + -3\r\n--    3*x^3 + -4\r\n--    10*x\r\ngenPol :: (Arbitrary a, Num a, Eq a) => Int -> Gen (Polinomio a)\r\ngenPol 0 = return polCero\r\ngenPol n = do n <- choose (0,10)\r\n              b <- arbitrary\r\n              p <- genPol (div n 2)\r\n              return (consPol n b p) \r\n\r\ninstance (Arbitrary a, Num a, Eq a) => Arbitrary (Polinomio a) where\r\n    arbitrary = sized genPol\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, Eq 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. Por ejemplo,\r\n--    ejPol2            ==  x^5 + 5*x^2 + 4*x\r\n--    termLider ejPol2  ==  x^5\r\ntermLider:: (Num t, Eq 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, Eq 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-- Propiedad. El polinomio cero es el elemento neutro de la suma.\r\nprop_neutroSumaPol :: Polinomio Int -> Bool\r\nprop_neutroSumaPol p = \r\n    sumaPol polCero p == p\r\n\r\n-- Comprobaci\u00f3n con QuickCheck.\r\n--    ghci> quickCheck prop_neutroSumaPol\r\n--    OK, passed 100 tests.\r\n\r\n-- Propiedad. La suma es conmutativa.\r\nprop_conmutativaSuma :: Polinomio Int -> Polinomio Int -> Bool\r\nprop_conmutativaSuma p q = \r\n    sumaPol p q == sumaPol q p\r\n\r\n-- Comprobaci\u00f3n:\r\n--    ghci> 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, Eq 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--    ghci> ejPol1\r\n--    3*x^4 + -5*x^2 + 3\r\n--    ghci> ejPol2\r\n--    x^5 + 5*x^2 + 4*x\r\n--    ghci> 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, Eq 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. El producto de polinomios es conmutativo.\r\nprop_conmutativaProducto :: Polinomio Int -> Polinomio Int -> Bool\r\nprop_conmutativaProducto p q = \r\n    multPol p q == multPol q p\r\n\r\n-- La comprobaci\u00f3n es\r\n--    ghci> quickCheck prop_conmutativaProducto\r\n--    OK, passed 100 tests.\r\n\r\n-- El producto es distributivo respecto de la suma.\r\nprop_distributivaProductoSuma :: Polinomio Int -> Polinomio Int \r\n                                 -> Polinomio Int -> Bool\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--    ghci> quickCheck prop_distributivaProductoSuma\r\n--    OK, passed 100 tests.\r\n\r\n-- polUnidad es el polinomio unidad. Por ejemplo, \r\n--    ghci> polUnidad\r\n--    1\r\npolUnidad:: (Num t, Eq 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 :: Polinomio Int -> Bool\r\nprop_polUnidad p = \r\n    multPol p polUnidad == p\r\n\r\n-- Comprobaci\u00f3n:\r\n--    ghci> 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 p 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, Eq 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, Eq 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-- (derivada p) es la derivada del polinomio p. Por ejemplo, \r\n--    ejPol2           ==  x^5 + 5*x^2 + 4*x\r\n--    derivada ejPol2  ==  5*x^4 + 10*x + 4\r\nderivada :: Polinomio Int -> Polinomio Int\r\nderivada p \r\n    | n == 0     = polCero\r\n    | otherwise  = consPol (n-1) (n*b) (derivada 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_derivada :: Polinomio Int -> Polinomio Int -> Bool\r\nprop_derivada p q =\r\n    derivada (sumaPol p q) == sumaPol (derivada p) (derivada q)\r\n\r\n-- Comprobaci\u00f3n\r\n--    ghci> quickCheck prop_derivada\r\n--    OK, passed 100 tests. \r\n\r\n-- ---------------------------------------------------------------------\r\n-- Resta de polinomios                                                --\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, Eq a) => Polinomio a -> Polinomio a -> Polinomio a\r\nrestaPol p q  = \r\n    sumaPol p (multPorTerm (creaTermino 0 (-1)) q)\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas hemos continuado el estudio del tipo abstracto de los polinomios y su implementaci\u00f3n 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&#8230;<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"open","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":[1],"tags":[270,298],"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\/3191"}],"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=3191"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/3191\/revisions"}],"predecessor-version":[{"id":3192,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/3191\/revisions\/3192"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=3191"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=3191"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=3191"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}