Composición de relaciones binarias
Usando el tipo de las relaciones binarias, definir la función
|
1 |
composicion :: Eq a => Rel a -> Rel a -> Rel a |
tal que composicion r s es la composición de las relaciones r y s. Por ejemplo,
|
1 2 |
λ> composicion (R ([1,2],[(1,2),(2,2)])) (R ([1,2],[(2,1)])) R ([1,2],[(1,1),(2,1)]) |
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 |
import Relaciones_binarias (Rel(R)) import Test.QuickCheck -- 1ª solución -- =========== composicion :: Eq a => Rel a -> Rel a -> Rel a composicion (R (u1,g1)) (R (_,g2)) = R (u1,[(x,z) | (x,y) <- g1, (y',z) <- g2, y == y']) -- 2ª solución -- =========== composicion2 :: Eq a => Rel a -> Rel a -> Rel a composicion2 (R (u1,g1)) (R (_,g2)) = R (u1, aux g1) where aux [] = [] aux ((x,y):g1') = [(x,z) | (y',z) <- g2, y == y'] ++ aux g1' -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_composicion :: Rel Int -> Rel Int -> Bool prop_composicion r1 r2 = composicion r1 r2 == composicion2 r1 r2 -- La comprobación es -- λ> quickCheck prop_composicion -- +++ 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 |
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 composicion(r1: Rel[A], r2: Rel[A]) -> Rel[A]: (u1, g1) = r1 (_, g2) = r2 return (u1, [(x, z) for (x, y) in g1 for (u, z) in g2 if y == u]) # 2ª solución # =========== def composicion2(r1: Rel[A], r2: Rel[A]) -> Rel[A]: (u1, g1) = r1 (_, g2) = r2 def aux(g: list[tuple[A, A]]) -> list[tuple[A, A]]: if not g: return [] (x, y) = g[0] return [(x, z) for (u, z) in g2 if y == u] + aux(g[1:]) return (u1, aux(g1)) # 2ª solución # =========== def composicion3(r1: Rel[A], r2: Rel[A]) -> Rel[A]: (u1, g1) = r1 (_, g2) = r2 r: list[tuple[A, A]] = [] for (x, y) in g1: r = r + [(x, z) for (u, z) in g2 if y == u] return (u1, r) # Comprobación de equivalencia # ============================ # La propiedad es @given(st.integers(min_value=0, max_value=10), st.integers(min_value=0, max_value=10)) def test_simetrica(n: int, m: int) -> None: r1 = relacionArbitraria(n) r2 = relacionArbitraria(m) res = composicion(r1, r2) assert composicion2(r1, r2) == res assert composicion2(r1, r2) == res # La comprobación es # > poetry run pytest -q Composicion_de_relaciones_binarias_v2.py # 1 passed in 0.19s |