{"id":2036,"date":"2012-04-13T17:04:13","date_gmt":"2012-04-13T17:04:13","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=2036"},"modified":"2013-03-08T05:48:15","modified_gmt":"2013-03-08T05:48:15","slug":"i1m2011-operaciones-con-el-tad-de-los-polinomios-en-haskell-3","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2011-operaciones-con-el-tad-de-los-polinomios-en-haskell-3\/","title":{"rendered":"I1M2011: Operaciones con el TAD de los polinomios en Haskell (3)"},"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 librer\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\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 10. Definir la funci\u00f3n\r\n--    integral :: Fractional a => Polinomio a -> Polinomio a\r\n-- tal que (integral p) es la integral del polinomio p cuyos coefientes\r\n-- son n\u00fameros racionales. Por ejemplo,\r\n--    ghci> pol3\r\n--    2*x^7 + 5*x^4 + 5*x^2\r\n--    ghci> integral pol3\r\n--    0.25*x^8 + x^5 + 1.6666666666666667*x^3\r\n--    ghci> integral pol3 :: Polinomio Rational\r\n--    1 % 4*x^8 + x^5 + 5 % 3*x^3\r\n-- ---------------------------------------------------------------------\r\n\r\nintegral :: Fractional a => Polinomio a -> Polinomio a\r\nintegral p \r\n    | esPolCero p = polCero\r\n    | otherwise   = consPol (n+1) (b \/ (fromIntegral (n+1))) (integral r)\r\n    where n = grado p\r\n          b = coefLider p\r\n          r = restoPol p\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 11. Definir la funci\u00f3n\r\n--    integralDef :: Fractional t => Polinomio t -> t -> t -> t          \r\n-- tal que (integralDef p a b) es la integral definida del polinomio p\r\n-- cuyos coefientes son n\u00fameros racionales. Por ejemplo,\r\n--    ghci> integralDef pol3 0 1\r\n--    2.916666666666667\r\n--    ghci> integralDef pol3 0 1 :: Rational\r\n--    35 % 12\r\n-- ---------------------------------------------------------------------\r\n\r\nintegralDef :: Fractional t => Polinomio t -> t -> t -> t          \r\nintegralDef p a b = (valor q b) - (valor q a)\r\n    where q = integral p\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 12. Definir la funci\u00f3n\r\n--    multEscalar :: Num a => a -> Polinomio a -> Polinomio a\r\n-- tal que (multEscalar c p) es el polinomio obtenido multiplicando el\r\n-- n\u00famero c por el polinomio p. Por ejemplo, \r\n--    pol2                    ==  2*x + 3\r\n--    multEscalar 4 pol2      ==  8*x + 12\r\n--    multEscalar (1%4) pol2  ==  1 % 2*x + 3 % 4\r\n-- ---------------------------------------------------------------------\r\n\r\nmultEscalar :: Num a => a -> Polinomio a -> Polinomio a\r\nmultEscalar c p \r\n  | esPolCero p = polCero\r\n  | otherwise   = consPol n (c*b) (multEscalar c r)\r\n  where n = grado p\r\n        b = coefLider p\r\n        r = restoPol p\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 13. Definir la funci\u00f3n\r\n--    cociente:: Fractional a => Polinomio a -> Polinomio a -> Polinomio a\r\n-- tal que (cociente p q) es el cociente de la divisi\u00f3n de p entre\r\n-- q. Por ejemplo, \r\n--    pol4  ==  3 % 1*x^4 + 5 % 1*x^2 + 3 % 1\r\n--    pol5  ==  6 % 1*x^2 + 2 % 1*x\r\n--    cociente pol4 pol5  ==  1 % 2*x^2 + (-1) % 6*x + 8 % 9\r\n-- ---------------------------------------------------------------------\r\n\r\ncociente:: Fractional a => Polinomio a -> Polinomio a -> Polinomio a\r\ncociente p q\r\n    | n2 == 0   = multEscalar (1\/a2) p\r\n    | n1 < n2   = polCero\r\n    | otherwise =  consPol n' a' (cociente p' q)\r\n    where n1 = grado p\r\n          a1 = coefLider p\r\n          n2 = grado q\r\n          a2 = coefLider q\r\n          n' = n1-n2\r\n          a' = a1\/a2\r\n          p' = restaPol p (multPorTerm (creaTermino n' a') q)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 14. Definir la funci\u00f3n\r\n--    resto:: Fractional a => Polinomio a -> Polinomio a -> Polinomio a\r\n-- tal que (resto p q) es el resto de la divisi\u00f3n de p entre q. Por\r\n-- ejemplo,  \r\n--    pol4  ==  3 % 1*x^4 + 5 % 1*x^2 + 3 % 1\r\n--    pol5  ==  6 % 1*x^2 + 2 % 1*x\r\n--    resto pol4 pol5  ==  (-16) % 9*x + 3 % 1\r\n-- ---------------------------------------------------------------------\r\n\r\nresto :: Fractional a => Polinomio a -> Polinomio a -> Polinomio a\r\nresto p q = restaPol p (multPol (cociente p q) q)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 15. Definir la funci\u00f3n\r\n--    divisiblePol :: Fractional a => Polinomio a -> Polinomio a -> Bool\r\n-- tal que (divisiblePol p q) se verifica si el polinomio p es divisible\r\n-- por el polinomio q. Por ejemplo,\r\n--    pol6  ==  8 % 1*x^2 + 14 % 1*x + 3 % 1\r\n--    pol2  ==  2*x + 3\r\n--    pol5  ==  6 % 1*x^2 + 2 % 1*x\r\n--    divisiblePol pol6 pol2  ==  True\r\n--    divisiblePol pol6 pol5  ==  False\r\n-- ---------------------------------------------------------------------\r\n\r\ndivisiblePol :: Fractional a => Polinomio a -> Polinomio a -> Bool\r\ndivisiblePol p q = esPolCero (resto p 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 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 librer\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\/2036"}],"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=2036"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/2036\/revisions"}],"predecessor-version":[{"id":2821,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/2036\/revisions\/2821"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=2036"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=2036"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=2036"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}