Relaciones simétricas
Usando el tipo de las relaciones binarias, definir la función
|
1 |
simetrica :: Eq a => Rel a -> Bool |
tal que simetrica r se verifica si la relación r es simétrica. Por ejemplo,
|
1 2 3 |
simetrica (R ([1,3],[(1,1),(1,3),(3,1)])) == True simetrica (R ([1,3],[(1,1),(1,3),(3,2)])) == False simetrica (R ([1,3],[])) == True |
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 |
import Relaciones_binarias (Rel(R)) import Test.QuickCheck -- 1ª solución -- =========== simetrica :: Eq a => Rel a -> Bool simetrica (R (_,g)) = and [(y,x) `elem` g | (x,y) <- g] -- 2ª solución -- =========== simetrica2 :: Eq a => Rel a -> Bool simetrica2 (R (_,g)) = all (\(x,y) -> (y,x) `elem` g) g -- 3ª solución -- =========== simetrica3 :: Eq a => Rel a -> Bool simetrica3 (R (_,g)) = aux g where aux [] = True aux ((x,y):ps) = (y,x) `elem` g && aux ps -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_simetrica :: Rel Int -> Bool prop_simetrica r = all (== simetrica r) [simetrica2 r, simetrica3 r] -- La comprobación es -- λ> quickCheck prop_simetrica -- +++ 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 53 |
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 simetrica(r: Rel[A]) -> bool: (_, g) = r return all(((y, x) in g for (x, y) in g)) # 2ª solución # =========== def simetrica2(r: Rel[A]) -> bool: (_, g) = r def aux(ps: list[tuple[A, A]]) -> bool: if not ps: return True (x, y) = ps[0] return (y, x) in g and aux(ps[1:]) return aux(g) # 3ª solución # =========== def simetrica3(r: Rel[A]) -> bool: (_, g) = r for (x, y) in g: if (y, x) not in g: return False return True # Comprobación de equivalencia # ============================ # La propiedad es @given(st.integers(min_value=0, max_value=10)) def test_simetrica(n: int) -> None: r = relacionArbitraria(n) res = simetrica(r) assert simetrica2(r) == res assert simetrica3(r) == res # La comprobación es # > poetry run pytest -q Relaciones_simetricas.py # 1 passed in 0.11s |