TAD de los conjuntos - Número de elementos de un conjunto

José A. Alonso

07-03-2023

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

   cardinal :: Conj a -> Int

tal que cardinal c es el número de elementos del conjunto c. Por ejemplo,

   cardinal (inserta 4 (inserta 5 vacio))             == 2
   cardinal (inserta 4 (inserta 5 (inserta 4 vacio))) == 2

Soluciones

Se usará la función conjuntoAlista definida 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, menor, elimina, esVacio)
import TAD_Transformaciones_conjuntos_listas (conjuntoAlista)
import Test.QuickCheck

-- 1ª solución
-- ===========

cardinal :: Ord a => Conj a -> Int
cardinal c
  | esVacio c = 0
  | otherwise = 1 + cardinal (elimina (menor c) c)

-- 2ª solución
-- ===========

cardinal2 :: Ord a => Conj a -> Int
cardinal2 = length . conjuntoAlista

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_cardinal :: Conj Int -> Bool
prop_cardinal c =
  cardinal c == cardinal2 c

-- La comprobación es
--    λ> quickCheck prop_cardinal
--    +++ OK, passed 100 tests.

Soluciones en Python

from __future__ import annotations

from abc import abstractmethod
from copy import deepcopy
from typing import 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

class Comparable(Protocol):
    @abstractmethod
    def __lt__(self: A, otro: A) -> bool:
        pass

A = TypeVar('A', bound=Comparable)

# 1ª solución
# ===========

def cardinal(c: Conj[A]) -> int:
    if esVacio(c):
        return 0
    return 1 + cardinal(elimina(menor(c), c))

# 2ª solución
# ===========

def cardinal2(c: Conj[A]) -> int:
    return len(conjuntoAlista(c))

# 3ª solución
# ===========

def cardinal3(c: Conj[A]) -> int:
    r = 0
    while not esVacio(c):
        r = r + 1
        c = elimina(menor(c), c)
    return r

# 4ª solución
# ===========

def cardinal4Aux(c: Conj[A]) -> int:
    r = 0
    while not c.esVacio():
        r = r + 1
        c.elimina(menor(c))
    return r

def cardinal4(c: Conj[A]) -> int:
    _c = deepcopy(c)
    return cardinal4Aux(_c)

# Comprobación de equivalencia
# ============================

@given(c=conjuntoAleatorio())
def test_cardinal(c: Conj[int]) -> None:
    r = cardinal(c)
    assert cardinal2(c) == r
    assert cardinal3(c) == r
    assert cardinal3(c) == r

# La comprobación es
#    src> poetry run pytest -q TAD_Numero_de_elementos_de_un_conjunto.py
#    1 passed in 0.33s