Menu Close

Día: 30 marzo, 2023

Relaciones reflexivas

José A. Alonso, ,

Usando el tipo de las relaciones binarias, definir la función

   reflexiva :: Eq a => Rel a -> Bool

tal que reflexiva r se verifica si la relación r es reflexiva. Por ejemplo,

   reflexiva (R ([1,3],[(1,1),(1,3),(3,3)]))    ==  True
   reflexiva (R ([1,2,3],[(1,1),(1,3),(3,3)]))  ==  False

Soluciones

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


Soluciones en Haskell

module Relaciones_reflexivas where
 
import Relaciones_binarias (Rel(R))
import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
reflexiva :: Eq a => Rel a -> Bool
reflexiva (R ([], _))   = True
reflexiva (R (x:xs, ps)) = (x, x) `elem` ps && reflexiva  (R (xs, ps))
 
-- 2ª solución
-- ===========
 
reflexiva2 :: Eq a => Rel a -> Bool
reflexiva2 (R (us,ps)) = and [(x,x) `elem` ps | x <- us]
 
-- 3ª solución
-- ===========
 
reflexiva3 :: Eq a => Rel a -> Bool
reflexiva3 (R (us,ps)) = all (`elem` ps) [(x,x) | x <- us]
 
-- 4ª solución
-- ===========
 
reflexiva4 :: Eq a => Rel a -> Bool
reflexiva4 (R (us,ps)) = all (\x -> (x,x) `elem` ps) us
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_reflexiva :: Rel Int -> Bool
prop_reflexiva r =
  all (== reflexiva r)
      [reflexiva2 r,
       reflexiva3 r,
       reflexiva4 r]
 
-- La comprobación es
--    λ> quickCheck prop_reflexiva
--    +++ OK, passed 100 tests.


Soluciones en Python

from random import choice, randint, sample
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 reflexiva(r: Rel[A]) -> bool:
    (us, ps) = r
    if not us:
        return True
    return (us[0], us[0]) in ps and reflexiva((us[1:], ps))
 
# 2ª solución
# ===========
 
def reflexiva2(r: Rel[A]) -> bool:
    (us, ps) = r
    return all(((x,x) in ps for x in us))
 
# 3ª solución
# ===========
 
def reflexiva3(r: Rel[A]) -> bool:
    (us, ps) = r
    for x in us:
        if (x, x) not in ps:
            return False
    return True
 
# Comprobación de equivalencia
# ============================
 
# La propiedad es
@given(st.integers(min_value=0, max_value=10))
def test_reflexiva(n: int) -> None:
    r = relacionArbitraria(n)
    res = reflexiva(r)
    assert reflexiva2(r) == res
    assert reflexiva3(r) == res
 
# La comprobación es
#    > poetry run pytest -q Relaciones_reflexivas.py
#    1 passed in 0.41s
Leer más →