{"id":5407,"date":"2016-04-29T16:08:16","date_gmt":"2016-04-29T14:08:16","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=5407"},"modified":"2016-04-30T07:08:01","modified_gmt":"2016-04-30T05:08:01","slug":"i1m2105-ejercicios-con-el-tad-de-los-polinomios-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2105-ejercicios-con-el-tad-de-los-polinomios-en-haskell\/","title":{"rendered":"I1M2105: Ejercicios 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-15\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> se han explicado las soluciones de los ejercicios con el TAD de los polinomios.<\/p>\n<p>Los ejercicios y sus soluciones son<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\n-- ---------------------------------------------------------------------\n-- Introducci\u00f3n                                                       --\n-- ---------------------------------------------------------------------\n\n-- El objetivo de esta relaci\u00f3n es ampliar el conjunto de operaciones\n-- sobre polinomios definidas utilizando las implementaciones del TAD de\n-- polinomio estudiadas en el tema 21 \n--    http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-15\/temas\/tema-21.html\n-- \n-- Adem\u00e1s, en algunos ejemplos de usan polinomios con coeficientes\n-- racionales. En Haskell, el n\u00famero racional x\/y se representa por\n-- x%y. El TAD de los n\u00fameros racionales est\u00e1 definido en el m\u00f3dulo\n-- Data.Ratio.   \n-- \n-- Para realizar los ejercicios hay que tener instalada la librer\u00eda I1M\n-- que contiene la implementaci\u00f3n de TAD de los polinomios. Los pasos\n-- para instalarla son los siguientes:\n-- + Descargar el paquete I1M desde http:\/\/bit.ly\/1pbnDqm\n-- + Descomprimirlo (y se crea el directorio I1M-master.zip).\n-- + Cambiar al directorio I1M-master.\n-- + Ejecutar cabal install I1M.cabal\n-- \n-- Otra forma es descargar, en el directorio de ejercicios, la\n-- implementaci\u00f3n del TAD de polinomios: \n-- + PolRepTDA      que est\u00e1 en http:\/\/bit.ly\/1WJnS93\n-- + PolRepDispersa que est\u00e1 en http:\/\/bit.ly\/1WJnUO8\n-- + PolRepDensa    que est\u00e1 en http:\/\/bit.ly\/1WJnV4E \n-- + PolOperaciones que est\u00e1 en http:\/\/bit.ly\/1WJnTd7\n\n-- ---------------------------------------------------------------------\n-- Importaci\u00f3n de librer\u00edas                                           --\n-- ---------------------------------------------------------------------\n\nimport Test.QuickCheck\nimport Data.Ratio\n\n-- Hay que elegir una librer\u00eda \nimport I1M.PolOperaciones \n-- import PolOperaciones \n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1. Definir la funci\u00f3n\n--    creaPolDispersa :: (Num a, Eq a) => [a] -> Polinomio a\n-- tal que (creaPolDispersa xs) es el polinomio cuya representaci\u00f3n\n-- dispersa es xs. Por ejemplo,\n--    creaPolDispersa [7,0,0,4,0,3]  ==  7*x^5 + 4*x^2 + 3\n-- ---------------------------------------------------------------------\n\ncreaPolDispersa :: (Num a, Eq a) => [a] -> Polinomio a\ncreaPolDispersa []     = polCero\ncreaPolDispersa (x:xs) = consPol (length xs) x (creaPolDispersa xs)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2. Definir la funci\u00f3n\n--    creaPolDensa :: (Num a, Eq a) => [(Int,a)] -> Polinomio a\n-- tal que (creaPolDensa xs) es el polinomio cuya representaci\u00f3n\n-- densa es xs. Por ejemplo,\n--    creaPolDensa [(5,7),(4,2),(3,0)]  ==  7*x^5 + 2*x^4\n-- ---------------------------------------------------------------------\n\ncreaPolDensa :: (Num a, Eq a) => [(Int,a)] -> Polinomio a\ncreaPolDensa []         = polCero\ncreaPolDensa ((n,a):ps) = consPol n a (creaPolDensa ps)\n\n-- 2\u00aa definici\u00f3n\ncreaPolDensa2 :: (Num a, Eq a) => [(Int,a)] -> Polinomio a\ncreaPolDensa2 = foldr (\\(x,y) -> consPol x y) polCero\n\n-- 3\u00aa definici\u00f3n\ncreaPolDensa3 :: (Num a, Eq a) => [(Int,a)] -> Polinomio a\ncreaPolDensa3 = foldr (uncurry consPol) polCero\n\n-- ---------------------------------------------------------------------\n-- Nota. En el resto de la relaci\u00f3n se usar\u00e1 en los ejemplos los\n-- los polinomios que se definen a continuaci\u00f3n.\n-- ---------------------------------------------------------------------\n\npol1, pol2, pol3 :: (Num a, Eq a) => Polinomio a\npol1 = creaPolDensa [(5,1),(2,5),(1,4)]\npol2 = creaPolDispersa [2,3]\npol3 = creaPolDensa [(7,2),(4,5),(2,5)]\n\npol4, pol5, pol6 :: Polinomio Rational \npol4 = creaPolDensa [(4,3),(2,5),(0,3)]\npol5 = creaPolDensa [(2,6),(1,2)]\npol6 = creaPolDensa [(2,8),(1,14),(0,3)]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3. Definir la funci\u00f3n\n--    densa :: (Num a, Eq a) => Polinomio a -> [(Int,a)]\n-- tal que (densa p) es la representaci\u00f3n densa del polinomio p. Por\n-- ejemplo, \n--    pol1        ==  x^5 + 5*x^2 + 4*x\n--    densa pol1  ==  [(5,1),(2,5),(1,4)]\n-- ---------------------------------------------------------------------\n\ndensa :: (Num a, Eq a) => Polinomio a -> [(Int,a)]\ndensa p | esPolCero p = []\n        | otherwise   = (grado p, coefLider p) : densa (restoPol p)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4. Definir la funci\u00f3n\n--    densaAdispersa :: Num a => [(Int,a)] -> [a]\n-- tal que (densaAdispersa ps) es la representaci\u00f3n dispersa del\n-- polinomio cuya representaci\u00f3n densa es ps. Por ejemplo,\n--    densaAdispersa [(5,1),(2,5),(1,4)]  ==  [1,0,0,5,4,0]\n-- ---------------------------------------------------------------------\n\ndensaAdispersa :: Num a => [(Int,a)] -> [a]\ndensaAdispersa [] = []\ndensaAdispersa [(n,a)] = a : replicate n 0\ndensaAdispersa ((n,a):(m,b):ps) = \n    a : replicate (n-m-1) 0 ++ densaAdispersa ((m,b):ps)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 5. Definir la funci\u00f3n\n--    dispersa :: (Num a, Eq a) => Polinomio a -> [a]\n-- tal que (dispersa p) es la representaci\u00f3n dispersa del polinomio\n-- p. Por ejemplo,\n--    pol1           ==  x^5 + 5*x^2 + 4*x\n--    dispersa pol1  ==  [1,0,0,5,4,0]\n-- ---------------------------------------------------------------------\n\ndispersa :: (Num a, Eq a) => Polinomio a -> [a]\ndispersa = densaAdispersa . densa\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 6. Definir la funci\u00f3n\n--    coeficiente :: (Num a, Eq a) => Int -> Polinomio a -> a\n-- tal que (coeficiente k p) es el coeficiente del t\u00e9rmino de grado k\n-- del polinomio p. Por ejemplo,\n--    pol1                ==  x^5 + 5*x^2 + 4*x\n--    coeficiente 2 pol1  ==  5\n--    coeficiente 3 pol1  ==  0\n-- ---------------------------------------------------------------------\n\ncoeficiente :: (Num a, Eq a) => Int -> Polinomio a -> a\ncoeficiente k p | k == n                 = coefLider p\n                | k > grado (restoPol p) = 0\n                | otherwise              = coeficiente k (restoPol p)\n    where n = grado p\n\n-- Otra definici\u00f3n equivalente es\ncoeficiente2 :: (Num a, Eq a) => Int -> Polinomio a -> a\ncoeficiente2 k p = busca k (densa p)\n    where busca k ps = head ([a | (n,a) <- ps, n == k] ++ [0])\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 7. Definir la funci\u00f3n\n--    coeficientes :: (Num a, Eq a) => Polinomio a -> [a]\n-- tal que (coeficientes p) es la lista de los coeficientes del\n-- polinomio p. Por ejemplo,\n--    pol1               ==  x^5 + 5*x^2 + 4*x\n--    coeficientes pol1  ==  [1,0,0,5,4,0]\n-- ---------------------------------------------------------------------\n\ncoeficientes :: (Num a, Eq a) => Polinomio a -> [a]\ncoeficientes p = [coeficiente k p | k <- [n,n-1..0]]\n    where n = grado p\n\n-- 2\u00aa definici\u00f3n\ncoeficientes2 :: (Num a, Eq a) => Polinomio a -> [a]\ncoeficientes2 = dispersa\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 8. Definir la funci\u00f3n\n--    potencia :: (Num a, Eq a) => Polinomio a -> Int -> Polinomio a\n-- tal que (potencia p n) es la potencia n-\u00e9sima del polinomio p. Por\n-- ejemplo, \n--    pol2             ==  2*x + 3\n--    potencia pol2 2  ==  4*x^2 + 12*x + 9\n--    potencia pol2 3  ==  8*x^3 + 36*x^2 + 54*x + 27\n-- ---------------------------------------------------------------------\n\npotencia :: (Num a, Eq a) => Polinomio a -> Int -> Polinomio a\npotencia p 0 = polUnidad\npotencia p n = multPol p (potencia p (n-1))\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 9. Mejorar la definici\u00f3n de potencia definiendo la funci\u00f3n\n--    potenciaM :: (Num a, Eq a) => Polinomio a -> Int -> Polinomio a\n-- tal que (potenciaM p n) es la potencia n-\u00e9sima del polinomio p,\n-- utilizando las siguientes propiedades:\n--    * Si n es par,   entonces x^n = (x^2)^(n\/2)\n--    * Si n es impar, entonces x^n = x * (x^2)^((n-1)\/2)\n-- Por ejemplo, \n--    pol2              ==  2*x + 3\n--    potenciaM pol2 2  ==  4*x^2 + 12*x + 9\n--    potenciaM pol2 3  ==  8*x^3 + 36*x^2 + 54*x + 27\n-- ---------------------------------------------------------------------\n\npotenciaM :: (Num a, Eq a) => Polinomio a -> Int -> Polinomio a\npotenciaM p 0 = polUnidad\npotenciaM p n\n    | even n    = potenciaM (multPol p p) (n `div` 2)\n    | otherwise = multPol p (potenciaM (multPol p p) ((n-1) `div` 2))\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 10. Definir la funci\u00f3n\n--    integral :: (Fractional a, Eq a) => Polinomio a -> Polinomio a\n-- tal que (integral p) es la integral del polinomio p cuyos coefientes\n-- son n\u00fameros racionales. Por ejemplo,\n--    ghci> pol3\n--    2*x^7 + 5*x^4 + 5*x^2\n--    ghci> integral pol3\n--    0.25*x^8 + x^5 + 1.6666666666666667*x^3\n--    ghci> integral pol3 :: Polinomio Rational\n--    1 % 4*x^8 + x^5 + 5 % 3*x^3\n-- ---------------------------------------------------------------------\n\nintegral :: (Fractional a, Eq a) => Polinomio a -> Polinomio a\nintegral p \n    | esPolCero p = polCero\n    | otherwise   = consPol (n+1) (b \/ fromIntegral (n+1)) (integral r)\n    where n = grado p\n          b = coefLider p\n          r = restoPol p\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 11. Definir la funci\u00f3n\n--    integralDef :: (Fractional t, Eq t) => Polinomio t -> t -> t -> t\n-- tal que (integralDef p a b) es la integral definida del polinomio p\n-- cuyos coefientes son n\u00fameros racionales. Por ejemplo,\n--    ghci> integralDef pol3 0 1\n--    2.916666666666667\n--    ghci> integralDef pol3 0 1 :: Rational\n--    35 % 12\n-- ---------------------------------------------------------------------\n\nintegralDef :: (Fractional t, Eq t) => Polinomio t -> t -> t -> t          \nintegralDef p a b = valor q b - valor q a\n    where q = integral p\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 12. Definir la funci\u00f3n\n--    multEscalar :: (Num a, Eq a) => a -> Polinomio a -> Polinomio a\n-- tal que (multEscalar c p) es el polinomio obtenido multiplicando el\n-- n\u00famero c por el polinomio p. Por ejemplo, \n--    pol2                    ==  2*x + 3\n--    multEscalar 4 pol2      ==  8*x + 12\n--    multEscalar (1%4) pol2  ==  1 % 2*x + 3 % 4\n-- ---------------------------------------------------------------------\n\nmultEscalar :: (Num a, Eq a) => a -> Polinomio a -> Polinomio a\nmultEscalar c p \n  | esPolCero p = polCero\n  | otherwise   = consPol n (c*b) (multEscalar c r)\n  where n = grado p\n        b = coefLider p\n        r = restoPol p\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 13. Definir la funci\u00f3n\n--    cociente:: (Fractional a, Eq a) => \n--               Polinomio a -> Polinomio a -> Polinomio a\n-- tal que (cociente p q) es el cociente de la divisi\u00f3n de p entre\n-- q. Por ejemplo, \n--    pol4  ==  3 % 1*x^4 + 5 % 1*x^2 + 3 % 1\n--    pol5  ==  6 % 1*x^2 + 2 % 1*x\n--    cociente pol4 pol5  ==  1 % 2*x^2 + (-1) % 6*x + 8 % 9\n-- ---------------------------------------------------------------------\n\ncociente:: (Fractional a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a\ncociente p q\n    | n2 == 0   = multEscalar (1\/a2) p\n    | n1 < n2   = polCero\n    | otherwise =  consPol n3 a3 (cociente p3 q)\n    where n1 = grado p\n          a1 = coefLider p\n          n2 = grado q\n          a2 = coefLider q\n          n3 = n1-n2\n          a3 = a1\/a2\n          p3 = restaPol p (multPorTerm (creaTermino n3 a3) q)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 14. Definir la funci\u00f3n\n--    resto:: (Fractional a, Eq a) => \n--            Polinomio a -> Polinomio a -> Polinomio a\n-- tal que (resto p q) es el resto de la divisi\u00f3n de p entre q. Por\n-- ejemplo,  \n--    pol4  ==  3 % 1*x^4 + 5 % 1*x^2 + 3 % 1\n--    pol5  ==  6 % 1*x^2 + 2 % 1*x\n--    resto pol4 pol5  ==  (-16) % 9*x + 3 % 1\n-- ---------------------------------------------------------------------\n\nresto :: (Fractional a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a\nresto p q = restaPol p (multPol (cociente p q) q)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 15. Definir la funci\u00f3n\n--    divisiblePol :: (Fractional a, Eq a) => \n--                    Polinomio a -> Polinomio a -> Bool\n-- tal que (divisiblePol p q) se verifica si el polinomio p es divisible\n-- por el polinomio q. Por ejemplo,\n--    pol6  ==  8 % 1*x^2 + 14 % 1*x + 3 % 1\n--    pol2  ==  2*x + 3\n--    pol5  ==  6 % 1*x^2 + 2 % 1*x\n--    divisiblePol pol6 pol2  ==  True\n--    divisiblePol pol6 pol5  ==  False\n-- ---------------------------------------------------------------------\n\ndivisiblePol :: (Fractional a, Eq a) => Polinomio a -> Polinomio a -> Bool\ndivisiblePol p q = esPolCero (resto p q)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 16. El m\u00e9todo de Horner para calcular el valor de un\n-- polinomio se basa en representarlo de una forma forma alernativa. Por\n-- ejemplo, para calcular el valor de \n--    a*x^5 + b*x^4 + c*x^3 + d*x^2 + e*x + f\n-- se representa como\n--   (((((0 * x + a) * x + b) * x + c) * x + d) * x + e) * x + f\n-- y se eval\u00faa de dentro hacia afuera; es decir,\n--   v(0) = 0\n--   v(1) = v(0)*x+a = 0*x+a = a\n--   v(2) = v(1)*x+b = a*x+b \n--   v(3) = v(2)*x+c = (a*x+b)*x+c = a*x^2+b*x+c\n--   v(4) = v(3)*x+d = (a*x^2+b*x+c)*x+d = a*x^3+b*x^2+c*x+d\n--   v(5) = v(4)*x+e = (a*x^3+b*x^2+c*x+d)*x+e = a*x^4+b*x^3+c*x^2+d*x+e\n--   v(6) = v(5)*x+f = (a*x^4+b*x^3+c*x^2+d*x+e)*x+f = a*x^5+b*x^4+c*x^3+d*x^2+e*x+f\n-- \n-- Definir la funci\u00f3n\n--    horner :: (Num a, Eq a) => Polinomio a -> a -> a\n-- tal que (horner p x) es el valor del polinomio p al sustituir su\n-- variable por el n\u00famero x. Por ejemplo, \n--    horner pol1 0     ==  0\n--    horner pol1 1     ==  10\n--    horner pol1 1.5   ==  24.84375\n--    horner pol1 (3%2) ==  795 % 32\n-- ---------------------------------------------------------------------\n\nhorner :: (Num a, Eq a) => Polinomio a -> a -> a\nhorner p x = hornerAux (coeficientes p) 0 \n    where hornerAux [] v     = v\n          hornerAux (a:as) v = hornerAux as (v*x+a)\n\n-- El c\u00e1lculo de (horner pol1 2) es el siguiente\n--    horner pol1 2 \n--    = hornerAux [1,0,0,5,4,0] 0\n--    = hornerAux   [0,0,5,4,0] ( 0*2+1) = hornerAux   [0,0,5,4,0] 1\n--    = hornerAux     [0,5,4,0] ( 1*2+0) = hornerAux     [0,5,4,0] 2\n--    = hornerAux       [5,4,0] ( 2*2+0) = hornerAux       [5,4,0] 4\n--    = hornerAux         [4,0] ( 4*2+5) = hornerAux         [4,0] 13\n--    = hornerAux           [0] (13*2+4) = hornerAux           [0] 30 \n--    = hornerAux            [] (30*2+0) = hornerAux            [] 60 \n\n-- Una defininici\u00f3n equivalente por plegado es\nhorner2 :: (Num a, Eq a) => Polinomio a -> a -> a\nhorner2 p x = foldr (\\a b -> a + b*x) 0 (coeficientes p)\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 se han explicado las soluciones de los ejercicios con el TAD de los polinomios. Los ejercicios y sus soluciones son<\/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":[250],"tags":[270,310],"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\/5407"}],"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=5407"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5407\/revisions"}],"predecessor-version":[{"id":5411,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5407\/revisions\/5411"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=5407"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=5407"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=5407"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}