composicion :: Eq a => Rel a -> Rel a -> Rel a

   λ> composicion (R ([1,2],[(1,2),(2,2)])) (R ([1,2],[(2,1)]))
   R ([1,2],[(1,1),(2,1)])

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.

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