TAD de los conjuntos: Aplicación de una función a los elementos de un conjunto
Utilizando el tipo abstracto de datos de los conjuntos definir la función
|
1 |
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,
|
1 2 |
λ> mapC (*2) (inserta 3 (inserta 1 vacio)) {2, 6} |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
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. |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 |
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 |