{"id":1980,"date":"2012-03-20T16:47:55","date_gmt":"2012-03-20T16:47:55","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2011-el-tad-de-los-polinomios-en-haskell-2\/"},"modified":"2013-03-08T05:48:17","modified_gmt":"2013-03-08T05:48:17","slug":"i1m2011-el-tad-de-los-polinomios-en-haskell-2","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2011-el-tad-de-los-polinomios-en-haskell-2\/","title":{"rendered":"I1M2011: 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-11\">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\/i1m2011-el-tad-de-los-polinomios-en-haskell-1\">clase anterior<\/a>. Concretamente, hemos estudiado la implementaciones en Haskell del TAD de los polinomios mediantes listas dispersas y mediante listas densas.<\/p>\n<p>Las transparencias usadas en la clase son las p\u00e1ginas 16-31 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 de la representaci\u00f3n dispersa del TAD de los polinomios es<\/p>\n<pre lang=\"haskell\">\r\nmodule PolRepDispersa\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 dispersas                    --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- Representaremos 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-- Escritura de los polinomios                                        --\r\n-- ---------------------------------------------------------------------\r\n\r\ninstance Num a => Show (Polinomio a) 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 :: 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 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<\/pre>\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 (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 => 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","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 mediantes listas dispersas y mediante listas densas. Las transparencias&#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\/1980"}],"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=1980"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1980\/revisions"}],"predecessor-version":[{"id":2838,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1980\/revisions\/2838"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=1980"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=1980"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=1980"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}