diferencia :: Ord a => Conj a -> Conj a -> Conj a

   λ> ej1 = inserta 5 (inserta 3 (inserta 2 (inserta 7 vacio)))
   λ> ej2 = inserta 7 (inserta 4 (inserta 3 vacio))
   λ> diferencia ej1 ej2
   {2, 5}
   λ> diferencia ej2 ej1
   {4}
   λ> diferencia ej1 ej1
   {}

import TAD.Conjunto (Conj, vacio, inserta, menor, elimina, pertenece, esVacio)
import TAD_Transformaciones_conjuntos_listas (conjuntoAlista, listaAconjunto)
import Test.QuickCheck

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

diferencia :: Ord a => Conj a -> Conj a -> Conj a
diferencia c1 c2
  | esVacio c1       = vacio
  | pertenece mc1 c2 = diferencia rc1 c2
  | otherwise        = inserta mc1 (diferencia rc1 c2)
  where mc1 = menor c1
        rc1 = elimina mc1 c1

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

diferencia2 :: Ord a => Conj a -> Conj a -> Conj a
diferencia2 c1 c2 =
  listaAconjunto [x | x <- conjuntoAlista c1, not (pertenece x c2)]

-- 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_diferencia :: Conj Int -> Conj Int -> Bool
prop_diferencia c1 c2 =
  diferencia c1 c2 == diferencia2 c1 c2

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

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

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

def diferencia(c1: Conj[A], c2: Conj[A]) -> Conj[A]:
    if esVacio(c1):
        return vacio()
    mc1 = menor(c1)
    rc1 = elimina(mc1, c1)
    if pertenece(mc1, c2):
        return diferencia(rc1, c2)
    return inserta(mc1, diferencia(rc1, c2))

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

def diferencia2(c1: Conj[A], c2: Conj[A]) -> Conj[A]:
    return listaAconjunto([x for x in conjuntoAlista(c1)
                           if not pertenece(x, c2)])

# 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 diferencia3Aux(c1: Conj[A], c2: Conj[A]) -> Conj[A]:
    r: Conj[A] = vacio()
    while not esVacio(c1):
        mc1 = menor(c1)
        if not pertenece(mc1, c2):
            r = inserta(mc1, r)
        c1 = elimina(mc1, c1)
    return r

def diferencia3(c1: Conj[A], c2: Conj[A]) -> Conj[A]:
    _c1 = deepcopy(c1)
    return diferencia3Aux(_c1, c2)

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

def diferencia4Aux(c1: Conj[A], c2: Conj[A]) -> Conj[A]:
    r: Conj[A] = Conj()
    while not c1.esVacio():
        mc1 = c1.menor()
        if not c2.pertenece(mc1):
            r.inserta(mc1)
        c1.elimina(mc1)
    return r

def diferencia4(c1: Conj[A], c2: Conj[A]) -> Conj[A]:
    _c1 = deepcopy(c1)
    return diferencia4Aux(_c1, c2)

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

# La propiedad es
@given(c1=conjuntoAleatorio(), c2=conjuntoAleatorio())
def test_diferencia(c1: Conj[int], c2: Conj[int]) -> None:
    r = diferencia(c1, c2)
    assert diferencia2(c1, c2) == r
    assert diferencia3(c1, c2) == r
    assert diferencia4(c1, c2) == r

# La comprobación de las propiedades es
#    > poetry run pytest -q TAD_Diferencia_de_conjuntos.py
#    1 passed in 0.31s