Clausura simétrica

José A. Alonso

13-04-2023

Usando el tipo de las relaciones binarias, definir las funciones

   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,

   λ> 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

Se usará la función simetrica definida en el ejercicio Relaciones simétricas.

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

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 comprobación es
--    λ> quickCheck prop_ClausuraSimetrica
--    +++ OK, passed 100 tests.

Soluciones en Python

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 comprobación es
#    > poetry run pytest -q Clausura_simetrica.py
#    1 passed in 0.12s