Una función f entre dos conjuntos A e B se puede representar mediante una lista de pares de AxB tales que para cada elemento a de A existe un único elemento b de B tal que (a,b) pertenece a f. Por ejemplo,

• [(1,2),(3,6)] es una función de [1,3] en [2,4,6];
• [(1,2)] no es una función de [1,3] en [2,4,6], porque no tiene ningún par cuyo primer elemento sea igual a 3;
• [(1,2),(3,6),(1,4)] no es una función porque hay dos pares distintos cuya primera coordenada es 1.

Definir la función

funciones :: [a] -> [a] -> [[(a,a)]]

tal que (funciones xs ys) es el conjunto de las funciones de xs en ys. Por ejemplo,

λ> funciones [] [2,4,6]
[[]]
λ> funciones [3] [2,4,6]
[[(3,2)],[(3,4)],[(3,6)]]
λ> funciones [1,3] [2,4,6]
[[(1,2),(3,2)], [(1,2),(3,4)], [(1,2),(3,6)], [(1,4),(3,2)], [(1,4),(3,4)],
 [(1,4),(3,6)], [(1,6),(3,2)], [(1,6),(3,4)], [(1,6),(3,6)]]

Comprobar con QuickCheck que si xs es un conjunto con n elementos e ys un conjunto con m elementos, entonces (funciones xs ys) tiene m^n elementos.

Nota. Al hacer la comprobación limitar el tamaño de las pruebas como se indica a continuación

λ> quickCheckWith (stdArgs {maxSize=7}) prop_funciones
+++ OK, passed 100 tests.

Soluciones

import Test.QuickCheck

funciones :: [a] -> [a] -> [[(a,a)]]
funciones [] _      = [[]]
funciones (x:xs) ys = [((x,y):f) | y <- ys, f <- fs]
    where fs = funciones xs ys

prop_funciones :: [Int] -> [Int] -> Bool
prop_funciones xs ys =
    length (funciones xs ys) == (length ys)^(length xs)