Una funci\u00f3n 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 \u00fanico elemento b de B tal que (a,b) pertenece a f. Por ejemplo,<\/p>\n
Definir las funciones<\/p>\n
\n funciones :: (Ord a, Ord b) => [a] -> [b] -> [[(a,b)]]\n nFunciones :: (Ord a, Ord b) => [a] -> [b] -> Integer\n<\/pre>\ntales que<\/p>\n
\n \u03bb> funciones [1] [2]\n [[(1,2)]]\n \u03bb> funciones [1] [2,4]\n [[(1,2)],[(1,4)]]\n \u03bb> funciones [1,3] [2]\n [[(1,2),(3,2)]]\n \u03bb> funciones [1,3] [2,4]\n [[(1,2),(3,2)],[(1,2),(3,4)],[(1,4),(3,2)],[(1,4),(3,4)]]\n \u03bb> funciones [1,3] [2,4,6]\n [[(1,2),(3,2)],[(1,2),(3,4)],[(1,2),(3,6)],\n [(1,4),(3,2)],[(1,4),(3,4)],[(1,4),(3,6)],\n [(1,6),(3,2)],[(1,6),(3,4)],[(1,6),(3,6)]]\n \u03bb> funciones [1,3,5] [2,4]\n [[(1,2),(3,2),(5,2)],[(1,2),(3,2),(5,4)],[(1,2),(3,4),(5,2)],\n [(1,2),(3,4),(5,4)],[(1,4),(3,2),(5,2)],[(1,4),(3,2),(5,4)],\n [(1,4),(3,4),(5,2)],[(1,4),(3,4),(5,4)]]\n \u03bb> funciones [] []\n [[]]\n \u03bb> funciones [] [2]\n [[]]\n \u03bb> funciones [1] []\n []\n<\/pre>\n\n nFunciones [1,3] [2,4,6] == 9\n nFunciones [1,3,5] [2,4] == 8\n length (show (nFunciones2 [1..10^6] [1..10^3])) == 3000001\n<\/pre>\nSoluciones<\/h4>\n\nimport Data.List (genericLength, nub, sort, subsequences)\n\n-- 1\u00aa definici\u00f3n de funciones\n-- ==========================\n\nfunciones :: (Ord a, Ord b) => [a] -> [b] -> [[(a,b)]]\nfunciones xs ys =\n conjunto [r | r <- relaciones xs ys\n , esFuncion r xs ys]\n\n-- (relaciones xs ys) es el conjunto de las relaciones binarias entre xs\n-- e ys. Por ejemplo,\n-- \u03bb> relaciones [1,3] [2,4]\n-- [[],[(1,2)],[(1,4)],[(1,2),(1,4)],[(3,2)],[(1,2),(3,2)],\n-- [(1,4),(3,2)],[(1,2),(1,4),(3,2)],[(3,4)],[(1,2),(3,4)],\n-- [(1,4),(3,4)],[(1,2),(1,4),(3,4)],[(3,2),(3,4)],\n-- [(1,2),(3,2),(3,4)],[(1,4),(3,2),(3,4)],\n-- [(1,2),(1,4),(3,2),(3,4)]]\nrelaciones :: [a] -> [b] -> [[(a,b)]]\nrelaciones xs ys =\n subsequences (producto xs ys)\n\n-- (producto xs ys) es el producto cartesiano de xs e ys. Por ejemplo,\n-- producto [1,3] [2,4] == [(1,2),(1,4),(3,2),(3,4)]\nproducto :: [a] -> [b] -> [(a,b)]\nproducto xs ys =\n [(x,y) | x <- xs, y <- ys]\n\n-- (esFuncional r) r se verifica si la relaci\u00f3n r es funcional. Por\n-- ejemplo, \n-- esFuncional [(2,4),(1,5),(3,4)] == True\n-- esFuncional [(3,4),(1,4),(1,2),(3,4)] == False\nesFuncional :: (Ord a, Ord b) => [(a,b)] -> Bool\nesFuncional r =\n and [esUnitario (imagen r x) | x <- dominio r] \n\n-- (dominio r) es el dominio de la relaci\u00f3n r. Por ejemplo,\n-- dominio [(5,4),(1,4),(1,2),(3,4)] == [1,3,5]\ndominio :: Ord a => [(a,b)] -> [a]\ndominio = sort . nub . map fst\n\n-- (imagen r x) es la imagen de x en la relaci\u00f3n r. Por ejemplo,\n-- imagen [(5,4),(1,4),(1,2),(3,4)] 1 == [2,4]\n-- imagen [(5,4),(1,4),(1,2),(3,4)] 2 == []\nimagen :: (Ord a, Ord b) => [(a,b)] -> a -> [b]\nimagen r x =\n conjunto [y | (x1,y) <- r, x1 == x]\n\n-- (conjunto xs) es el conjunto (es decir, lista ordenada de elementos\n-- distintos) correspondiente a la lista xs. Por ejemplo, \n-- conjunto [7,2,3,2,7,3] == [2,3,7]\nconjunto :: Ord a => [a] -> [a]\nconjunto = sort . nub\n\n-- (esUnitario xs) se verifica si xs tiene s\u00f3lo un elemento.\nesUnitario :: [a] -> Bool\nesUnitario xs =\n length xs == 1\n\n-- (esFuncion r xs ys) se verifica si r es una funci\u00f3n con dominio xs y\n-- codominio ys. Por ejemplo,\n-- esFuncion [(2,4),(1,5),(3,4)] [1,2,3] [4,5,7] == True\n-- esFuncion [(2,4),(1,5),(3,4)] [1,3] [4,5,7] == False\n-- esFuncion [(2,4),(1,5),(3,4)] [1,2,3] [4,7] == False\n-- esFuncion [(1,4),(1,5),(3,4)] [1,2,3] [4,5,7] == False\nesFuncion :: (Ord a, Ord b) => [(a,b)] -> [a] -> [b] -> Bool\nesFuncion r xs ys =\n conjunto xs == dominio r \n && rango r `contenido` conjunto ys\n && esFuncional r\n\n-- (rango r) es el rango de la relaci\u00f3n r. Por ejemplo,\n-- rango [(5,4),(1,4),(1,2),(3,4)] == [2,4]\nrango :: Ord b => [(a,b)] -> [b]\nrango = sort . nub . map snd\n\n-- (contenido xs ys) se verifica si el conjunto xs est\u00e1 contenido en el\n-- ys. Por ejemplo,\n-- [1,3] `contenido` [1,2,3,5] == True\n-- [1,3] `contenido` [1,2,4,5] == False\ncontenido :: Ord a => [a] -> [a] -> Bool \ncontenido xs ys =\n all (`elem` ys) xs\n\n-- 2\u00aa definici\u00f3n de funciones\n-- ==========================\n\nfunciones2 :: (Ord a, Ord b) => [a] -> [b] -> [[(a,b)]]\nfunciones2 xs ys =\n conjunto (aux xs ys)\n where aux [] _ = [[]]\n aux [x] ys = [[(x,y)] | y <- ys]\n aux (x:xs) ys = [((x,y):f) | y <- ys, f <- fs]\n where fs = aux xs ys\n\n-- Comparaci\u00f3n de eficiencia de funciones\n-- ======================================\n\n-- \u03bb> length (funciones [1..4] [1..4]) \n-- 256\n-- (2.69 secs, 754,663,072 bytes)\n-- \u03bb> length (funciones2 [1..4] [1..4]) \n-- 256\n-- (0.04 secs, 243,600 bytes)\n\n-- 1\u00aa definici\u00f3n de nFunciones\n-- ===========================\n\nnFunciones :: (Ord a, Ord b) => [a] -> [b] -> Integer\nnFunciones xs ys =\n genericLength (funciones2 xs ys)\n\n-- 2\u00aa definici\u00f3n de nFunciones\n-- ===========================\n\nnFunciones2 :: (Ord a, Ord b) => [a] -> [b] -> Integer\nnFunciones2 xs ys =\n (genericLength ys)^(genericLength xs)\n\n-- Comparaci\u00f3n de eficiencia de nFunciones\n-- =======================================\n\n-- \u03bb> nFunciones [1..5] [1..5] \n-- 3125\n-- (1.35 secs, 1,602,872 bytes)\n-- \u03bb> nFunciones2 [1..5] [1..5] \n-- 3125\n-- (0.03 secs, 140,480 bytes)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"Una funci\u00f3n 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 \u00fanico elemento b de B tal que (a,b) pertenece a f. Por ejemplo, [(1,2),(3,6)] es una funci\u00f3n de [1,3] en [2,4,6]; [(1,2)] no es una funci\u00f3n…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[4],"tags":[41,100,8,26,10,24,11,6,14,88],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3457"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=3457"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3457\/revisions"}],"predecessor-version":[{"id":3500,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3457\/revisions\/3500"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=3457"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=3457"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=3457"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}