{"id":8041,"date":"2023-04-19T06:00:00","date_gmt":"2023-04-19T04:00:00","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=8041"},"modified":"2023-04-13T11:10:43","modified_gmt":"2023-04-13T09:10:43","slug":"19-abr-23","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/19-abr-23\/","title":{"rendered":"TAD de los polinomios: Transformaciones entre polinomios y listas dispersas"},"content":{"rendered":"<p>Utilizando el <a href=\"https:\/\/bit.ly\/3KwqXYu\">tipo abstracto de datos de los polinomios<\/a> definir las funciones<\/p>\n<pre lang=\"text\">\n   dispersaApolinomio :: (Num a, Eq a) => [(Int,a)] -> Polinomio a\n   polinomioAdispersa :: (Num a, Eq a) => Polinomio a -> [(Int,a)]\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li><code>dispersaApolinomio ps<\/code> es el polinomiocuya representaci\u00f3n dispersa es <code>ps<\/code>. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     \u03bb> dispersaApolinomio [(6,9),(3,5),(1,4),(0,7)]\n     9*x^6 + 5*x^3 + 4*x + 7\n<\/pre>\n<ul>\n<li><code>polinomioAdispersa p<\/code> es la representaci\u00f3n dispersa del polinomio <code>p<\/code>. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     \u03bb> ejPol = consPol 6 9 (consPol 3 5 (consPol 1 4 (consPol 0 7 polCero)))\n     \u03bb> ejPol\n     9*x^6 + 5*x^3 + 4*x + 7\n     \u03bb> polinomioAdispersa ejPol\n     [(6,9),(3,5),(1,4),(0,7)]\n<\/pre>\n<p>Comprobar con QuickCheck que ambas funciones son inversas.<\/p>\n<p><b>Soluciones<\/b><\/p>\n<p>A continuaci\u00f3n se muestran las <a href=\"#haskell\">soluciones en Haskell<\/a> y las <a href=\"#python\">soluciones en Python<\/a>.<\/p>\n<p><a name=\"haskell\"><\/a><br \/>\n<b>Soluciones en Haskell<\/b><\/p>\n<pre lang=\"haskell\">\nimport TAD.Polinomio (Polinomio, polCero, esPolCero, consPol, grado,\n                      coefLider, restoPol)\nimport Data.List (sort, nub)\nimport Test.QuickCheck\n\n-- 1\u00aa definici\u00f3n de dispersaApolinomio\n-- ===================================\n\ndispersaApolinomio :: (Num a, Eq a) => [(Int,a)] -> Polinomio a\ndispersaApolinomio []         = polCero\ndispersaApolinomio ((n,a):ps) = consPol n a (dispersaApolinomio ps)\n\n-- 2\u00aa definici\u00f3n de dispersaApolinomio\n-- ===================================\n\ndispersaApolinomio2 :: (Num a, Eq a) => [(Int,a)] -> Polinomio a\ndispersaApolinomio2 = foldr (\\(x,y) -> consPol x y) polCero\n\n\n-- 3\u00aa definici\u00f3n de dispersaApolinomio\n-- ===================================\n\ndispersaApolinomio3 :: (Num a, Eq a) => [(Int,a)] -> Polinomio a\ndispersaApolinomio3 = foldr (uncurry consPol) polCero\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- Tipo de las representaciones dispersas de polinomios.\nnewtype Dispersa = Dis [(Int,Int)]\n  deriving Show\n\n-- dispersaArbitraria es un generador de representaciones dispersas de\n-- polinomios. Por ejemplo,\n--    \u03bb> sample dispersaArbitraria\n--    Dis []\n--    Dis []\n--    Dis [(3,-2),(2,0),(0,3)]\n--    Dis [(6,1),(4,-2),(3,4),(2,-4)]\n--    Dis []\n--    Dis [(5,-7)]\n--    Dis [(12,5),(11,-8),(10,3),(8,-10),(7,-5),(4,12),(3,6),(2,-8),(1,11)]\n--    Dis [(7,-2),(2,-8)]\n--    Dis [(14,-15)]\n--    Dis [(17,5),(16,1),(15,-1),(14,10),(13,5),(12,-15),(9,12),(6,14)]\n--    Dis [(19,17),(12,7),(8,-3),(7,13),(5,-2),(4,7)]\ndispersaArbitraria :: Gen Dispersa\ndispersaArbitraria = do\n  (xs, ys) <- arbitrary\n  let xs' = nub (reverse (sort (map abs xs)))\n      ys' = filter (\/= 0) ys\n  return (Dis (zip xs' ys'))\n\n-- Dispersa est\u00e1 contenida en Arbitrary\ninstance Arbitrary Dispersa where\n  arbitrary = dispersaArbitraria\n\n-- La propiedad es\nprop_dispersaApolinomio :: Dispersa -> Bool\nprop_dispersaApolinomio (Dis ps) =\n  all (== dispersaApolinomio ps)\n      [dispersaApolinomio2 ps,\n       dispersaApolinomio3 ps]\n\n-- Definici\u00f3n de polinomioAdispersa\n-- ================================\n\npolinomioAdispersa :: (Num a, Eq a) => Polinomio a -> [(Int,a)]\npolinomioAdispersa p\n  | esPolCero p = []\n  | otherwise   = (grado p, coefLider p) : polinomioAdispersa (restoPol p)\n\n-- Propiedad de ser inversas\n-- =========================\n\n-- La primera propiedad es\nprop_polinomioAdispersa_dispersaApolinomio :: Dispersa -> Bool\nprop_polinomioAdispersa_dispersaApolinomio (Dis ps) =\n  polinomioAdispersa (dispersaApolinomio ps) == ps\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_polinomioAdispersa_dispersaApolinomio\n--    +++ OK, passed 100 tests.\n\n-- La segunda propiedad es\nprop_dispersaApolinomio_polinomioAdispersa :: Polinomio Int -> Bool\nprop_dispersaApolinomio_polinomioAdispersa p =\n  dispersaApolinomio (polinomioAdispersa p) == p\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_dispersaApolinomio_polinomioAdispersa\n--    +++ OK, passed 100 tests.\n<\/pre>\n<p><a name=\"python\"><\/a><br \/>\n<b>Soluciones en Python<\/b><\/p>\n<pre lang=\"python\">\nfrom typing import TypeVar\n\nfrom hypothesis import given\n\nfrom src.Polinomios_Transformaciones_dispersa_y_densa import dispersaAleatoria\nfrom src.TAD.Polinomio import (Polinomio, coefLider, consPol, esPolCero, grado,\n                               polCero, polinomioAleatorio, restoPol)\n\nA = TypeVar('A', int, float, complex)\n\n\n# 1\u00aa definici\u00f3n de dispersaApolinomio\n# ===================================\n\ndef dispersaApolinomio(ps: list[tuple[int, A]]) -> Polinomio[A]:\n    if not ps:\n        return polCero()\n    (n, a) = ps[0]\n    return consPol(n, a, dispersaApolinomio(ps[1:]))\n\n# 2\u00aa definici\u00f3n de dispersaApolinomio\n# ===================================\n\ndef dispersaApolinomio2(ps: list[tuple[int, A]]) -> Polinomio[A]:\n    r: Polinomio[A] = polCero()\n    for (n, a) in reversed(ps):\n        r = consPol(n, a, r)\n    return r\n\n# Comprobaci\u00f3n de equivalencia\n# ============================\n\n# La propiedad es\n@given(ps=dispersaAleatoria())\ndef test_dispersaApolinomio(ps: list[tuple[int, int]]) -> None:\n    assert dispersaApolinomio(ps) == dispersaApolinomio2(ps)\n\n# El generador dispersaAleatoria est\u00e1 definido en el ejercicio\n# \"Transformaciones entre las representaciones dispersa y densa\" que se\n# encuentra en https:\/\/bit.ly\/402UpuT\n\n# Definici\u00f3n de polinomioAdispersa\n# ================================\n\ndef polinomioAdispersa(p: Polinomio[A]) -> list[tuple[int, A]]:\n    if esPolCero(p):\n        return []\n    return [(grado(p), coefLider(p))] + polinomioAdispersa(restoPol(p))\n\n# Propiedad de ser inversas\n# =========================\n\n# La primera propiedad es\n@given(ps=dispersaAleatoria())\ndef test_polinomioAdispersa_dispersaApolinomio(ps: list[tuple[int,\n                                                              int]]) -> None:\n    assert polinomioAdispersa(dispersaApolinomio(ps)) == ps\n\n# La segunda propiedad es\n@given(p=polinomioAleatorio())\ndef test_dispersaApolinomio_polinomioAdispersa(p: Polinomio[int]) -> None:\n    assert dispersaApolinomio(polinomioAdispersa(p)) == p\n\n# La comprobaci\u00f3n es\n#    > poetry run pytest -v Polinomios_Transformaciones_polinomios_dispersas.py\n#    test_dispersaApolinomio PASSED\n#    test_polinomioAdispersa_dispersaApolinomio PASSED\n#    test_dispersaApolinomio_polinomioAdispersa PASSED\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Utilizando el tipo abstracto de datos de los polinomios definir las funciones dispersaApolinomio :: (Num a, Eq a) => [(Int,a)] -> Polinomio a polinomioAdispersa :: (Num a, Eq a) => Polinomio a -> [(Int,a)] tales que dispersaApolinomio ps es el polinomiocuya representaci\u00f3n dispersa es ps. Por ejemplo, \u03bb> dispersaApolinomio [(6,9),(3,5),(1,4),(0,7)] 9*x^6 + 5*x^3 + 4*x&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","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":[581],"tags":[265],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8041"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=8041"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8041\/revisions"}],"predecessor-version":[{"id":8043,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8041\/revisions\/8043"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=8041"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=8041"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=8041"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}