Las relaciones binarias en un conjunto A se pueden representar mediante conjuntos de pares de elementos de A. Por ejemplo, la relación de divisibilidad en el conjunto {1,2,3,6} se representa por

[(1,1),(1,2),(1,3),(1,6),(2,2),(2,6),(3,3),(3,6),(6,6)]

La composición de dos relaciones binarias R y S en el conjunto A es la relación binaria formada por los pares (x,y) para los que existe un z tal que (x,z) ∈ R y (z,y) ∈ S.

Definir la función

composicion :: Eq a => [(a,a)] -> [(a,a)] -> [(a,a)]

tal que (composicion r s) es la composición de las relaciones binarias r y s. Por ejemplo,

λ> composicion [(1,2)] [(2,3),(2,4)]
[(1,3),(1,4)]
λ> composicion [(1,2),(5,2)] [(2,3),(2,4)]
[(1,3),(1,4),(5,3),(5,4)]
λ> composicion [(1,2),(1,4),(1,5)] [(2,3),(4,3)]
[(1,3)]
λ> composicion [(0,1)] [(2,3)]
[]

Nota: Se supone que las relaciones binarias son listas sin elementos repetidos.

Soluciones

import Data.List (nub)

composicion :: Eq a => [(a,a)] -> [(a,a)] -> [(a,a)]
composicion r s = nub [(x,y) | (x,u) <- r, (v,y) <- s, u == v]