filtra :: Ord a => (a -> Bool) -> Conj a -> Conj a

   λ> filtra even (inserta 5 (inserta 4 (inserta 7 (inserta 2 vacio))))
   {2, 4}
   λ> filtra odd (inserta 5 (inserta 4 (inserta 7 (inserta 2 vacio))))
   {5, 7}

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

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

filtra :: Ord a => (a -> Bool) -> Conj a -> Conj a
filtra p c
  | esVacio c = vacio
  | p mc      = inserta mc (filtra p rc)
  | otherwise = filtra p rc
  where mc = menor c
        rc = elimina mc c

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

filtra2 :: Ord a => (a -> Bool) -> Conj a -> Conj a
filtra2 p c =
  listaAconjunto (filter p (conjuntoAlista c))

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

-- La propiedad es
prop_filtra :: (Int -> Bool) -> [Int] -> Bool
prop_filtra p xs =
  filtra p c == filtra2 p c
  where c = listaAconjunto xs

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

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, 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 filtra(p: Callable[[A], bool], c: Conj[A]) -> Conj[A]:
    if esVacio(c):
        return vacio()
    mc = menor(c)
    rc = elimina(mc, c)
    if p(mc):
        return inserta(mc, filtra(p, rc))
    return filtra(p, rc)

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

def filtra2(p: Callable[[A], bool], c: Conj[A]) -> Conj[A]:
    return listaAconjunto(list(filter(p, conjuntoAlista(c))))

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

def filtra3Aux(p: Callable[[A], bool], c: Conj[A]) -> Conj[A]:
    r: Conj[A] = vacio()
    while not esVacio(c):
        mc = menor(c)
        c = elimina(mc, c)
        if p(mc):
            r = inserta(mc, r)
    return r

def filtra3(p: Callable[[A], bool], c: Conj[A]) -> Conj[A]:
    _c = deepcopy(c)
    return filtra3Aux(p, _c)

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

def filtra4Aux(p: Callable[[A], bool], c: Conj[A]) -> Conj[A]:
    r: Conj[A] = Conj()
    while not c.esVacio():
        mc = c.menor()
        c.elimina(mc)
        if p(mc):
            r.inserta(mc)
    return r

def filtra4(p: Callable[[A], bool], c: Conj[A]) -> Conj[A]:
    _c = deepcopy(c)
    return filtra4Aux(p, _c)

# Comprobación de equivalencia de las definiciones
# ================================================

# La propiedad es
@given(c=conjuntoAleatorio())
def test_filtra(c: Conj[int]) -> None:
    r = filtra(lambda x: x % 2 == 0, c)
    assert filtra2(lambda x: x % 2 == 0, c) == r
    assert filtra3(lambda x: x % 2 == 0, c) == r
    assert filtra4(lambda x: x % 2 == 0, c) == r

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