Una relación binaria entre dos conjuntos A y B se puede representar mediante un conjunto de pares (a,b) tales que a ∈ A y b ∈ B. Por ejemplo, la relación < entre A = {1,5,3} y B = {0,2,4} se representa por {(1,2),(1,4),(3,4)}.

Definir las funciones

relaciones  :: [a] -> [b] -> [[(a,b)]]
nRelaciones :: [a] -> [b] -> Integer

tales que

(relaciones xs ys) es el conjunto de las relaciones del conjunto xs en el conjunto ys. Por ejemplo,

λ> relaciones [1] [2]
[[],[(1,2)]]
λ> relaciones [1] [2,4]
[[],[(1,2)],[(1,4)],[(1,2),(1,4)]]
λ> relaciones [1,3] [2]
[[],[(1,2)],[(3,2)],[(1,2),(3,2)]]
λ> relaciones [1,3] [2,4]
[[],[(1,2)],[(1,4)],[(1,2),(1,4)],[(3,2)],[(1,2),(3,2)],
 [(1,4),(3,2)],[(1,2),(1,4),(3,2)],[(3,4)],[(1,2),(3,4)],
 [(1,4),(3,4)],[(1,2),(1,4),(3,4)],[(3,2),(3,4)],
 [(1,2),(3,2),(3,4)],[(1,4),(3,2),(3,4)],
 [(1,2),(1,4),(3,2),(3,4)]]
λ> relaciones [] []
[[]]
λ> relaciones [] [2]
[[]]
λ> relaciones [1] []
[[]]

(nRelaciones xs ys) es el número de relaciones del conjunto xs en el conjunto ys. Por ejemplo,

nRelaciones [1,2] [4,5]    ==  16
nRelaciones [1,2] [4,5,6]  ==  64
nRelaciones [0..9] [0..9]  ==  1267650600228229401496703205376

Soluciones

import Data.List (genericLength, subsequences)

relaciones :: [a] -> [b] -> [[(a,b)]]
relaciones xs ys =
  subsequences (producto xs ys)

-- (producto xs ys) es el producto cartesiano de xs e ys. Por ejemplo,
--    producto [1,3] [2,4]  ==  [(1,2),(1,4),(3,2),(3,4)]
producto :: [a] -> [b] -> [(a,b)]
producto xs ys =
  [(x,y) | x <- xs, y <- ys]

-- 1ª definición de nRelaciones
nRelaciones :: [a] -> [b] -> Integer
nRelaciones xs ys = genericLength (relaciones xs ys)

-- 2ª definición de nRelaciones
nRelaciones2 :: [a] -> [b] -> Integer
nRelaciones2 xs ys =
  2^(length xs * length ys)

-- Comparación de eficiencia
--    λ> nRelaciones [1..4] [1..5]
--    1048576
--    (1.17 secs, 228,243,608 bytes)
--    λ> nRelaciones2 [1..4] [1..5]
--    1048576
--    (0.02 secs, 144,856 bytes)

Exercitium

Conjunto de relaciones binarias entre dos conjuntos

Soluciones