interseccion :: Ord a => Conj a -> Conj a -> Conj a

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

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

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

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

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

interseccion2 :: Ord a => Conj a -> Conj a -> Conj a
interseccion2 c1 c2 =
  listaAconjunto [x | x <- conjuntoAlista c1, x `pertenece` c2]

-- 3ª solución
-- ===========

interseccion3 :: Ord a => Conj a -> Conj a -> Conj a
interseccion3 c1 c2 =
  listaAconjunto (conjuntoAlista c1 `intersect` conjuntoAlista c2)

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

-- La propiedad es
prop_interseccion :: Conj Int -> Conj Int -> Bool
prop_interseccion c1 c2 =
  all (== interseccion c1 c2)
      [interseccion2 c1 c2,
       interseccion3 c1 c2]

-- La comprobación es
--    λ> quickCheck prop_interseccion
--    +++ 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 interseccion(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 inserta(mc1, interseccion(rc1, c2))
    return interseccion(rc1, c2)

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

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

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

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

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

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

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

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

# La propiedad es
@given(c1=conjuntoAleatorio(), c2=conjuntoAleatorio())
def test_interseccion(c1: Conj[int], c2: Conj[int]) -> None:
    r = interseccion(c1, c2)
    assert interseccion2(c1, c2) == r
    assert interseccion3(c1, c2) == r
    assert interseccion4(c1, c2) == r

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