{"id":7922,"date":"2023-03-01T06:00:50","date_gmt":"2023-03-01T04:00:50","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=7922"},"modified":"2023-02-22T19:57:38","modified_gmt":"2023-02-22T17:57:38","slug":"01-mar-23","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/01-mar-23\/","title":{"rendered":"TAD de los conjuntos: Transformaciones entre conjuntos y listas"},"content":{"rendered":"<p>Utilizando el <a href=\"https:\/\/bit.ly\/3HbB7fo\">tipo abstracto de datos de los conjuntos<\/a> definir las funciones<\/p>\n<pre lang=\"text\">\n   listaAconjunto :: [a] -> Conj a\n   conjuntoAlista :: Conj a -> [a]\n<\/pre>\n<p>tales que<br \/>\n+ <code>listaAconjunto xs<\/code> es el conjunto formado por los elementos de <code>xs<\/code>. Por ejemplo,<\/p>\n<pre lang=\"text\">\n     \u03bb> listaAconjunto [3, 2, 5]\n     {2, 3, 5}\n<\/pre>\n<ul>\n<li><code>conjuntoAlista c<\/code> es la lista formada por los elementos del conjunto <code>c<\/code>. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     \u03bb> conjuntoAlista (inserta 5 (inserta 2 (inserta 3 vacio)))\n     [2,3,5]\n<\/pre>\n<p>Comprobar con QuickCheck que ambas funciones son inversa; es decir,<\/p>\n<pre lang=\"text\">\n   conjuntoAlista (listaAconjunto xs) = sort (nub xs)\n   listaAconjunto (conjuntoAlista c)  = c\n<\/pre>\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.Conjunto (Conj, vacio, inserta, menor, elimina, pertenece, esVacio)\nimport Data.List (sort, nub)\nimport Test.QuickCheck\n\n-- 1\u00aa definici\u00f3n de listaAconjunto\n-- ===============================\n\nlistaAconjunto :: Ord a => [a] -> Conj a\nlistaAconjunto []     = vacio\nlistaAconjunto (x:xs) = inserta x (listaAconjunto xs)\n\n-- 2\u00aa definici\u00f3n de listaAconjunto\n-- ===============================\n\nlistaAconjunto2 :: Ord a => [a] -> Conj a\nlistaAconjunto2 = foldr inserta vacio\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_listaAconjunto :: [Int] -> Bool\nprop_listaAconjunto xs =\n  listaAconjunto xs == listaAconjunto2 xs\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_listaAconjunto\n--    +++ OK, passed 100 tests.\n\n-- Definici\u00f3n de conjuntoAlista\n-- ============================\n\nconjuntoAlista :: Ord a => Conj a -> [a]\nconjuntoAlista c\n  | esVacio c = []\n  | otherwise = mc : conjuntoAlista rc\n  where mc = menor c\n        rc = elimina mc c\n\n-- Comprobaci\u00f3n de las propiedades\n-- ===============================\n\n-- La primera propiedad es\nprop_1_listaAconjunto :: [Int] -> Bool\nprop_1_listaAconjunto xs =\n  conjuntoAlista (listaAconjunto xs) == sort (nub xs)\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_1_listaAconjunto\n--    +++ OK, passed 100 tests.\n\n-- La segunda propiedad es\nprop_2_listaAconjunto :: Conj Int -> Bool\nprop_2_listaAconjunto c =\n  listaAconjunto (conjuntoAlista c) == c\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_2_listaAconjunto\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 __future__ import annotations\n\nfrom abc import abstractmethod\nfrom copy import deepcopy\nfrom functools import reduce\nfrom typing import Protocol, TypeVar\n\nfrom hypothesis import given\nfrom hypothesis import strategies as st\n\nfrom src.TAD.conjunto import (Conj, conjuntoAleatorio, elimina, esVacio,\n                              inserta, menor, pertenece, vacio)\n\nclass Comparable(Protocol):\n    @abstractmethod\n    def __lt__(self: A, otro: A) -> bool:\n        pass\n\nA = TypeVar('A', bound=Comparable)\n\n# 1\u00aa definici\u00f3n de listaAconjunto\n# ===============================\n\ndef listaAconjunto(xs: list[A]) -> Conj[A]:\n    if not xs:\n        return vacio()\n    return inserta(xs[0], listaAconjunto(xs[1:]))\n\n# 2\u00aa definici\u00f3n de listaAconjunto\n# ===============================\n\ndef listaAconjunto2(xs: list[A]) -> Conj[A]:\n    return reduce(lambda ys, y: inserta(y, ys), xs, vacio())\n\n# 3\u00aa soluci\u00f3n de listaAconjunto\n# =============================\n\ndef listaAconjunto3(xs: list[A]) -> Conj[A]:\n    c: Conj[A] = Conj()\n    for x in xs:\n        c.inserta(x)\n    return c\n\n# Comprobaci\u00f3n de equivalencia\n# ============================\n\n# La propiedad es\n@given(st.lists(st.integers()))\ndef test_listaAconjunto(xs: list[int]) -> None:\n    r = listaAconjunto(xs)\n    assert listaAconjunto2(xs) == r\n    assert listaAconjunto3(xs) == r\n\n# 1\u00aa definici\u00f3n de conjuntoAlista\n# ===============================\n\ndef conjuntoAlista(c: Conj[A]) -> list[A]:\n    if esVacio(c):\n        return []\n    mc = menor(c)\n    rc = elimina(mc, c)\n    return [mc] + conjuntoAlista(rc)\n\n# 2\u00aa definici\u00f3n de conjuntoAlista\n# ===============================\n\ndef conjuntoAlista2Aux(c: Conj[A]) -> list[A]:\n    if c.esVacio():\n        return []\n    mc = c.menor()\n    c.elimina(mc)\n    return [mc] + conjuntoAlista2Aux(c)\n\ndef conjuntoAlista2(c: Conj[A]) -> list[A]:\n    c1 = deepcopy(c)\n    return conjuntoAlista2Aux(c1)\n\n# 3\u00aa definici\u00f3n de conjuntoAlista\n# ===============================\n\ndef conjuntoAlista3Aux(c: Conj[A]) -> list[A]:\n    r = []\n    while not c.esVacio():\n        mc = c.menor()\n        r.append(mc)\n        c.elimina(mc)\n    return r\n\ndef conjuntoAlista3(c: Conj[A]) -> list[A]:\n    c1 = deepcopy(c)\n    return conjuntoAlista3Aux(c1)\n\n# Comprobaci\u00f3n de equivalencia de las definiciones de conjuntoAlista\n# ==============================================================\n\n@given(c=conjuntoAleatorio())\ndef test_conjuntoAlista(c: Conj[int]) -> None:\n    r = conjuntoAlista(c)\n    assert conjuntoAlista2(c) == r\n    assert conjuntoAlista3(c) == r\n\n# Comprobaci\u00f3n de las propiedades\n# ===============================\n\n# La primera propiedad es\n@given(st.lists(st.integers()))\ndef test_1_listaAconjunto(xs: list[int]) -> None:\n    assert conjuntoAlista(listaAconjunto(xs)) == sorted(list(set(xs)))\n\n# La segunda propiedad es\n@given(c=conjuntoAleatorio())\ndef test_2_listaAconjunto(c: Conj[int]) -> None:\n    assert listaAconjunto(conjuntoAlista(c)) == c\n\n# La comprobaci\u00f3n de las propiedades es\n#    > poetry run pytest -v TAD_Transformaciones_conjuntos_listas.py\n#       test_listaAconjunto PASSED\n#       test_conjuntoAlista PASSED\n#       test_1_listaAconjunto PASSED\n#       test_2_listaAconjunto PASSED\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Utilizando el tipo abstracto de datos de los conjuntos definir las funciones listaAconjunto :: [a] -> Conj a conjuntoAlista :: Conj a -> [a] tales que + listaAconjunto xs es el conjunto formado por los elementos de xs. Por ejemplo, \u03bb> listaAconjunto [3, 2, 5] {2, 3, 5} conjuntoAlista c es la lista formada por&#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":[331,585],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7922"}],"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=7922"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7922\/revisions"}],"predecessor-version":[{"id":7970,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/7922\/revisions\/7970"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=7922"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=7922"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=7922"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}