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

José A. Alonso

22-03-2023

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

Se usarán las funciones conjuntoAlista y listaAconjunto definidas en el ejercicio Transformaciones entre conjuntos y listas.

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))

-- 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))))

# 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