{"id":4187,"date":"2014-03-11T21:57:24","date_gmt":"2014-03-11T20:57:24","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=4187"},"modified":"2014-03-11T21:57:24","modified_gmt":"2014-03-11T20:57:24","slug":"i1m2013-operaciones-con-el-tad-de-los-polinomios-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2013-operaciones-con-el-tad-de-los-polinomios-en-haskell\/","title":{"rendered":"I1M2013: Operaciones con el TAD de los polinomios en Haskell"},"content":{"rendered":"<p>En la primera parte de la clase de hoy de <a  href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-13\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> hemos estudiado las operaciones con los polinomios usando el TAD de los polinomios presentados en la <a href=\"http:\/\/bit.ly\/1otFzVJ\">clase anterior<\/a>.<\/p>\n<p>Las transparencias usadas en la clase son las p\u00e1ginas 42-55 del <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-13\/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 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 primera parte de la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas hemos estudiado las operaciones con los polinomios usando el TAD de los polinomios presentados en la clase anterior. Las transparencias usadas en la clase son las p\u00e1ginas 42-55 del tema 21<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","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":[222],"tags":[270,300,194,126],"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\/4187"}],"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=4187"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4187\/revisions"}],"predecessor-version":[{"id":4188,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4187\/revisions\/4188"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=4187"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=4187"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=4187"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}