Clausura simétrica
Usando el tipo de las relaciones binarias, definir la función
|
1 |
clausuraSimetrica :: Eq a => Rel a -> Rel a |
tal que clausuraSimetrica r es la clausura simétrica de r; es decir, la menor relación simétrica que contiene a r. Por ejemplo,
|
1 2 |
λ> clausuraSimetrica (R ([1,3,5],[(1,1),(3,1),(1,5)])) R ([1,3,5],[(1,1),(3,1),(1,5),(1,3),(5,1)]) |
Comprobar con QuickCheck que clausuraSimetrica es simétrica.
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 |
import Relaciones_binarias (Rel(R)) import Data.List (union) import Relaciones_simetricas (simetrica) import Test.QuickCheck clausuraSimetrica :: Eq a => Rel a -> Rel a clausuraSimetrica (R (u,g)) = R (u, g `union` [(y,x) | (x,y) <- g]) -- La propiedad es prop_ClausuraSimetrica :: Rel Int -> Bool prop_ClausuraSimetrica r = simetrica (clausuraSimetrica r) -- La función simetrica está definida en el ejercicio -- "Relaciones simétricas" que se encuentra en -- https://bit.ly/3zlO2rH -- La comprobación es -- λ> quickCheck prop_ClausuraSimetrica -- +++ 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 |
from typing import TypeVar from hypothesis import given from hypothesis import strategies as st from src.Relaciones_binarias import Rel, relacionArbitraria from src.Relaciones_simetricas import simetrica A = TypeVar('A') def clausuraSimetrica(r: Rel[A]) -> Rel[A]: (u, g) = r return (u, list(set(g) | {(y, x) for (x,y) in g})) # 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) assert simetrica(clausuraSimetrica(r)) # La función simetrica está definida en el ejercicio # "Relaciones simétricas" que se encuentra en # https://bit.ly/3zlO2rH # La comprobación es # > poetry run pytest -q Clausura_simetrica.py # 1 passed in 0.12s |