{"id":1952,"date":"2012-03-16T16:59:58","date_gmt":"2012-03-16T16:59:58","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=1952"},"modified":"2013-03-08T05:48:17","modified_gmt":"2013-03-08T05:48:17","slug":"i1m2011-el-tad-de-los-polinomios-en-haskell-1","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2011-el-tad-de-los-polinomios-en-haskell-1\/","title":{"rendered":"I1M2011: El TAD de los polinomios en Haskell (1)"},"content":{"rendered":"<p>En la clase de hoy de <a  href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-11\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> hemos estudiado el tipo abstracto de los polinomios y su implementaci\u00f3n en Haskell.<\/p>\n<p>Comenzamos la clase analizando las posibles representaciones de los polinomios y, como consecuencia, establecer la signatura y las propiedades del TAD de los polinomios.<\/p>\n<p>A continuaci\u00f3n, estudiamos tres prosibles representaciones del TAD de los polinomios: mediante tipos algebraicos, mediantes listas dispersas y mediante listas densas.<\/p>\n<p>Finalmente, estudiamos la implementaci\u00f3n de los polinomios como tipo algebraico y dejamos las otras dos como ejercicio.<\/p>\n<p>Las transparencias usadas en la clase son las p\u00e1ginas 1-15 del <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-10\/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 del programa es el siguiente<\/p>\n<pre lang=\"haskell\">\r\nmodule PolRepTDA\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 t => Polinomio t -> t                           \r\n    restoPol   -- Polinomio t -> Polinomio t                          \r\n  ) where\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-- 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-- Ejemplos de polinomios con coeficientes reales:\r\nejPol5, ejPol6, ejPol7:: Polinomio Float\r\nejPol5 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))\r\nejPol6 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))\r\nejPol7 = consPol 1 2 (consPol 4 6 polCero)\r\n\r\n-- Comprobaci\u00f3n de escritura:\r\n--    > ejPol5\r\n--    3.0*x^4 + -5.0*x^2 + 3.0\r\n--    > ejPol6\r\n--    x^5 + 5.0*x^2 + 4.0*x\r\n--    > ejPol7\r\n--    6.0*x^4 + 2.0*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--    > 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 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<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas hemos estudiado el tipo abstracto de los polinomios y su implementaci\u00f3n 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\u00f3n, estudiamos tres prosibles&#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":[295],"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\/1952"}],"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=1952"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1952\/revisions"}],"predecessor-version":[{"id":2840,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1952\/revisions\/2840"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=1952"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=1952"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=1952"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}