producto :: [a] -> [b] -> [(a,b)]

   producto [1,3] [2,4] == [(1,2),(1,4),(3,2),(3,4)]

import Test.QuickCheck

-- 1ª solución
-- ===========

producto1 :: [a] -> [a] -> [(a,a)]
producto1 xs ys = [(x,y) | x <- xs, y <- ys]

-- 2ª solución
-- ===========

producto2 :: [a] -> [a] -> [(a,a)]
producto2 []     _  = []
producto2 (x:xs) ys = [(x,y) | y <- ys] ++ producto2 xs ys

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_producto :: [Int] -> [Int] -> Bool
prop_producto xs ys =
  producto1 xs ys `iguales` producto2 xs ys

-- (iguales xs ys) se verifica si xs e ys son iguales. Por ejemplo,
--    iguales [3,2,3] [2,3]    ==  True
--    iguales [3,2,3] [2,3,2]  ==  True
--    iguales [3,2,3] [2,3,4]  ==  False
--    iguales [2,3] [4,5]      ==  False
iguales :: Ord a => [a] -> [a] -> Bool
iguales xs ys =
  subconjunto xs ys && subconjunto ys xs

-- (subconjunto xs ys) se verifica si xs es un subconjunto de ys. por
-- ejemplo,
--    subconjunto [3,2,3] [2,5,3,5]  ==  True
--    subconjunto [3,2,3] [2,5,6,5]  ==  False
subconjunto :: Ord a => [a] -> [a] -> Bool
subconjunto xs ys =
  [x | x <- xs, x `elem` ys] == xs

-- La comprobación es
--    λ> quickCheck prop_producto
--    +++ OK, passed 100 tests.

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> length (producto1 [1..4000] [1..4000])
--    16000000
--    (2.33 secs, 1,537,551,208 bytes)
--    λ> length (producto2 [1..4000] [1..4000])
--    16000000
--    (2.87 secs, 2,434,095,160 bytes)

-- Comprobación de la propiedad
-- ============================

-- La propiedad es
prop_elementos_producto :: [Int] -> [Int] -> Bool
prop_elementos_producto xs ys =
  length (producto1 xs ys) == length xs * length ys

-- La comprobación es
--    λ> quickCheck prop_elementos_producto
--    +++ OK, passed 100 tests.

from sys import setrecursionlimit
from timeit import Timer, default_timer
from typing import TypeVar

from hypothesis import given
from hypothesis import strategies as st

setrecursionlimit(10**6)

A = TypeVar('A')
B = TypeVar('B')

# 1ª solución
# ===========

def producto1(xs: list[A], ys: list[B]) -> list[tuple[A, B]]:
    return [(x, y) for x in xs for y in ys]

# 2ª solución
# ===========

def producto2(xs: list[A], ys: list[B]) -> list[tuple[A, B]]:
    if xs:
        return [(xs[0], y) for y in ys] + producto2(xs[1:], ys)
    return []

# Comprobación de equivalencia
# ============================

# La propiedad es
@given(st.lists(st.integers()),
       st.lists(st.integers()))
def test_producto(xs: list[int], ys: list[int]) -> None:
    assert sorted(producto1(xs, ys)) == sorted(producto2(xs, ys))

# La comprobación es
#    src> poetry run pytest -q producto_cartesiano_de_dos_conjuntos.py
#    1 passed in 0.31s

# Comparación de eficiencia
# =========================

def tiempo(e: str) -> None:
    """Tiempo (en segundos) de evaluar la expresión e."""
    t = Timer(e, "", default_timer, globals()).timeit(1)
    print(f"{t:0.2f} segundos")

# La comparación es
#    >>> tiempo('len(producto1(range(0, 1000), range(0, 500)))')
#    0.03 segundos
#    >>> tiempo('len(producto2(range(0, 1000), range(0, 500)))')
#    2.58 segundos

# Comprobación de la propiedad
# ============================

# La propiedad es
@given(st.lists(st.integers()),
       st.lists(st.integers()))
def test_elementos_producto(xs: list[int], ys: list[int]) -> None:
    assert len(producto1(xs, ys)) == len(xs) * len(ys)

# La comprobación es
#    src> poetry run pytest -q producto_cartesiano_de_dos_conjuntos.py
#    2 passed in 0.48s