Relaciones irreflexivas
Usando el tipo de las relaciones binarias, definir la función
1 |
irreflexiva :: Eq a => Rel a -> Bool |
tal que irreflexiva r
se verifica si la relación r
es irreflexiva; es decir, si ningún elemento de su universo está relacionado con él mismo. Por ejemplo,
1 2 |
irreflexiva (R ([1,2,3],[(1,2),(2,1),(2,3)])) == True irreflexiva (R ([1,2,3],[(1,2),(2,1),(3,3)])) == False |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
import Relaciones_binarias (Rel(R)) import Test.QuickCheck -- 1ª solución -- =========== irreflexiva :: Eq a => Rel a -> Bool irreflexiva (R (u,g)) = and [(x,x) `notElem` g | x <- u] -- 2ª solución -- =========== irreflexiva2 :: Eq a => Rel a -> Bool irreflexiva2 (R(u,g)) = all (\x -> (x,x) `notElem` g) u -- 3ª solución -- =========== irreflexiva3 :: Eq a => Rel a -> Bool irreflexiva3 (R(u,g)) = aux u where aux [] = True aux (x:xs) = (x,x) `notElem` g && aux xs -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_irreflexiva :: Rel Int -> Bool prop_irreflexiva r = all (== irreflexiva r) [irreflexiva2 r, irreflexiva3 r] -- La comprobación es -- λ> quickCheck prop_irreflexiva -- +++ OK, passed 100 tests. |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
from typing import TypeVar from hypothesis import given from hypothesis import strategies as st from src.Relaciones_binarias import Rel, relacionArbitraria A = TypeVar('A') # 1ª solución # =========== def irreflexiva(r: Rel[A]) -> bool: (u, g) = r return all(((x, x) not in g for x in u)) # 2ª solución # =========== def irreflexiva2(r: Rel[A]) -> bool: (u, g) = r def aux(xs: list[A]) -> bool: if not xs: return True return (xs[0], xs[0]) not in g and aux(xs[1:]) return aux(u) # 3ª solución # =========== def irreflexiva3(r: Rel[A]) -> bool: (u, g) = r for x in u: if (x, x) in g: return False return True # Comprobación de equivalencia # ============================ # La propiedad es @given(st.integers(min_value=0, max_value=10)) def test_irreflexiva(n: int) -> None: r = relacionArbitraria(n) res = irreflexiva(r) assert irreflexiva2(r) == res assert irreflexiva3(r) == res # La comprobación es # > poetry run pytest -q Relaciones_irreflexivas.py # 1 passed in 0.12s |