{"id":2030,"date":"2012-04-11T16:15:45","date_gmt":"2012-04-11T16:15:45","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=2030"},"modified":"2013-03-08T05:48:15","modified_gmt":"2013-03-08T05:48:15","slug":"i1m2011-operaciones-con-el-tad-de-los-polinomios-en-haskell-2","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2011-operaciones-con-el-tad-de-los-polinomios-en-haskell-2\/","title":{"rendered":"I1M2011: Operaciones con 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 estudiando la implementaci\u00f3n en Haskell de operaciones con los polinomios utilizando las implementaciones del TAD de los polinomios estudiadas en las clases anteriores.<\/p>\n<p>En los ejercicios se usan las siguientes libretr\u00edas:<\/p>\n<ul>\n<li> <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m\/codigos\/PolRepTDA.hs\">PolRepTDA<\/a>: Implementaci\u00f3n de los polinomios mediante tipos de datos algebraicos.\n<li> <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m\/codigos\/PolRepDispersa.hs\">PolRepDispersa<\/a>: Implementaci\u00f3n de los polinomios mediante listas dispersas.\n<li> <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m\/codigos\/PolRepDensa.hs\">PolRepDensa<\/a>: Implementaci\u00f3n de los polinomios mediante listas densas.\n<li> <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m\/codigos\/PolOperaciones.hs\">PolOperaciones<\/a>: Operaciones con el TAD de los polinomios.\n<\/ul>\n<p>Los ejercicios, y sus soluciones, se muestran a continuaci\u00f3n.<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\r\n-- ---------------------------------------------------------------------\r\n-- Importaci\u00f3n de librer\u00edas                                           --\r\n-- ---------------------------------------------------------------------\r\n\r\nimport PolOperaciones\r\nimport Test.QuickCheck\r\nimport Data.Ratio\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1. Definir la funci\u00f3n\r\n--    creaPolDispersa :: Num a => [a] -> Polinomio a\r\n-- tal que (creaPolDispersa xs) es el polinomio cuya representaci\u00f3n\r\n-- dispersa es xs. Por ejemplo,\r\n--    creaPolDispersa [7,0,0,4,0,3]  ==  7*x^5 + 4*x^2 + 3\r\n-- ---------------------------------------------------------------------\r\n\r\ncreaPolDispersa :: Num a => [a] -> Polinomio a\r\ncreaPolDispersa []     = polCero\r\ncreaPolDispersa (x:xs) = consPol (length xs) x (creaPolDispersa xs)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2. Definir la funci\u00f3n\r\n--    creaPolDensa :: Num a => [(Int,a)] -> Polinomio a\r\n-- tal que (creaPolDensa xs) es el polinomio cuya representaci\u00f3n\r\n-- densa es xs. Por ejemplo,\r\n--    creaPolDensa [(5,7),(4,2),(3,0)]  ==  7*x^5 + 2*x^4\r\n-- ---------------------------------------------------------------------\r\n\r\ncreaPolDensa :: Num a => [(Int,a)] -> Polinomio a\r\ncreaPolDensa [] = polCero\r\ncreaPolDensa ((n,a):ps) = consPol n a (creaPolDensa ps)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Nota. En el resto de la sucesi\u00f3n se usar\u00e1 en los ejemplos los\r\n-- los polinomios que se definen a continuaci\u00f3n.\r\n-- ---------------------------------------------------------------------\r\n\r\npol1, pol2, pol3 :: Num a => Polinomio a\r\npol1 = creaPolDensa [(5,1),(2,5),(1,4)]\r\npol2 = creaPolDispersa [2,3]\r\npol3 = creaPolDensa [(7,2),(4,5),(2,5)]\r\n\r\npol4, pol5, pol6 :: Polinomio Rational \r\npol4 = creaPolDensa [(4,3),(2,5),(0,3)]\r\npol5 = creaPolDensa [(2,6),(1,2)]\r\npol6 = creaPolDensa [(2,8),(1,14),(0,3)]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3. Definir la funci\u00f3n\r\n--    densa :: Num a => Polinomio a -> [(Int,a)]\r\n-- tal que (densa p) es la representaci\u00f3n densa del polinomio p. Por\r\n-- ejemplo, \r\n--    pol1        ==  x^5 + 5*x^2 + 4*x\r\n--    densa pol1  ==  [(5,1),(2,5),(1,4)]\r\n-- ---------------------------------------------------------------------\r\n\r\ndensa :: Num a => Polinomio a -> [(Int,a)]\r\ndensa p | esPolCero p = []\r\n        | otherwise   = (grado p, coefLider p) : densa (restoPol p)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 4. Definir la funci\u00f3n\r\n--    densaAdispersa :: Num a => [(Int,a)] -> [a]\r\n-- tal que (densaAdispersa ps) es la representaci\u00f3n dispersa del\r\n-- polinomio cuya representaci\u00f3n densa es ps. Por ejemplo,\r\n--    densaAdispersa [(5,1),(2,5),(1,4)]  ==  [1,0,0,5,4,0]\r\n-- ---------------------------------------------------------------------\r\n\r\ndensaAdispersa :: Num a => [(Int,a)] -> [a]\r\ndensaAdispersa [] = []\r\ndensaAdispersa [(n,a)] = a : replicate n 0\r\ndensaAdispersa ((n,a):(m,b):ps) = \r\n    a : (replicate (n-m-1) 0) ++ densaAdispersa ((m,b):ps)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 5. Definir la funci\u00f3n\r\n--    dispersa :: Num a => Polinomio a -> [a]\r\n-- tal que (dispersa p) es la representaci\u00f3n dispersa del polinomio\r\n-- p. Por ejemplo,\r\n--    pol1           ==  x^5 + 5*x^2 + 4*x\r\n--    dispersa pol1  ==  [1,0,0,5,4,0]\r\n-- ---------------------------------------------------------------------\r\n\r\ndispersa :: Num a => Polinomio a -> [a]\r\ndispersa = densaAdispersa . densa\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 6. Definir la funci\u00f3n\r\n--    coeficiente :: Num a => Int -> Polinomio a -> a\r\n-- tal que (coeficiente k p) es el coeficiente del t\u00e9rmino de grado k\r\n-- del polinomio p. Por ejemplo,\r\n--    pol1                ==  x^5 + 5*x^2 + 4*x\r\n--    coeficiente 2 pol1  ==  5\r\n--    coeficiente 3 pol1  ==  0\r\n-- ---------------------------------------------------------------------\r\n\r\ncoeficiente :: Num a => Int -> Polinomio a -> a\r\ncoeficiente k p | k == n                 = coefLider p\r\n                | k > grado (restoPol p) = 0\r\n                | otherwise              = coeficiente k (restoPol p)\r\n                where n = grado p\r\n\r\n-- Otra definici\u00f3n equivalente es\r\ncoeficiente' :: Num a => Int -> Polinomio a -> a\r\ncoeficiente' k p = busca k (densa p)\r\n    where busca k ps = head ([a | (n,a) <- ps, n == k] ++ [0])\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 7. Definir la funci\u00f3n\r\n--    coeficientes :: Num a => Polinomio a -> [a]\r\n-- tal que (coeficientes p) es la lista de los coeficientes del\r\n-- polinomio p. Por ejemplo,\r\n--    pol1               ==  x^5 + 5*x^2 + 4*x\r\n--    coeficientes pol1  ==  [1,0,0,5,4,0]\r\n-- ---------------------------------------------------------------------\r\n\r\ncoeficientes :: Num a => Polinomio a -> [a]\r\ncoeficientes p = [coeficiente k p | k <-[n,n-1..0]]\r\n    where n = grado p\r\n\r\n-- Una definici\u00f3n equivalente es\r\ncoeficientes' :: Num a => Polinomio a -> [a]\r\ncoeficientes' = dispersa\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 8. Definir la funci\u00f3n\r\n--    potencia :: Num a => Polinomio a -> Int -> Polinomio a\r\n-- tal que (potencia p n) es la potencia n-\u00e9sima del polinomio p. Por\r\n-- ejemplo, \r\n--    pol2             ==  2*x + 3\r\n--    potencia pol2 2  ==  4*x^2 + 12*x + 9\r\n--    potencia pol2 3  ==  8*x^3 + 36*x^2 + 54*x + 27\r\n-- ---------------------------------------------------------------------\r\n\r\npotencia :: Num a => Polinomio a -> Int -> Polinomio a\r\npotencia p 0 = polUnidad\r\npotencia p n = multPol p (potencia p (n-1))\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 9. Mejorar la definici\u00f3n de potencia definiendo la funci\u00f3n\r\n--    potenciaM :: Num a => Polinomio a -> Int -> Polinomio a\r\n-- tal que (potenciaM p n) es la potencia n-\u00e9sima del polinomio p,\r\n-- utilizando las siguientes propiedades:\r\n--    * Si n es par,   entonces x^n = (x^2)^(n\/2)\r\n--    * Si n es impar, entonces x^n = x * (x^2)^((n-1)\/2)\r\n-- Por ejemplo, \r\n--    pol2              ==  2*x + 3\r\n--    potenciaM pol2 2  ==  4*x^2 + 12*x + 9\r\n--    potenciaM pol2 3  ==  8*x^3 + 36*x^2 + 54*x + 27\r\n-- ---------------------------------------------------------------------\r\n\r\npotenciaM :: Num a => Polinomio a -> Int -> Polinomio a\r\npotenciaM p 0 = polUnidad\r\npotenciaM p n\r\n    | even n    = potenciaM (multPol p p) (n `div` 2)\r\n    | otherwise = multPol p (potenciaM (multPol p p) ((n-1) `div` 2))\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 estudiando la implementaci\u00f3n en Haskell de operaciones con los polinomios utilizando las implementaciones del TAD de los polinomios estudiadas en las clases anteriores. En los ejercicios se usan las siguientes libretr\u00edas: PolRepTDA: Implementaci\u00f3n de los polinomios mediante tipos de datos&#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\/2030"}],"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=2030"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/2030\/revisions"}],"predecessor-version":[{"id":2824,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/2030\/revisions\/2824"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=2030"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=2030"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=2030"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}