Relaciones binarias
Una relación binaria R sobre un conjunto A se puede mediante un par (u,g) donde u es la lista de los elementos de tipo A (el universo de R) y g es la lista de pares de elementos de u (el grafo de R).
Definir el tipo de dato (Rel a), para representar las relaciones binarias sobre a, y la función
1 |
esRelacionBinaria :: Eq a => Rel a -> Bool |
tal que esRelacionBinaria r
se verifica si r
es una relación binaria. Por ejemplo,
1 2 3 4 |
λ> esRelacionBinaria (R ([1, 3], [(3, 1), (3, 3)])) True λ> esRelacionBinaria (R ([1, 3], [(3, 1), (3, 2)])) False |
Además, definir un generador de relaciones binarias y comprobar que las relaciones que genera son relaciones binarias.
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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
import Data.List (nub) import Test.QuickCheck newtype Rel a = R ([a], [(a,a)]) deriving (Eq, Show) -- 1ª solución -- =========== esRelacionBinaria :: Eq a => Rel a -> Bool esRelacionBinaria (R (u, g)) = and [x `elem` u && y `elem` u | (x,y) <- g] -- 2ª solución -- =========== esRelacionBinaria2 :: Eq a => Rel a -> Bool esRelacionBinaria2 (R (u, g)) = all (\(x,y) -> x `elem` u && y `elem` u) g -- 3ª solución -- =========== esRelacionBinaria3 :: Eq a => Rel a -> Bool esRelacionBinaria3 (R (_, [])) = True esRelacionBinaria3 (R (u, (x,y):g)) = x `elem` u && y `elem` u && esRelacionBinaria3 (R (u, g)) -- Comprobación de equivalencia -- ============================ -- Generador de relaciones binarias. Por ejemplo, -- λ> sample (relacionArbitraria :: Gen (Rel Int)) -- R ([0],[]) -- R ([0,-1,1],[(0,-1),(0,1),(-1,1),(1,0)]) -- R ([1],[]) -- R ([-5,3],[(-5,-5),(-5,3),(3,-5),(3,3)]) -- R ([-2,-7],[(-7,-7)]) -- R ([11,-7],[]) -- R ([0],[]) -- R ([-13,-11],[(-13,-13)]) relacionArbitraria :: (Arbitrary a, Eq a) => Gen (Rel a) relacionArbitraria = do n <- choose (0, 10) u1 <- vectorOf n arbitrary let u = nub u1 g <- sublistOf [(x,y) | x <- u, y <- u] return (R (u, g)) -- Relaciones es una subclase de Arbitrary. instance (Arbitrary a, Eq a) => Arbitrary (Rel a) where arbitrary = relacionArbitraria -- La propiedad es prop_esRelacionBinaria :: Rel Int -> Bool prop_esRelacionBinaria r = esRelacionBinaria r && esRelacionBinaria2 r && esRelacionBinaria3 r -- La comprobación es -- λ> quickCheck prop_esRelacionBinaria -- +++ 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 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 |
from random import choice, randint, sample from typing import TypeVar from hypothesis import given from hypothesis import strategies as st A = TypeVar('A') Rel = tuple[list[A], list[tuple[A, A]]] # 1ª solución # =========== def esRelacionBinaria(r: Rel[A]) -> bool: (u, g) = r return all((x in u and y in u for (x, y) in g)) # 2ª solución # =========== def esRelacionBinaria2(r: Rel[A]) -> bool: (u, g) = r if not g: return True (x, y) = g[0] return x in u and y in u and esRelacionBinaria2((u, g[1:])) # 3ª solución # =========== def esRelacionBinaria3(r: Rel[A]) -> bool: (u, g) = r for (x, y) in g: if x not in u or y not in u: return False return True # Generador de relaciones binarias # ================================ # conjuntoArbitrario(n) es un conjunto arbitrario cuyos elementos están # entre 0 y n-1. Por ejemplo, # >>> conjuntoArbitrario(10) # [8, 9, 4, 5] # >>> conjuntoArbitrario(10) # [1, 2, 3, 4, 5, 6, 7, 8, 9] # >>> conjuntoArbitrario(10) # [0, 1, 2, 3, 6, 7, 9] # >>> conjuntoArbitrario(10) # [8, 2, 3, 7] def conjuntoArbitrario(n: int) -> list[int]: xs = sample(range(n), randint(0, n)) return list(set(xs)) # productoCartesiano(xs, ys) es el producto cartesiano de xs e ys. Por # ejemplo, # >>> productoCartesiano([2, 3], [1, 7, 5]) # [(2, 1), (2, 7), (2, 5), (3, 1), (3, 7), (3, 5)] def productoCartesiano(xs: list[int], ys: list[int]) -> list[tuple[int, int]]: return [(x, y) for x in xs for y in ys] # sublistaArbitraria(xs) es una sublista arbitraria de xs. Por ejemplo, # >>> sublistaArbitraria(range(10)) # [3, 7] # >>> sublistaArbitraria(range(10)) # [] # >>> sublistaArbitraria(range(10)) # [4, 1, 0, 9, 8, 7, 5, 6, 2, 3] def sublistaArbitraria(xs: list[A]) -> list[A]: n = len(xs) k = randint(0, n) return sample(xs, k) # relacionArbitraria(n) es una relación arbitraria tal que los elementos # de su universo están entre 0 y n-1. Por ejemplo, # >>> relacionArbitraria(3) # ([0, 1], [(1, 0), (1, 1)]) # >>> relacionArbitraria(3) # ([], []) # >>> relacionArbitraria(5) # ([0, 2, 3, 4], [(2, 0), (3, 3), (2, 3), (4, 0), (3, 4), (4, 2)]) def relacionArbitraria(n: int) -> Rel[int]: u = conjuntoArbitrario(n) g = sublistaArbitraria(productoCartesiano(u, u)) return (u, g) # Comprobación de la propiedad # ============================ # La propiedad es @given(st.integers(min_value=0, max_value=10)) def test_esRelacionBinaria(n: int) -> None: r = relacionArbitraria(n) assert esRelacionBinaria(r) assert esRelacionBinaria2(r) assert esRelacionBinaria3(r) # La comprobación es # > poetry run pytest -q Relaciones_binarias.py # 1 passed in 0.14s |