interseccion :: Eq a => [a] -> [a] -> [a]

   interseccion [3,2,5] [5,7,3,4]  ==  [3,5]
   interseccion [3,2,5] [9,7,6,4]  ==  []

import Data.List (nub, sort, intersect)
import qualified Data.Set as S (fromList, toList, intersection )
import Test.QuickCheck

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

interseccion1 :: Eq a => [a] -> [a] -> [a]
interseccion1 xs ys =
  [x | x <- xs, x `elem` ys]

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

interseccion2 :: Ord a => [a] -> [a] -> [a]
interseccion2 [] _ = []
interseccion2 (x:xs) ys
  | x `elem` ys = x : xs `interseccion2` ys
  | otherwise   = xs `interseccion2` ys

-- 3ª solución
-- ===========

interseccion3 :: Ord a => [a] -> [a] -> [a]
interseccion3 = intersect

-- 4ª solución
-- ===========

interseccion4 :: Ord a => [a] -> [a] -> [a]
interseccion4 xs ys =
  S.toList (S.fromList xs `S.intersection` S.fromList ys)

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

-- La propiedad es
prop_interseccion :: [Int] -> [Int] -> Bool
prop_interseccion xs ys =
  all (== sort (xs' `interseccion1` ys'))
      [sort (xs' `interseccion2` ys'),
       sort (xs' `interseccion3` ys'),
       xs' `interseccion4` ys']
  where xs' = nub xs
        ys' = nub ys

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

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

-- La comparación es
--    λ> length (interseccion1 [0..3*10^4] [1,3..3*10^4])
--    15000
--    (2.94 secs, 6,673,360 bytes)
--    λ> length (interseccion2 [0..3*10^4] [1,3..3*10^4])
--    15000
--    (3.04 secs, 9,793,440 bytes)
--    λ> length (interseccion3 [0..3*10^4] [1,3..3*10^4])
--    15000
--    (5.39 secs, 6,673,472 bytes)
--    λ> length (interseccion4 [0..3*10^4] [1,3..3*10^4])
--    15000
--    (0.04 secs, 8,593,176 bytes)

from typing import TypeVar
from timeit import Timer, default_timer
from sys import setrecursionlimit
from hypothesis import given, strategies as st

setrecursionlimit(10**6)

A = TypeVar('A')

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

def interseccion1(xs: list[A], ys: list[A]) -> list[A]:
    return [x for x in xs if x in ys]

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

def interseccion2(xs: list[A], ys: list[A]) -> list[A]:
    if not xs:
        return []
    if xs[0] in ys:
        return [xs[0]] + interseccion2(xs[1:], ys)
    return interseccion2(xs[1:], ys)

# 3ª solución
# ===========

def interseccion3(xs: list[A], ys: list[A]) -> list[A]:
    zs = []
    for x in xs:
        if x in ys:
            zs.append(x)
    return zs

# 4ª solución
# ===========

def interseccion4(xs: list[A], ys: list[A]) -> list[A]:
    return list(set(xs) & set(ys))

# Comprobación de equivalencia
# ============================
#
# La propiedad es
@given(st.lists(st.integers()),
       st.lists(st.integers()))
def test_interseccion(xs, ys):
    xs1 = list(set(xs))
    ys1 = list(set(ys))
    assert sorted(interseccion1(xs1, ys1)) ==\
           sorted(interseccion2(xs1, ys1)) ==\
           sorted(interseccion3(xs1, ys1)) ==\
           sorted(interseccion4(xs1, ys1))

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

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

def tiempo(e):
    """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('interseccion1(list(range(0,20000)), list(range(1,20000,2)))')
#    0.98 segundos
#    >>> tiempo('interseccion2(list(range(0,20000)), list(range(1,20000,2)))')
#    2.13 segundos
#    >>> tiempo('interseccion3(list(range(0,20000)), list(range(1,20000,2)))')
#    0.87 segundos
#    >>> tiempo('interseccion4(list(range(0,20000)), list(range(1,20000,2)))')
#    0.00 segundos