Menu Close

Día: 22 de marzo de 2023

TAD de los conjuntos: Aplicación de una función a los elementos de un conjunto

José A. Alonso, ,

Utilizando el tipo abstracto de datos de los conjuntos definir la función

   mapC :: (Ord a, Ord b) => (a -> b) -> Conj a -> Conj b

tal que map f c es el conjunto formado por las imágenes de los elementos del conjunto c, mediante la aplicación f. Por ejemplo,

   λ> mapC (*2) (inserta 3 (inserta 1 vacio))
   {2, 6}

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell

import TAD.Conjunto (Conj, vacio, inserta, esVacio, menor, elimina)
import TAD_Transformaciones_conjuntos_listas (conjuntoAlista, listaAconjunto)
import Test.QuickCheck.HigherOrder
 
-- 1ª solución
-- ===========
 
mapC :: (Ord a, Ord b) => (a -> b) -> Conj a -> Conj b
mapC f c
  | esVacio c = vacio
  | otherwise = inserta (f mc) (mapC f rc)
  where mc = menor c
        rc = elimina mc c
 
-- 2ª solución
-- ===========
 
mapC2 :: (Ord a, Ord b) => (a -> b) -> Conj a -> Conj b
mapC2 f c = listaAconjunto (map f (conjuntoAlista c))
 
-- Las funciones conjuntoAlista y listaAconjunto está definida en el
-- ejercicio Transformaciones entre conjuntos y listas" que se encuentra
-- en https://bit.ly/3RexzxH
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_mapC :: (Int -> Int) -> [Int] -> Bool
prop_mapC f xs =
  mapC f c == mapC2 f c
  where c = listaAconjunto xs
 
-- La comprobación es
--    λ> quickCheck' prop_mapC
--    +++ OK, passed 100 tests.


Soluciones en Python

from __future__ import annotations
 
from abc import abstractmethod
from copy import deepcopy
from typing import Callable, Protocol, TypeVar
 
from hypothesis import given
 
from src.TAD.conjunto import (Conj, conjuntoAleatorio, elimina, esVacio,
                              inserta, menor, vacio)
from src.TAD_Transformaciones_conjuntos_listas import (conjuntoAlista,
                                                       listaAconjunto)
 
class Comparable(Protocol):
    @abstractmethod
    def __lt__(self: A, otro: A) -> bool:
        pass
 
A = TypeVar('A', bound=Comparable)
B = TypeVar('B', bound=Comparable)
 
# 1ª solución
# ===========
 
def mapC(f: Callable[[A], B], c: Conj[A]) -> Conj[B]:
    if esVacio(c):
        return vacio()
    mc = menor(c)
    rc = elimina(mc, c)
    return inserta(f(mc), mapC(f, rc))
 
# 2ª solución
# ===========
 
def mapC2(f: Callable[[A], B], c: Conj[A]) -> Conj[B]:
    return listaAconjunto(list(map(f, conjuntoAlista(c))))
 
# Las funciones conjuntoAlista y listaAconjunto está definida en el
# ejercicio Transformaciones entre conjuntos y listas" que se encuentra
# en https://bit.ly/3RexzxH
 
# 3ª solución
# ===========
 
def mapC3Aux(f: Callable[[A], B], c: Conj[A]) -> Conj[B]:
    r: Conj[B] = vacio()
    while not esVacio(c):
        mc = menor(c)
        c = elimina(mc, c)
        r = inserta(f(mc), r)
    return r
 
def mapC3(f: Callable[[A], B], c: Conj[A]) -> Conj[B]:
    _c = deepcopy(c)
    return mapC3Aux(f, _c)
 
# 4ª solución
# ===========
 
def mapC4Aux(f: Callable[[A], B], c: Conj[A]) -> Conj[B]:
    r: Conj[B] = Conj()
    while not c.esVacio():
        mc = c.menor()
        c.elimina(mc)
        r.inserta(f(mc))
    return r
 
def mapC4(f: Callable[[A], B], c: Conj[A]) -> Conj[B]:
    _c = deepcopy(c)
    return mapC4Aux(f, _c)
 
# Comprobación de equivalencia de las definiciones
# ================================================
 
# La propiedad es
@given(c=conjuntoAleatorio())
def test_mapPila(c: Conj[int]) -> None:
    r = mapC(lambda x: 2 * x, c)
    assert mapC2(lambda x: 2 * x, c) == r
    assert mapC3(lambda x: 2 * x, c) == r
    assert mapC4(lambda x: 2 * x, c) == r
 
# La comprobación es
#    src> poetry run pytest -q TAD_mapC.py
#    1 passed in 0.29s
Leer más →